きろく

特筆すべき記録のまとめ

yukicoder:No.818 Dinner time

問題

yukicoder.me

解法

まず,ニワトリ i が k 回食料として利用されるとき,ニワトリ i - 1 は必ず k 回以上利用されなければならない.そうでなければ,問題のルールに反してしまう.

次に,各ニワトリに分けて考える.各ニワトリについて食料として利用する回数 k を全通り決めて計算していては O(NM) となり間に合わないので,k の候補を減らしたいことを考える.ここで,各ニワトリに対して行う動作は「何もしない」,「1回だけ利用する」,「M 回利用する」の3つに絞ることが出来る.こうすると,DP の遷移が O(1) となり,全体でも O(N) で計算することが可能となる.実装上は明らかに M 日分の食事が用意できないようなパターン(最初のニワトリを 0, 1 回しか使わないときなど)をはじく必要がある.

解答

yukicoder.me

f:id:babcs2035:20190420203443p:plain