問題 atcoder.jp 解法 最終的に選んだものは、小さい方から取っていくのが最適だと証明可能. ということで、最小の値 X を固定したらそこから貪欲に取れば良い. 「X 未満の値は取れない ⇔ X未満の値を跨ぐような区間を選べない」 ゆえに X 未満の値がある場…

問題 atcoder.jp 解法 dpをする. i 番目のコインが有り余ってたら i + 1 番目のコインとして見なすことで、i 番目のコインを 0 ~ max(a[ i ] + 下からの傘増し, 9) しかないと思っても良い. 各ステップ i で下から傘増しされるコインの種類数はそんなに多く…