2008JOI本選3 ダーツ 解説

問題リンク

解説

蟻本にもほぼ同じ問題が載っていることで有名です。 解法の説明はおそらくそちらの方が詳しいので、そちらを参照していただければ良いと思います。

2本の矢を投げて作れる点数を で列挙しソートしたあとに、それらを探索しながら「和が を超えないようにするときの最大値」を二分探索で探します。計算量は です。

このように、二分探索を適用できる場所を見極めるのは上位の問題になってもとても重要な観察です。 難易度6~7の問題で、二分探索を適用することに慣れておきましょう。