練習メモ

メモ。
AGC010
D
・偶数が奇数個なら偶数を選び続ければ勝てる
奇数が混ざってるときgcdも奇数だから偶奇は反転しないので

逆条件をとって
・偶数が偶数個、奇数が２個以上なら負ける

・それ以外の時、「唯一の奇数」を選ばないと負け確なのでシュミレーションできる。
一回の操作で半分（=> 全部偶数の状態でgcdで割るから）なのでlog(maxAi)回しかシュミレーションしない

ということで順を追って考えればわかるんだけどこれ本番中に解けるのはめっちゃ頭いいと思う。
・偶数が奇数個なら偶数を選び続ければ勝てる
という条件を思いつくのが最難

F
・自分より大きい方に遷移したら、戻す操作を続けられて終了
というのをグラフにする。
難しいような難しくないような。

CF385Div2D
0346
8078
1302
8740

みたいな 「hidden matrix」があったとき
｛1..nの部分集合s｝を出力すると、各iについてmin mat[i][j](jはsの元）がかえってくる。
２０回以内で全部数字を当てろ。という問題。

sについて、kが含まれていたらmin mat[k][j]は0がかえってくる。つまり使えない情報がかえってくる。不純物がない集合、要するに[1..n] - kが欲しい。
そこで、各ビットが１のもの・０のもの全部を聞いておくと、任意のkについて
（kとビットが完全には一致しないものの集合）＝　[1..n] - k
が得られるので答えられる。
この問題めっちゃ面白いと思うんだけどけっこう解かれてるし典型なのかなあ。

CF385Div2E
集合のビットと「赤で得した数」を持つ。
ビットだけでは情報が足りない（トークンが余ってる量を持ちたいけど状態増えすぎるから）のでこうする、というのまあ普通にそうという感じなんだけどどうも苦手で解けない。

CF396Div2D
UnionFindのド典型。AOJのTrue LiarsからDPと復元（ほぼ全部じゃん）が消えた感じ。
コンテストに出してはいけないレベルで典型な気がするんだが。

最近RustにハマっているのでどうしてもAtCoder,CodeForcesが多い。
早くいろいろなオンラインジャッジがRustに対応してほしいものだ。