3完。前半しか解けてないけど面白かった。自分が早解きできないのは面白くないが、レーティングの意味では（微減で済んでいるので）どうでもいい。ここまで簡単でこんなに時間かかるというのがすごい。実装も手間取るところがあり、明らかに楽な実装なのに普段のABCやその他趣味のプログラミングではやらない種類の実装なのが気持ちいい。今週は競プロモチベゼロだったけど、思い出させてくれた。とてもよかった。
A - Gold and Silver
苦手なやつ。安いときに買って高いときに売るってみんな言うけど感覚としてわからない。紙に書いて色々考えたが全然見えない。金で始まって金で終わる必要があるのが難しい。「Road to Millionaire」で学んだことを思い出し、毎回全て金に替えることにする。翌日の金の量を最大化すればよい（翌日が終わったときに金で持っているか銀で持っているかは翌日考えればいい）。そうなると、今日と明日の交換レートを比較するだけだ。明日金の価値が下がるなら銀で持っているのがよい。これで各日にどちらで持つのがいいかわかったので、前日と違うなら1を出力する。どちらで持つかの01列をxorで変換して答えの01列にする実装が好き。
B - Balls of Three Colors
不変量を考えたくなるけど、ボールが減るわけではないので難しそう。色に意味はない。しばらく眺めて何も見えない。とりあえず最短距離は置いといて、2つの個数を一致させてそれを全部残った1つの色にすることを考える。ここで、2つの個数の差は3の倍数ずつしか変化しないので差が3の倍数でないときは不可能だと気づく。ということで実装はとりあえず、ソートしてnext_permutation。前の2つを一致させる。最初2つめのが大きい（または同じ）とする。気になるのは、一直線に一致させに行くと個数が負になってしまうケース。足りないところを増やすようにすれば手数は増えるが一致させることはできる。時間もないので実装から入る。もちろん愚直にやる時間はないが、必要なぶんをまとめて合わせていく感じにすればlogくらいにはなる気はする。しかし、その実装を詰めていくと、負になる心配があるのは最終的にその色だけにしたいやつなので増やして損しないことに気づいた。つまり、残す色を決めたらそれ以外の2つの差が3の倍数でないなら不可能、3の倍数なら2つのうち多いほうの個数が答え。1回の操作で1個しか減らせないのでそれだけの回数がかかるし、3の倍数の差が0になるのに必要な回数だけそっちに振り分けて順番を適切に決めればちゃんと1色になる。差は1回に3ずつ縮まるので元の個数より必要な回数のが少なくなるし、減らし続ける対象以外の2個の和は増え続けるので負にならないように操作するのも簡単。実装しているうちに、なんとなくの解法が証明付きの解法に化けて鋭く面白かった。
C - Max Dot
Mの制限がない場合を考える。後ろから見てxの値はどこかからは（そこより後ろは）ずっと同じになりそう。しかしA_iが小さくなればそこからは変化しないかと言えば、A=(5, 1, 1, 2, 2, 2, 2, 2, 2) みたいのだと後半でxを大きくしたくなる。しばらくして、後ろから何個かをでかい値にしてそれ以外は0にするのが最適っぽいと気づく。これは簡単に計算できそう（累積和を使う）。xに中途半端な値は要らなくて、なぜなら間に半端なのがあったらそこのA_iが後半部分のAの平均を上げるならマックスまで引き上げたほうがいいし、そうでないなら0にして損しない。さて、Mの制限がある場合はどうか。制限なしで計算してMを超えたならその区間はMにしていいよなあとか思いながら、どうもはっきりしない。しばらくして、今さらながらNが5000だったことを思い出す。0と0以上M以下とMの3つの区間に分けるのを全探索するだけやん。まず、Mにする区間だけで和がSを超えたらアウト。Sピッタリなら残りは全部0。そうでないとき、真ん中の区間の幅が0でなければ残りを分配する。分配した結果Mを超えたのもアウト。判定は全部整数でできて、スコア計算はdouble。構成する必要がないので、誤差は考えなくていい。0, i, j, n で区間を作っていたが、添え字を勘違いしたり区間の幅で割ってxを求めるところで混乱したりで時間がかかった。簡単そうに見えて慣れない実装だった。
D - Neq Neq
操作するとだんだん同じ数が連続するようになって操作できなくなる。連続する同じ数があったらそこは分断されているので独立に考えてよさそう。手で実験すると、思ったより自由に残すものを選べる。
時間がないので、解くつもりで考える状態にはなかなかなれなかった。それでもコンテスト中の思考は貴重なのでギリギリまで考える。撤退の目安として、解けそうになっていない状態で残り時間が1分・3分・5分などがあるが、精神状態がよければ疲れていても残り1分までは考える（残り5分で撤退するのはコンテストで相当嫌な目に遭ってやさぐれてるとき）。今回は、提出時に（雑ではあるが）証明できていたのが気持ちよさにつながっていた気がする（そうでないと時間かかったことを気にしてそう）。
