d_tutuz https://blog.hatena.ne.jp/d_tutuz/ 数学/競プロメモ https://tutuz.hateblo.jp/ 二分探索 累積和 3つに分ける 問題 https://beta.atcoder.jp/contests/abc102/tasks/arc100_b 数列 a_n から 3 点を選択して、数列を連続する 4 つの部分列に分解する。各部分列の総和を P, Q, R, S とする。 | max(P, Q, R, S) - min(P, Q, R, S) | の最小値を求めよ。 制約 4 <= N <= 2 * 105 1 <= a_i <= 109 考え方 全探索＋二分探索の組み合わせ。解を求めるためには、a_n を 3 点を選んで区切る必要があるが、これは真ん中を固定するとうまくいく。まず真ん中で 2 つに分けた後、それぞれをさ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftutuz.hateblo.jp%2Fentry%2F2018%2F07%2F21%2F175435" title="ABC102-D：Equal Cut(600) - 数学/競プロメモ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=a_i Hatena Blog https://hatena.blog 2018-07-21 17:54:35 rich https://tutuz.hateblo.jp/entry/2018/07/21/175435 1.0 100%