今年はダメだったよ。順当な結果ではある。
A - DDCC Finals
去年の本戦に出てたので1000000円を獲得するのをこの目で見た。状況を知っているので若干有利。実装は、10万円単位で計算して最後に10万を掛ける。
B - Iron Bar Cutting
2020202020って何だよ！2*10^9と書いてほしい。非本質で30秒くらい使った。操作が2種類あるし難しそうに見えたが、どこで切るか決め打ちすれば左の和と右の和をabs(左の和-右の和)回の操作で合わせるしかないとわかる。縮めるのには限界があるが、膨張は制限がないので膨張だけすればいい。どちらも状況が1しか改善しないのは同じ。あとは全体の和を先に求めておけば各切れ目についてO(1)で求まる。ループ回数はN-1。
C - Strawberry Cakes
しばらく碁石をイチゴの代わりに並べてウンウンうなっていた。切り分け方は必ず存在するらしい。確かにどう置いてもできるっぽいが（できない例を構成できない）。テキトーに取っていいわけでもないので難しい。マスの側から見てどのイチゴに属するか決められないかとも考えたがダメ。さて、問題文で与えてくれた「切り分け方が必ず存在する」という情報を利用することを思いつく。両方にイチゴが存在するように2つに切れば小さな問題に帰着できる。ということで、1列ずつ考えれば楽ちんだということに気づいた。この発想出るのが遅いよ！というのはまあ仕方ない。問題文にある情報を使って気づくことができたというのがよかった。これで解けたようなもんだが、最初の列にイチゴがないケースもあり、もちろん最後の列もそうだし、実装がそれなりに重い。出力を文字列と勘違いしていて手間取ったりもした。各列、1個目のイチゴでは番号を変化させず、それ以降はデクリメントする（初期値をKとした）、列が塗り終わったときもデクリメント。イチゴがない列があったら上からコピーする（上に塗った場所があれば）。最後に、下から見ていって塗ってない場所があったら下からコピーする。
これを通して順位表見たらめっちゃ順位低くてびっくりした。あれに気づいてこの実装も間違えないやつがこんなにいるのか。
D - Digit Sum Replace
数というより、文字列を縮めていく問題だと認識する。また、操作で必ず数として小さくなることを確認（和は高々18で1+9も減る）。色々な例を紙の上で試す。しばらくして、各桁の和に注目することを思いつく。9で割ったあまりは変わらないとか、不変量はないかみたいな視点は最初からあったけど、ここでは操作を行ったときの各桁の和と桁数の関係に気づいた。1回の操作では、各桁の和が9減るか桁数が1減るかのどちらかだ。つまり、「各桁の和+桁数*9」という量が9ずつ減っていく。懸念点は、この量だけから1桁であることを判定できるかというところで、紙の上で計算してみると9と10が同じになる。しかしこれは9の倍数かどうかで区別できるということで実装した。が、これは計算ミスで9と10は最初から区別できていた（笑）。実装はかなりシンプルになる。んで、「18以下になったら終わり」という条件はわかっているのに、何を引いてから9で割ればいいのか全然わからない。仕方なく下のような表を書いて10を引けばいいと知る。提出するがWA！けっこう悩んだが、dがc個あるのに単にdを足していた。直してAC。計算ミスが痛かった。WAのペナルティよりも、短時間コンテストでの思考時間のロスが痛い。
8 18 0
9 19 1
10 20 1
E - Majority of Balls
Fは見てない。やるならインタラクティブだろと最初から思っていた。実際面白いけど、たとえ時間があったとしても解けなかっただろうと思える強実装だった。（解法がわかってるときに）すらすらこれを書けるような力があったら競プロもっと楽しいだろうなー。と思いつつ競プロ外のプログラミングでは、知らない実装のきれいな書き方をゆっくり考えるが楽しいので、特に実装力が欲しいとは思ってなかったり（どうせ数学力がネックになることしかない）。
コンテスト中には、碁石を使って考えた。Nが奇数と聞いて「4個ではなく8個だな」と思ってしまった。それは2^3だけど3が奇数なだけで偶数要素しかないんだよなあ。というわけで6個の例を考える。9路盤を8x8のマスとして使うやつ。そのうちの1x6を使う。石があるマスと空のマスどっちが多いか。なるほど奇数だから同じになることがないのね。とりあえず最初は前半N個を選んで一般性を失わない。210回だから198個を1個ずつ決めていってさらにlog(N)くらいは余裕で余るね。O(N)回の前準備はできないけど。んー、1個ずつずらしながら（巡回するものとする）2N回のクエリを出したら何が得られる？Nくらい離れた2つが違っててしかも赤青が入れ替わったときを検出できるだけ。情報量が少ない。情報が得られても2個ずつは扱いが難しそうだ。逆にギリギリのセットがわかってればそこに何か追加することで追加したやつの情報が得られるか。まてよ最初のN個でクエリ出して赤が多かったら後半のN個は青が多いじゃん。その間に必ず入れ替わる場所がある。これまさかの二分探索ライブラリが使えてしまうのか！？二分探索をするプログラムの立場で考えると、FFTTTTTみたいな並びで最初に現れるTを見つけたいわけで、単調になってなかったとしても端っこがF...Tになっていれば見つけたTより右は全部Tだと思ってくれるし、見つけたFより左は全部Fだと思ってくれる。境目の一つを答えとして出力してくれることが保証されそうな気がする。単調性を仮定したコードでこんなことできるのかと驚いた。こういう場所に誘導してくる問題がスゲエ。あとはこれで残り半分を求めて、半分がわかったらそこからギリギリのやつ構成できそうだし、解けてるんじゃ？実装は無限時間かかりそうだけど、って感じだった。今にして思えば、赤と青がちょうど半々のN-1個のセットと1個ずつの赤と青がわかってれば、それ以外のN-1個も半々なんだな。
