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つ残ってる状態で「これは単純な二分探索では解けないに違いない」と考え出して迷走した
- 二分探索チェックリストにまとめた
