ABC174E
https://gyazo.com/d918641f069655a20c15816f05aa0133
from ABC174
ABC174E
https://gyazo.com/1a24dd1ea8f7b2400d189a120215cb44
E - Logs
二分探索だとは気付いて、実装したのだが、微妙なズレを「これは単純な二分探索ではダメなのに違いない」と思い込んで時間を使い切ってしまった
強い人のコードと見比べてみると、僕のコードには2つのバグがあった
どうすれば気づけただろうか
コンテスト中の思考
https://gyazo.com/4eb43b6ef20a3f75aa8708896d8b7c2d
まず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)
誤り
コンテスト終了まで気づかなかったがここが一番のミス
https://gyazo.com/9b66f0994c8a6d7bc7e22ed4396fb528
「10からは3を3つ取れる」正しい
「だから最長3の時には10は3分割される、切断数は2」間違い
3.3になってる、切り上げたら4
10の時は3回切る、9の時は2回
これを踏まえると sum((a - 1) // x for a in AS) が正解
この図描けば分かったはずなのに…
s >= K
誤り
https://gyazo.com/d918641f069655a20c15816f05aa0133
切り上げた値を返せという問題条件から、一致する値がない時には右側を返す必要がある
つまり一致する時には、それが右側に入る必要がある
sがK以上の時leftに入れるコードは誤り、s > K が正解
まとめ
二分探索の4つの構成要素をすべて間違えていた、うち2つは自力でコンテスト中に修正できたが、残り2つ残ってる状態で「これは単純な二分探索では解けないに違いない」と考え出して迷走した
二分探索チェックリストにまとめた