(AOJ0625) JOI2015/2016本選-1:オレンジの出荷

なんかAOJ-JOIの難易度6(AOJ/AtCoder-JOI)で難しいという声があり、実際苦戦したので記事にしてみた。

問題

A - オレンジの出荷 (Oranges)
有志の方の尽力によってAtCoder上で問題が見れるようになって嬉しい。ありがとうございます。

考察・解法

　こういうのを見ると、 $i$ 個目のオレンジを $j$ 個めの箱に入れたときに...みたいな感じでdpをしたくなりがち(僕だけ？)だが、それではうまくいかない。よく考えると、箱に関するコストは一定だから、箱を何個使ったかみたいな情報は必要ない。それよりも、箱に入れるオレンジの数、大きさの最大値・最小値という値がコストに関わる方が厄介である。ここで、「ひとつの箱には連続した番号のオレンジしか詰めることができない」という文言に注目しよう。これは、ある箱に詰めるオレンジの集合は区間をなすことを意味する。そしてその区間の長さ、その区間に含まれる値の最大値・最小値が問題になると言っているので、「全体をいくつかの区間を分割する」タイプのdpが相性がよさそうだ。
　 $dp_i$ : $i$ 番目のオレンジまで詰めたときのコストの最小値　とする。そして $0 \leq j \leq M-1$ を満たす $j$ について、区間 $[i-j,i]$ を同じ箱に詰めると考えて遷移を行う。この遷移は $j$ の小さい順に行えば、 $a,b$ の値を順次更新していくことができるので、 $i$ への遷移を $O(M)$ で行える。全体の計算量は $O(NM)$ となり、十分高速である。

実装

Submission #4243568 - 第１５回日本情報オリンピック本選（オンライン）
実装は軽いと思う。dp2とか書いたのは試行錯誤の跡...。