[競プロ典型90問] 001 - Yokan Party（★4）

[shimopino]

リンク

• [Twitter] 問題リンク
• [AtCoder] 問題リンク
• [公式AC] C++

着想

解答時

今回の問題の最適解は、長さLの物体をK等分に切断することである。

そこでK等分した際の位置から、実際のN個の切れ目の位置に最も近いものを選択していけば解けると考えた。

しかし、1個1個端から順番に実行していくと、最初に選択した切り口の影響で後続の切り口の最適箇所が変化してしまうため、すべてを同時に計算する必要があったが、その方法がわからなかった。

公式解説

ポイントは、「スコアを x 以上にすることができるのか」という問いを「切断されてできる K+1 個のようかんの長さをすべて x 以上とすることができるのか」と言い換えることである。

この問題は2分探索と貪欲法を組み合わせることで解くことができる。

1. 2分探索
   • ようかんの長さを0以上、L以下の中から探索していく
     • スコアを mid 以上にすることが可能である -> left
     • 不可能である -> right
   • 計算量は O(log(L))
2. 貪欲法
   • 探索対象の長さで、ようかんを切断できるのか検証する
   • 計算量は O(N)

全体の計算量は O(Nlog(L)) となる。

ACコード

• 解説をコードに落としたもの

その他

類題はコメントに追加する

[shimopino]

類題

• AtCoder Beginner Contest 023 D - 射撃王
• Square869120Contest #5 B - Emblem
• AtCoder Regular Contest 101 D - Median of Medians

[shimopino]

似たような系統の問題で 平均最大化 がある。