今回は競プロ典型90問の「001 – Yokan Party」の解法の備忘のために記事を書いています。
かなり遅いですが最近競プロ典型90問を始め、1問目から解説を見ないと解けませんでした。
自身の備忘のためにも、今後解説を見ないと解けなかった問題、解説から知見を得た問題については記事にすることにしました。
問題については上記のリンクを見ていただき、本記事では公式の解説の説明と、自身が提出したコードを載せていきます。
競プロ典型90問の公式解説では、要約となるようなキーワードが付けられています。
今回のキーワードは「答えで二分探索」でした。
今回やりたいのは最短長をスコアとした場合のスコア最大化ですが、解法では以下の2工程に分けて解を導いています。
最小値最大化の問題では同じ解き方ができるらしく、ABC023-D-射撃王などが解けるそうです。
個人ブログの方に実際にACしたコードを載せました。
興味のある方はご覧ください。
【競プロ】競プロ典型90問 – 001 – Yokan Party
入会申込
ログイン
