165分かけてABの2完。Cは、Bをやっている合間に読むだけ読んだ。ABはAGCらしいいい問題だった。コンテスト中はどうしても「いい結果を出したい」「悪い順位になりたくない」という気持ちに邪魔されてしまうところはあるが、それでもこのAを考えるのは楽しさが上回る。コンテスト中なら当然ながらネタバレの可能性がない、その状態で考えることができるのはAGCに参加した人の特権だ。考えることはたっぷりあって、"結果的に"実装は軽くなる。一時期全然AGCを楽しめなかったけど、ここ半年くらい自分の好みの出題傾向になってきてて嬉しい。これを楽しめる状態に今の自分があることは本当に幸せだと思う。
ただそれだけに悔しい。内容的にこのパフォーマンス値は納得の結果であり、悔しい。あと単純にレーティング単調減少はつらい。
A - >< again
最初から良い数列で、それを分解してその全部が良い数列である必要がある。その特殊な状況をまず認識する。次に考えるのは、例えば3増える場所があったとして、それをいくつかに分解したら増分3を分け合う必要があるということ。つまり、kは隣り合う数の差の絶対値の最小値でありそうな雰囲気がある（少なくともそれより大きくはならない）。
ここからが難しい。つかみどころがない。かなり早い段階からB問題と交互に考えていたが、なんだかんだ考えるのが楽しくてA問題にかける時間が長かった。なんか微分してから分けてそこから復元みたいなことをしようと思った。とりあえず増減を見て 1, 2, 1, 0, 1 のようなミニマムな変化をk-1個作って分解してみる（最小が0になるよう調整する）。それでいいだろうと思って書いたのだが、提出する前に念のため確認したら間違っていた。10 0 3 10 7 4 1 5 という数列を与えると残りが負数を含む数列になってしまう。
やっぱ微分は下限0があるので微妙なんだよな。もっと均等に分けたい。都合のいいことを考えて、単にkで割ってという方針を探ってみたが、当たりだった。これは最初から多少は浮かんでいたのだけど、さすがに一発でそれを選ぶのは無理。そもそも非負実数列でよければ単にkで割るだけ。整数だから上限kがあるのだけど、差の絶対値がk以上なのでkで割っても1以上の差を残せそうだ。A_i % k よりも番号が若い数列のi番目の要素それぞれにあまりのぶんの1を足す。差がkなら（あまりがあっても）ちょうど1の差になるし、kより大きければ差が増えるほうにしか働かない（っぽいとしか確認してなかったけど）。
最初は、正しいか不安な（実際間違っている）方法しか浮かばなかったのに、気づいてしまえばきれいな実装でばちっと決まる。すごい問題だ。
B - Taking the middle
横に伸びた数の列を真ん中で折って（真ん中を支点にして両端を）上に立てると、高橋君が好きな数を取って青木君がもう片方の列の一番下の数を取るという操作になる。これはすぐに思いついた。しかしここからが何も進展しない。ゲームでよくある後ろから考えるというのもできない（最後にどのカードが残るかわからないので）。高橋君の選び方で状況が全然違ってきてしまう。何か貪欲がありそうな気もするが、全然わからない。詰まったらDPだけどさすがに何もまとまらない（同一視できるものをまとめるのがDPという文脈）。
一番下の2つについて、高橋君は片方しか取れない。そこをもう少し拡張して2段目までの4つの数について考えてみると、高橋君がそのうちの3つを取ることはできないみたいだ。そこから類推して、i段目まで見てi個より多くは取れないしi個以下なら取れると予想される。確かに、選びたい数を上から選んでいけば達成できそう。半分より多く取るのもなんか埋まっちゃいそうだよね。で、それを達成するためのアルゴリズムが思い浮かばない。想定解ではなさそうと思いつつ、まず貪欲に大きいN個に印を付け下から見ていって半分を超えるなら次に大きいものへ印を移動させる複雑なコードを実装。途中簡単な実装方針がないかたまに考えるも何も出ず。
サンプルが合って提出したがWA。反例がなかなか浮かばなかった。さっき別の実装を少し考えて棄却したときに描いた図を見てWAの原因がわかった。大きい順に選んでいってその位置から見て半分を超えたか判定するのは簡単だが、その位置で超えてなくてもより上の位置から見て半分を超えることもあるのだ。印を移動させるのは、自分より下も含めた最小のものにしないと少なくともダメだ。最小値を持ってそのように修正しようとするが、最小値を使ったら2番目に小さいものを持ってこないといけない。これは困った。でも困ったことで「この困る感覚はpriority_queueだ」と思うことができた。難しいコードを書かなくても、priority_queueに全部突っ込んで、あふれたぶんは使えないので半分になるまで捨ててというのを繰り返すだけ。最後に残ったN個の和が答え。ACはしたけど、めちゃくちゃ時間かかった。ここははっきりとした力不足を感じた。
