ARC100 Equal Cut ~しゃくとりと二分探索~ - Senの競技プログラミング備忘録

前回の続き。

しばらく普通のしゃくとりの例題と実装を説明するので上の問題の解説はしばらく後。

普通のしゃくとり法は、条件を満たす区間の中で最善になる可能性のあるものを、区間の両端を動かすことにより求める。

たとえば、

長さｎの自然数列を与えられる。この中で総和がＳになるような連続する部分列で最小の長さを求めよ

入力：　{1, 2, 3, 4, 5} S = 11

手順

　　　　1 2 3 4 5

1回目 [------]

2回目 [-----------]

3回目 [-----------------]

4回目 [-----------------------]

5回目 [----------------]

6回目 [-----------]

上記の手順により　{3, 4, 5}の長さ3である。

具体的な流れとしては

ずっとループを回す。

右端がオーバーしない上で条件を満たす区間になるまで右端を右へ動かす。(すでに条件を満たしてるのならスルー)

このとき、右端がオーバーする＝条件を満たす区間を作れてないなので、そこでループ脱出させる。

答えの更新。

左端を一つ右へとずらす。

蟻本第二版p.136 ~ 137のままです。

これがノーマルタイプのしゃくとり。

では今回の問題Equal Cutがつかうしゃくとり法を考えよう。

しゃくとり法の大前提は、区間の数個の端が単調にしか変化しないことで、そこからオーダーの次元を一つ落としてる。

ここで、仕切りが3つある場合を考える。真ん中の仕切りを右に一つずらすと、

つまり、区間の端がすべて単調に変化するという条件を満たしてるので、しゃくとり法でオーダーを一つ落とせるのである！

具体的な操作は、

これを、ずっと繰り返せばよい。

ACコード

以上