各頂点の出次数が１以上」というのは行き止まりがないという意味だった。構造がよくわからないままメモ化再帰でがんばった。■F 問題「Not Adjacent」。E 問題と点差が 25 点しかないなら点数の高い方を解かない理由がない。解けるも解けないもどれだけ時間がかかるかもほぼ同じだと仮定すればね。直前の要素を使った場合と使っていない場合の２種類に分けて DP をするのだと思った。提出 #70054346 (TLE×31/AC×22)。21 分かけて完成したものが TLE だった。答えを出すのにいっぱいいっぱいで高速化のアイデアはないので E 問題に行った。E 問題を 21 分で通してから戻ってきたら残り 10 分で、最大ケースを書いて進捗を表示してみたら半分くらいまではまともな時間で動いているようだった。半分全列挙だな。と思ってコンテスト終了前後に３回提出したけど、どれも WA だった (#70062539、#70064082、#70064700)。この日記を書いている最中にひらめいて提出した４個目でやっと AC (#70067158)。３回も何をしていたかというと前半後半のマージをするのに２×２の組み合わせの何が有効で何が無効かを判断しなければいけないのだけど、有効にしすぎ、無効にしすぎ、ちょうどいいという変遷をたどっていた。ちょうどいいのに WA になっていた原因はというと、DP をする順番に意味があるのです。ただ個数を半分にするのではいけない。前半は前から DP をし、後半は後ろから DP をすることで、最後に両者をマージしたときに正しい答えが出る。「
A の（連続するとは限らない）部分列」についての問題を解いているなんてことはもうとっくに頭の中から抜けているので順序が大事だということにきづかない。ちなみに、一方の値が 0 のときにもう一方にある M の倍数を作るペアが M-0 ではなく 0 (=(M-0)%M) だという罠にははまらなかった。これが初めてというわけではないので。■E 問題「Wind Cleaning」。144 ビットでグリッドを表現して BFS をしたけど、これは Ruby に甘えていたのかも。128 ビットに収まっていたなら C++ でも書けたと言い訳できるけど。上下左右への移動をいざ書いてみたら思いのほか簡単に、シフトしてからマスクとのアンドを取るだけで移動後のグリッドが得られた。提出まで 21 分。■点数にならなかった F 問題への寄り道で E 問題の AC が 20 分遅れたにもかかわらず 1509 パフォが出ていることに驚いている。コンテスト成績証。AI 新ルールによる追い風が絶大では？