from ABC174

ABC174E

二分探索だとは気付いて、実装したのだが、微妙なズレを「これは単純な二分探索ではダメなのに違いない」と思い込んで時間を使い切ってしまった

強い人のコードと見比べてみると、僕のコードには2つのバグがあった

どうすれば気づけただろうか

コンテスト中の思考

まず1本の場合を考える

最大値の最小化すると、均等に分割することになる

それぞれの丸太についてk本に分割した場合の長さを求めて、kの和がKになるようにDP…

これは無理

k方向に10^9あるから

ならば逆転の発想で刻む長さの方に注目しよう

自力でこの発想に至ったのはナイス

値域と定義域の交換に似た発想

本数を定義域として長さを値域とする構図を反転させる

刻む長さを定義域として刻まれる本数を値域にする

長さが短くなるほど本数は増える

→二分探索で目的の値を求めることができる

二分探索

left = 1

right = min(AS)

s = sum(a // x - 1 for a in AS)

s >= K

right = min(AS)

誤り

一番短い丸太を切ることなくK回の切断ができる場合がある

right = max(AS)が正しい

この場合切断可能数がゼロになる

left = 1

誤り

長さ1で刻んでもK回に至らないことがある

left = 0にしたが、今思えばこの辺りから少し考察がぬるかった

s = sum(a // x - 1 for a in AS)

誤り

right = max(AS)にしたことで発覚したが、xがaより大きい時にマイナスになってしまう

安易に条件分岐でパッチを当てた

sum(a // x - 1 if a >= x else 0 for a in AS)

誤り

コンテスト終了まで気づかなかったがここが一番のミス

「10からは3を3つ取れる」正しい

「だから最長3の時には10は3分割される、切断数は2」間違い

3.3になってる、切り上げたら4

10の時は3回切る、9の時は2回

これを踏まえると sum((a - 1) // x for a in AS) が正解

この図描けば分かったはずなのに…

s >= K

誤り

切り上げた値を返せという問題条件から、一致する値がない時には右側を返す必要がある

つまり一致する時には、それが右側に入る必要がある

sがK以上の時leftに入れるコードは誤り、s > K が正解

まとめ

二分探索の4つの構成要素をすべて間違えていた、うち2つは自力でコンテスト中に修正できたが、残り2つ残ってる状態で「これは単純な二分探索では解けないに違いない」と考え出して迷走した

二分探索チェックリストにまとめた