Codeforces Round 950 (Div. 3)

　F1まで。

コンテストへのリンク

コンテスト後のツイート

E {sorted(A[i])}がsetとして一致。列についても一致。
F1 あるmまでのnの最大値を持つ。
F2 F1で1になったものそれぞれについて、使わなかった場合との差分を計算。その計算する箇所は、一つ前に1だった場所～一つ後に1だった場所の間だけで良いはず。

— titia (@titia_til) June 3, 2024

F2. Field Division (hard version)

　自力AC。

　コンテスト中に考えていた方針であっていたが、実装が大変だった。Gに行かずF2に集中していたらギリギリ間に合っていたかなぁ……。

G. Yasya and the Mysterious Tree

　Binary Trieを使うということを参考にAC。

　ただし、コンテスト中は誤読しており、xorではなくorを計算するものと思っていた。これがなかったら解法を思い付いていた気がする。

　ただし実装には非常に苦戦した。

　自分のTrieだとTLEで通らず、Chat GPTによりC++へ書き換えると、エラーが起きてしまい、どこが間違っているか分かるまで一時間以上かかった。

　偶奇に分けて要素たちをBinary Trieに突っ込み、毎回自分の要素を減らした上で最適なものを探すのだが、要素数が0になっていたときの処理を怠っていた。

　Pythonのコードもバグっていたはずなのだけど、PythonだとLIST[-1]というのでエラーが出ないため、たまたま合ってしまっていたんですね……。

　修正してなんとかAC。

　ただ、C++でも制限時間ギリギリだったので、Trieの書き方に問題がありそう。Binary Trieをちゃんと書かないといけないのかな。