AtCoder Regular Contest 129

　Cまで三完。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 129 Cまで三完。
A 最上位bitが打ち消し合うように。
B 左端の最大値と右端の最小値を管理
C "7"*xを組合せると高々5個で済むので、間に入れる数字を1 mod 7になるようにすればOK。

— titia (@titia_til) November 21, 2021

D - -1+2-1

　解説放送を聞いてAC。

　一時間考えていたけど、累積和なんて全く思い浮かばなかった。（階差は考えたが……）

　累積和を取るということが思い浮かべば、「初項に+2」「末尾の項に+2」以外の全ての操作は、累積和を一つ後ろの項へわたすような操作と分かる。なので、

・累積和の和が0になるよう、「初項に+2」「末尾の項に+2」により調整。

・あとは、「初項に+2」と「末尾の項に+2」は同じ回数ずつ使う。実際に操作が行えるよう、これらの操作回数を二分探索で決定（解説では二分探索していないが二分探索でも解ける）

　とすれば良い。

　なので、「累積和を取る」というのをどう思いつくのかが大事だろう。これは、

・「総和は変わらない」「数列が円環じゃない場合は簡単だから端の操作を特別視できそう」

　といったあたりから気付けなくてはいけなかったのだろうと思う。

　このあたりにギャップを感じるなら、maroonさんの公式解説の方が良いのかな……。こちらだと、操作で$i$を選んだ回数を$a_i$として立式することで、まあまあ自然に解法へと辿り着いているから。とはいえ、式を見たときこの考察へたどりつくのは簡単ではないな……。