ARC100

100だけど今回は特にお祭り感なし。30分早い開始は非常に珍しく、調子が狂う。

C - Linear Approximation

A_iからiを引いてしまえば昨日のB問題みたいになる。あー、B問題やっときゃよかったかと一瞬思ったが、これはたぶん単に真ん中（より大きいやつとより小さいやつの個数が同じなら少し動かしても変わらない）でよい。奇数個と偶数個の例でn/2でいいことを確認。極値のとこが平らじゃないこともあるのでしっかり選ぶ。ソートしてその値を取得。当時は中央値という言葉は頭になかったと思う。nth_elementのほうがたぶん速いがまあソートでいいでしょ。

D - Equal Cut

入力がCと同じなのが良い。なるべく均等に4つに分ける。4つって多いなあ。問題文をながめながら何か降ってくるのを待ったが何もない。順番を変えることはできないんだな。とりあえず2個に分けることを考えてみる。ちょうど真ん中くらいで切りたい。累積和を持っておけば、その区間の和はわかるし、その半分を超えたところが二分探索でわかる。超えたところか、その直前のどちらかが答え。じゃあ3つだったら？3つを2つと1つに分けて、その切る位置を変化させていく。1つのほうは狭義単調減少、2つのほうの最小値は広義単調増加。グラフを描くと三分探索で行ける気も（注:今考えると何言ってんだかわからない）。仮に三分探索で行けるなら、残りの分け方をN通り試してO(N(logN)^2)で解けるが。しかし平らなところがあるので三分探索ダメそうな気もする。うーん。
真ん中で分けたら？2つと2つに分ける位置をN通り試す。2つに分けるのは二分探索でできたはず。ていうかこの形ならしゃくとりでlog外せるじゃんと気づいた。なんか話がうますぎる。でも真ん中の境目を先に決めるのは問題ないし、左の2つを均等に分けることは最大値を小さくするし最小値を大きくするのでデメリットがない。これでいいっぽい。じゃあ実装するだけだ。右側と左側があるので関数を作ってreverseで2回実行する。もうしゃくとりに苦手意識はほとんどないが、今回の実装は重い。幅2から幅NまでのN-1個からなるvectorを返す。それもintのvectorじゃダメで差の絶対値と最大値と最小値、あ、差の絶対値は要らないか、それを返すためにarray<int, 2>のvectorにする（intはllにする必要があり1WA）。足してみて行き過ぎだったら戻して決定という処理がややこしい。幅2から幅Nまでを配列にどう格納するのが自然かもわからない。色々なことがあって、自分の能力で余裕を持って処理できず、ミスが出る。最小値の更新を忘れていてサンプルが通らずけっこう悩んだ。