ABは調子良く解けた。CDは、そこまで難しくはないものの、どこへ向かうかが難しく時間がかかった。みんな当たり前のようにCDを解いていて、昨日のABCでも感じた競プロerの特異な性質がここでも見える。内容は悪くなかったが、やっぱり勝てないのは面白くない。脳内BGMがずっと「俺だけ入れる隠しダンジョン」OPなの不吉だったよね。
CDは解説が何言ってるのかわからない。
A - Odd vs Even
めちゃくちゃ難しそう。とっかかりがない。1や素数について手で確認する。次に考えたのは、ある偶数が約数ならそれを2で割っても約数ということ。この方針もすっきりとは解けそうにない。ここで、約数の個数を求めるときに素因数分解するやつを考える。各素因数の個数+1の積だけど、素因数2について考えるとその超立方体を切ってる感じ。単に、各奇数の約数について2を何個乗せるか選べるということだ。つまり、素因数に2が0個なら奇数だけになり、2が1個なら同数、2が2個以上なら偶数が多くなる。こういう構造をしているのか。解くことで学べるいい問題。
B - Products of Min-Max
とりあえずソートしてしまっていい。最大値を固定する。ていうか最大値と最小値を固定するとその間の要素はどうでもいいので2冪になる。これでは計算量がNの2乗なのでまた最大値を固定してみる。最小値を動かして足していくが、その様子は最大値の位置が隣になってもちょっとずれるだけで似ている。なんか2倍して足してというのを区間を広げながら（最大値の位置を、0-indexedで1からN-1まで）。サンプルは合わないが、これまで考えていたのは最大値と最小値が異なる場合だけだった。なので1要素しか選ばない場合を足せばよい。
C - Multiple Sequences
数列の最後の要素を決め打ちする方針に行ってはまった。経路が何通りあるかコンビネーションでわかりそうだと思ってしまったが、実際はスタートもゴールも不定だしいくらでもジャンプできるし何回移動するかも不定で、不可能だった。
じゃあ何も決め打たず普通にDPで行けないか？これも、数列に何種類の数が現れるか不定なので難しい。しかし、1からMへ行くまでに最大でも17回しか変化しない（1が2^18になるのに18回でMは2^18より小さい）から、回数毎にDPできそうだ（今日は「できそう」って何回思ったことか）。自分の倍数に足していくDP。logが2つ付いてしまうのが気がかりだが、幸い最大ケースがサンプルにある。L回変化するとき、数列のN要素に仕切りをL個加えて、L+1種類の数を最低1個ずつは持つのでそのぶんを引いて、N-1個の中からL個を選択する。
昨日のC、ABC110Dじゃん！！当時できてた方針を、散々悩んで捨ててしまった（別の方法で解けたのもすごいが）。
— merom686 (@merom686) March 29, 2021
D - I Wanna Win The Game
総xorが0ということは、各ビット偶数個だけ立っている。つまりMが奇数なら0通り。そのような振り分け方が何通りあるかはDFSで求まる？いや、これは爆発してしまう。メモ化したら行けるようにも見える（この辺が感覚でわからないのが弱い（いやわからないのが普通だと思うけど相対的には弱い））。そして、実際は各ビットの立ってる個数の通り数ではなく数列の通り数を求める必要があるので、それができたとして何か工夫を考えるか別のアプローチをとる必要がある。この辺かなり色々な道があり、解けそうと無理そうを行ったり来たりし続けていた。上から「ここまでは何通りある」みたいな方針だったけど、普通に下が何通りか取ってくる方針に気づいてようやくレールに乗った。あとは下からもらってコンビネーションを掛けて足していくだけ。
爆発しそうなところメモ化再帰でまとめることができてしまうのが、感覚としてわからない。そういえば計算量を深く考えてなかった（DPテーブルがO(M*log(M))だし）けど、内部のループは平均N/log(M)程度だから結局2乗には収まってるのかな。
（追記）上からでやってみた。再帰でやろうとするとBFSみたいにせざるをえなくなりそうで（つまり無理そうで）、それなら普通に配るDPがいい。これは別に貰うDPでも書けるんだけど、自分の元の発想は配るほうで、配るDPの経験の少なさが出た。最近のCPUは書き込み遅くなさそうだし、積極的に配っていきたい。
E - Spread of Information
とりあえず思いつくのは、木の中心、直径、二分探索、全方位木DP。Eをやる時間が残ってなきゃあ話にならないんだよな。土俵に乗りたい。
