ぴよまるの雑多な技術所

間違えて休職中ってずっと書いていて心配されていました。全部ちょっとずつ齧って好きって思える技術を見つけたい。研究分野は数理最適化。

(競プロ)abc023 D問題

今日から

GitHub - E869120/kyopro_educational_90: 2021/3/30 ~ 2021/7/12 に行われる企画「競プロ典型 90 問」の問題・解説・ソースコードなどの資料をアップロードしています。

というリポジトリの問題を使って典型問題のとき方に触れつつ、類題で具体的なコードまで理解するということをします。ABCのD問題の難易度も多々あり、90問あるので終わったら自力回答が多少できるようになっているのでは??

D問題概要

射撃王です。

とき方

github.com こちらのリポジトリの1つめの解説を参考にすると、考え方の概要がわかります。 ざっくりかくと「できる/できないの境界がある場合のスコアの最大/最小値」を求める場合、できるかできないかで二分探索をする(スコアk+1は可能だが、スコアkは無理、という値kを見つければ良い。)です。

今回の問題だと

  • スコアXに対して二分探索をして、どこまでがとける問題かを探る
  • 1つずつが可能かどうかは風船ごとにどれくらいのスピードで割らなければいけないかを考えて、次の1秒で割らなければいけないものが複数になったらとけない問題とすることにする(貪欲法で境界値を探る)

という流れになると思います。

コードに落とし込む

ときかたとしては

scrapbox.io

こちらの記事が参考になりました。

pythonのコードは

note.com

ほぼこれを写経して、今回の二分探索の中で判定をしていくという流れを理解しました。

お気持ち

1周目はとにかくハードルを低く、CとD問題をまず読もうと思っていますが、自力実装までの溝が大きくて心が折れそうです。そういうのも含めて継続できるようブログに記していくぞ。