ken_math https://blog.hatena.ne.jp/ken_math/ 強くなりたい https://well-defined.hatenadiary.com/ 典型90問 競プロ 簡単な解法を自分用にメモしておこうと思います。 001 - Yokan Party（★4） 答えに単調性があるので二分探索を考えます。 答えを決め打ちしての二分探索です。具体的には答えはM以上か？ということを考えます。 仮にK回以上分割してスコアSが得られたとします。このときK回より多く分割していることからより少ない回数で分割すればS以上のスコアが達成できます。 M以上のスコアが取れるかを考える→長さがM以上になったら切断することを考える→得られるスコアはS(>=M)→切断回数がK回以上ならよりS以上(つまりM以上)のスコアが達成できる この判定を二分探索で繰り返します。 AC 002 - E… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fwell-defined.hatenadiary.com%2Fentry%2F2022%2F05%2F16%2F174732" title="典型90問 まとめ 001～010 - 強くなりたい" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2022-05-16 17:47:32 rich https://well-defined.hatenadiary.com/entry/2022/05/16/174732 1.0 100%