JOI2017/2018 予選 D - 水ようかん (Mizuyokan)
解法
番目までのようかんを切り終えて、ピースの最小値が
になるように切り分けたときに取り得る"ピースの最大値"の最小値
とします。こうすることで、答えはで求めることができます。
すると、でピースを作成すると仮定した際に遷移がどうなるかを考えればよいため、
として、
と考えたくなります。初期値はです。
しかし、このままではおそらくACすることはできません(参考)
以下のようなケースを考えます。
2 10 1
これは、サンプル2のようかんを左右反転させただけなので、明らかに答えは9です。
しかし、上のままの解法だと、おそらく答えが合わないかと思います。
この原因は、上のDP解が左端のようかんが最小値になる場合のみについて考えていることによるものです。
このケースのように、右端が最小のピースになったり、3つ以上に切り分けたうちの真ん中が最小になるケースも存在します。
これを解消するために、DPの定義を少し書き換えます。
最後まで切り分けた結果、ピースの最小値が
番目までのようかんを切り終えたときに取り得る"ピースの最大値"の最小値
すると、遷移はそのまま、初期値はとすることで、このDPを計算できます。
答えも最初と同様で求めることができます。が、仮定と矛盾する場合、つまりピースの最小値が
以上となる切り分け方が存在しなかった場合は排除しなければなりません。この場合は、
になっているため、容易に場合分けをして排除することができます。
切り分け方は存在するが、ピースの最小値がぴったりにならないものも存在します。が、今回は
以上、という仮定を置いているので、
ぴったりにならない場合は、
以降のどこかでぴったりになるはずです。
は、
が大きい方が値が小さくなるので、
によって問題なく最小値を取り出すことができます。
