第9回 日本情報オリンピック本選2：お菓子の分割
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0550
制約
考え方
DPで数え上げする。
dp[i][j][k] := 今 i 番目で A が j 個で、今 k であるときにかかる最小の時間
とする。
切る位置に対してそれぞれ、切る or 切らない の2通りを考えることができる。それぞれのコストを求めて、最終的に min(dp[n][n/2][0], dp[n][n/2][1]) が解になる。ただしメモリ制約上 64 MB までなので dp[10000][5000][2] の配列をもつことができない。DPの更新の際に直前の結果にしか依存しないことがわかると、更新後に更新前の配列の結果を初期化することで配列を使い回すことができるので、制約内に収めることができる。
どこに着目して考察するべきだったか
分割の方法を考えるとつらいので、切る切らないの2通り、全部で (n-1)2 通りの切る方法に着目するべきであった。そう考えるとDPが見えてきて、i 番目までで A が j 個で今 k であるときの最小値を考えることができそう。
そこからさらに制約内に収めるために高速化をするイメージ。
Submission #3697749 - 第９回日本情報オリンピック 本選（オンライン）
何がバグっていたか
得た知見
問題の見方を変えてみる。配列を使いまわして、空間計算量を節約する。
