(競プロ)abc023 D問題
今日から
というリポジトリの問題を使って典型問題のとき方に触れつつ、類題で具体的なコードまで理解するということをします。ABCのD問題の難易度も多々あり、90問あるので終わったら自力回答が多少できるようになっているのでは??
D問題概要
射撃王です。
とき方
github.com こちらのリポジトリの1つめの解説を参考にすると、考え方の概要がわかります。 ざっくりかくと「できる/できないの境界がある場合のスコアの最大/最小値」を求める場合、できるかできないかで二分探索をする(スコアk+1は可能だが、スコアkは無理、という値kを見つければ良い。)です。
今回の問題だと
- スコアXに対して二分探索をして、どこまでがとける問題かを探る
- 1つずつが可能かどうかは風船ごとにどれくらいのスピードで割らなければいけないかを考えて、次の1秒で割らなければいけないものが複数になったらとけない問題とすることにする(貪欲法で境界値を探る)
という流れになると思います。
コードに落とし込む
ときかたとしては
こちらの記事が参考になりました。
pythonのコードは
ほぼこれを写経して、今回の二分探索の中で判定をしていくという流れを理解しました。
お気持ち
1周目はとにかくハードルを低く、CとD問題をまず読もうと思っていますが、自力実装までの溝が大きくて心が折れそうです。そういうのも含めて継続できるようブログに記していくぞ。