計算量は多少多いが問題となるレベルではないし、十分現実的な解法である。最大値と最長値の差」の最小値を求めよ。総和の1/4になるまで数列を伸ばして、超えたらその前後で切るみたいな解法を思いつく。それではサンプルにあるケースがどうにも上手くいかないことに気づき、ここで行き詰まる。次に注目したのが問題文。いわゆるメタ解きというやつ。2つの切り方を全探索する。各パートについて、なるべく2等分するような切断位置を二分探索で探す。先程考えた解法は4つだと上手くいかないが2つなら上手くいくことも証明できる4のでここで実装に移る。求める必要があるが、これは累積和を作っておけば大丈夫。2パターンを考える必要がある。これは二分探索で境界となった値をどっちに入れるかを実際に試せばいい。0;}もう少しキレイに実装したいな〜という感じ。ちなみに上のコードをそのまま投げると通る。確かに実装は重いが、「こどふぉに比べればマシか...」とか思いながら実装していた。バグがほとんど生まれなかったのはこどふぉ様々だろうか。別解というよりこちらがEditorialに載っていた解法なので上が別解なのだが、二分探索の部分は尺取り法で代用できる。いうのも2つに切ったあとでさらに2つに切るとき、切るべき位置は単調性があるため前回切った位置を覚えておけば続きから探索できるからだ。上の方法より僅かだが速い。この問題に限った話ではなく、累積和で境界を探す問題のときはにぶたんと尺取り法がどちらも使えることが多い。分だけ速いが例によって大した問題にはならないので、どちらを使うかはお好みで。前回D500が解けなかった翌週で今回D600と知ったときには死を悟ったが、なんとかなって助かった。欲を言えばE700も解きたかったが、良い解法が浮かばず。パフォは2000乗ったので上々といったところか。それにしても先週は学問と競プロに対するモチベが尋常じゃなく低かった。睡眠不足か、栄養不足か、はたまたストレスか。差が致命的になることはほとんどないので、定数倍程度に思っていい。