スコアを与えられた数以上にできるかどうかの判定法について。（注意：説明がくどい）

問題と解説

問題はこちら→https://atcoder.jp/contests/typical90/tasks/typical90_a

出題者による解説はこちら（添付画像左）↓

【2 日目】
昨日の解説と今日の典型問題です。問題 001 については E869120 の想定ソースコードも GitHub に追加しました。今日は昨日と比較すると少し易しい問題だと思います。（昨日と同様、入力形式・入出力例は GitHub を参照のこと） #競プロ典型90問 pic.twitter.com/ewcAKEKEP1
— E869120@公開アカウント (@e869120) 2021年3月30日

解法のポイント

与えられた整数 $M$ に対して、「スコアを $M$ 以上にできるか？」は簡単に判定できる

二分探索は知っていたが、この事実に気付けなかったために解けなかった。逆にこれに気付きさえすれば、「 $M$ を動かして調べればいい」→「全範囲を調べると間に合わない」→「二分探索を使おう」という発想に至るのは難しくないと思う。しかしながら、解答を読んでも上記の問いに対する判定法の正しさをすぐには理解できなかった。そこで、以下ではその判定法について詳しく考察する。（二分探索については解説しない。）

判定のしかた

解答のステップ2にある通りだが、改めて説明する。

切れ目を左から見ていく。
最後に切ったところ（一度も切っていないときは左端）からの距離が初めて $M$ 以上になったらその切れ目で切る。これを繰り返す。
ただし、次の条件をいずれかを満たす場合はそれ以上切らずに繰り返しをやめる。
- 切れ目の右端まで見終わった。
- もし今見ている切れ目を切ると、右側の残った部分の長さが $M$ 未満になる。
トータルで切った回数が $K$ 以上ならスコアを $M$ 以上にできる。 $K$ 未満ならできない。

この判定法を「判定法A」と呼ぶことにする。

例

下の図に示すようなようかんがあるとする。縦線は切れ目を表し、切れ目と切れ目の間の数字はそれらの間の距離を表す。

f:id:sitorasu_today:20210508202617p:plain

このようかんを $4$ 回切って $5$ つのピースに分けることを考える。このとき、スコアを $3$ 以上にできるか？は次のようにして判定できる。

f:id:sitorasu_today:20210508182207p:plain

では、スコアを $6$ 以上にはできるだろうか？

f:id:sitorasu_today:20210508183339p:plain

一番右の切れ目は切らないことに注意してほしい。

判定法の正しさ

なるほど、判定のしかた自体は分かった。でもどうしてこの方法で正しく判定できるのだろう？先ほどの例で考えてみよう。ようかんを $4$ 回切って $5$ つのピースに分けるとき、スコアを $3$ 以上にはできるのだった。

この理由を説明するのは簡単だ。 $5$ 回切ったうちの $1$ 回を切らないようにすれば、スコアを $3$ 以上にする切り方のひとつが構成できる。同様に、 $5$ 回切ったうちの何回かを切らないようにすることで、 $5$ 回以下の任意の回数切ってスコアを $3$ 以上にする方法が構成できる。一般に、与えられた整数 $M$ に対して、判定法Aで $X$ 回切ることができたならば、 $X$ 回以下の任意の回数切ってスコアを $M$ 以上にできる。

問題は、 $X$ 回より多く切ってスコアを $M$ 以上にする方法が本当に存在しないのかということである。言い換えれば、 $X$ はスコア $M$ 以上になるように切れる最大の回数なのかということだ。もしそうであれば判定法Aは正しい。しかし、判定法Aはパッと見ではすべての切り方を考慮しつくしているようには思えない。例えば先ほどの結果によれば、 $4$ 回切ってスコアを $6$ 以上にする方法は存在しないのであった。

果たして本当にそうだろうか？違う切り方を試してみよう。例えば、最初に切る位置を少し左にずらしてみる。

f:id:sitorasu_today:20210508183914p:plain

これは全然ダメだ。今切り出したピースの長さが $6$ 未満なので、この時点でスコアが $6$ 未満になってしまうことが確定する。それでは、今度は最初に切る位置を少し右にずらしてみよう。

f:id:sitorasu_today:20210508183937p:plain

このように切っても、スコア $6$ 以上を保って切れる最大回数は増えそうにない。なぜならば、判定法Aで最初に切った段階よりも残り少ないようかんを、より多く切らなければならないからである。たとえるなら、テスト用紙の小さな記名欄に、自分の名前の一文字目を大きく書いてしまったような状況だ。でも実際の状況はもう少し複雑だ。今回の問題設定では切れ目の位置が決まっているし、それらが均等に配置されているとも限らないからだ。もう少しちゃんと考えることにする。

任意のようかんと切れ目と整数 $M$ が与えられたとする。判定法Aにしたがって最初の一回を切った後、残りをスコアが $M$ 以上になるように切る方法のうち、切れる最大の回数を $S$ とする。また、最初の一回を判定法Aより右側で切り、残りをスコアが $M$ 以上になるように切る方法のうち、切れる最大の回数を $S'$ とする。

f:id:sitorasu_today:20210508193045p:plain

このとき、 $S \geq S'$ である。なぜなら、もし仮に $S \lt S'$ であるとすると、判定法Aにしたがって最初の一回を切った後、残りをスコアが $M$ 以上になるように $S'(\gt S)$ 回切ることができるからである（下図参照）。これは $S$ が最大であることに矛盾する。

f:id:sitorasu_today:20210508193113p:plain

したがって、一回目を判定法A以外の方法で切ってもトータルで切れる最大回数は増えないことがわかる。つまり、最初の一回は判定法Aにしたがうのが最善である。これにより、ようかん全体をスコアが $M$ 以上になるようにできるだけたくさん切る問題は、最初の一回を判定法Aにしたがって切り、残りをできるだけたくさん切るという、より小さな問題に帰着できる。さらに、この理屈は残りのようかんに対して繰り返し適用できる。つまり、残りのようかんを改めてようかん全体だとみなすことで、残りをできるだけたくさん切るという問題は、残りを判定法Aにしたがって一回切り、それでもなお残った部分をできるだけたくさん切るというさらに小さな問題に帰着できる（下図参照）。これを繰り返すことで元の問題は自明な問題に帰着され、最大回数を求めることができる。これは判定法Aそのものである。

f:id:sitorasu_today:20210508195103p:plain