AtCoder Regular Contest 146

　AB二完で終了。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 146 ABの二完。
A 大きい三数の入れ替え
B 大きいbitから貪欲に、ANSの最大値のそのbitを1にできるか？　と考える。そのときに必要な回数をもちこし、変化させたA[i]=0としておく（その後はもっと小さいbitしか考えないので）。

— titia (@titia_til) August 20, 2022

C - Even XOR

　解説AC。

　コンテスト終盤、Sの要素で場合分けする、という方針を思い付き、N=4までは実験コードと結果が一致した。そのとき考えていたのは、

・相異なる3要素がSに入っていれば、それ以外の要素一つが禁止になる

　というものだった。偶然N=4までは一致したが、これは間違い。

　線形独立性を考えるのがポイントで、正しくは、

・x個の要素がSに入ったら、x個のうち一つを0に平行移動させ、それと線形従属な$2^{(x-1)}$個が禁止になる

　だった。

　コンテスト中書いていたコードを少し変えれば通った……という意味では惜しかったが、線形独立性は全く思いついていなかったので本質が分かっていなかったという意味では惜しくなかった。

D - >=<

　珍しく自力AC。

　できるだけ小さくしたいので、ANS=[1]*Nから始めて、条件p, x, q, yについて、ANS[p]>=x となる部分があればANS[q]=max(ANS[q], y)もしくはANS[q]=max(ANS[q], y+1)と、条件を満たす最小値へ更新していく。

　今更だけど、CでなくDへ行くべきでしたね。題意を理解するのにちょっと時間がかかる問題なので避けてしまったけど、ちゃんと検討すべきだったかなぁ。