ABC 401-500/ABC444C - AtCoder Riko - 競技プログラミング用 知識集積所

---

問題

ABC444C

必要知識

B以下レベルの内容は省略

• 考察問題
• 貪欲法（アルゴリズム系）※

考え方

「ある長さLであった可能性があるか？」は、以下の貪欲法※で解ける。

• まず、そもそも長さL以上のものがあれば、不可能
• 長さがLのものは、折れなかったものとして取り除く
• 残りの中で最も長いものと最も短いものの長さの和がLであればそれらを取り除く、を何もなくなるまでループさせられれば可能

ということで、可能性のある長さを全て列挙したとき、候補数が少なければそれらを全探索※すればよい。
そして、その候補は、よく考えてみると「最大の長さ」「最大の長さ+最小の長さ」の2つだけである。
というのも、

• 折れなかったものがあるなら、それは長さが最大のもの以外ありえない
• 全部折れたのなら、前述のチェックの1セット目に全部統一されるしかありえない

からである。

解答例

解答例

注意点

別解