UTPC 2020
面白かった。
コンテスト時間が短すぎる。
opencupみたいな３人チーム戦とかなら丁度いいかも？
A
にぶたん
B
前から解こうとして開いたら難しくて、難易度順じゃないことを察したけど、なんとか解いた。
見た目が面白い。
第一印象は解ける問題に見えなかったけど、性質を頑張って考えると簡単な数え上げになった。
C
かなりよく出来た構築問。
3回やると端に+2が実現できるので偶奇が絡んでそうとなる。
実は偶奇（とnが小さすぎるときの真ん中は自由度がない）さえ満たしていれば可能だった。
操作回数制限が厳しいので、出来そうなことが限られてて、N=2D-1を考えると自然と解法が分かる。
D
教科書のような、お手本のような問題。
綺麗で好き。
なぜか分割統治出来ないやんと思って平方分割したらTLギリギリだった。
（ブロック単位での積とブロック内の積があれば$ x^kの係数はO(k)で求まる）
E
部分点は自明ではないけど簡単目で、それをじっくりデータ構造に載せようと考察すると、なんか、出来る。
シンプルな設定で程よい難度でいい問題。Eだけに。
F
解説はXを増やしていく方針だったけど、自分はY側を増やしていく方針だった。
良い典型。
G
行列式について明るければ自明。
行列式＝Σ有向グラフをサイクルに分解したときの辺の値の積
という見方をすれば、頂点ごとに接する（自己ループ以外の）辺の符号を反転するという操作をしても行列式は変わらないことが分かる。
好き。
こういう問題が1,2問入ってる5時間コンテスト、いいよね。
H
良心
I
$ C_iじゃなくて$ (10^6)^{J_i}で良くない？（詰めるなら$ 2^{J_i}で良い）
J
解けるとしたら貪欲だけど、どういう貪欲をしたものか・・・
最初はAを昇順に処理しようとしていたが、$ A=\{1,1,2,2\}のとき$ B=\{3,3\}か$ B=\{2,4\}かで次の１手が変わって困っていた。
で、Bの降順でやってみると見事に貪欲が回って感動した。
綺麗。好き。
K
問題を読んだ段階では掴みどころがなくて何をすればいいのか取っ掛かりがつかめなかった。
とりあえずCに関して考えると、サイクルの集合みたいな構造だと分かる。
A,Bに関しては、なんか良い性質のをK個ずつ取り出して使うんだろうなぁとなる。
制約を眺めると、和が一定の組をK個取ることが可能だと分かる。
ただ、Cはdistinctじゃないといけないので、和が一定でも嬉しくなさそう。
差が一定も同様に取れることが分かる。
差が一定なら和はdistinctなので、これをCにしてみる。
でもそれだとスケールが合わないので、平均にしてみる。
グラフに戻って考えてみると、なんかうまく行った。
L
数論は弱いので、程々のところで解説読んだ。
なるほど、複素数使うといいのか。
modが4n+1なら i があるから複素数が定義できるのか。
勉強になった。
綺麗な良問。
M
これ思い出した。
maroon先生って、すげ〜