一般社団法人 全国個人事業主支援協会

COLUMN コラム

まえがき

今回は競プロ典型90問の「001 – Yokan Party」の解法の備忘のために記事を書いています。
かなり遅いですが最近競プロ典型90問を始め、1問目から解説を見ないと解けませんでした。
自身の備忘のためにも、今後解説を見ないと解けなかった問題、解説から知見を得た問題については記事にすることにしました。

問題については上記のリンクを見ていただき、本記事では公式の解説の説明と、自身が提出したコードを載せていきます。

解法の解説

競プロ典型90問の公式解説では、要約となるようなキーワードが付けられています。
今回のキーワードは「答えで二分探索」でした。

今回やりたいのは最短長をスコアとした場合のスコア最大化ですが、解法では以下の2工程に分けて解を導いています。

  1. スコアがx以上になる切り方が存在するか判定するロジックを実装
  2. 1を使用してスコアの最大値を二分探索

最小値最大化の問題では同じ解き方ができるらしく、ABC023-D-射撃王などが解けるそうです。

提出コード

個人ブログの方に実際にACしたコードを載せました。
興味のある方はご覧ください。
【競プロ】競プロ典型90問 – 001 – Yokan Party

The following two tabs change content below.

神谷 全俊

2018年からフリーランスのシステムエンジニアになりました。 出身は沖縄県で、プロフィール画像も沖縄で撮った写真です。 個人ブログも書いており、こちらにはそこでの記事の一部を載せる予定です。

最新記事 by 神谷 全俊 (全て見る)

この記事をシェアする

  • Twitterでシェア
  • Facebookでシェア
  • LINEでシェア