第14回日本情報オリンピック　予選４

2014年12月14日
情報オリンピック日本委員会

解説

単純な解法として，JOI 君の移動方法をすべて試して疲労度の合計を最小にするものを探すといったものが考えられる．しかし，JOI 君は最大で M 日間使えることを考えると，待機する日の選び方は M 日の中から M - N 日を選ぶ方法程度はあると言える．このような選ぶ組み合わせの数は M, N が大きくなるに従って爆発的に増大してしまうので，この単純な解法では時間内に大きな入力データに対して答えを得ることは難しい．

そこで重要なのは，JOI 君が都市 i にいて，それまでに j 回の行動をした (j 日間が経過した) 状態について，そこから先の移動方法を考えるにあたってそれ以前の移動方法は関係ないという事実である．「JOI 君が j 日間かけて都市 i に至るときに溜まる疲労度の合計の最小値」を f(i, j) とすれば，求める答えは f(N, N), f(N, N+1), ..., f(N, M) のうちの最小値となる．

f(i, j) を求める方法を考えよう．JOI 君が最後にとった行動について考えると以下のようになる．

• JOI 君が最後に「移動」をしていた場合，前日に JOI 君は都市 i - 1 におり，この移動で疲労度が D_i × C_j だけ溜まる．
• JOI 君が最後に「待機」をしていた場合，前日にも JOI 君は都市 i におり，疲労度の合計は変化していない．

ゆえに，f(i, j) は f(i - 1, j - 1) + D_i × C_j (JOI 君が最後に「移動」をしていた場合) と f(i, j - 1) (JOI 君が最後に「待機」をしていた場合) のうち小さい方である．ただし，初日に関しては前日の行動が存在しないので f(0, 0) = 0 と決められる．

これより，f(0, 0) が決まっていて，それ以外の f(i, j) の値は f(i - 1, j) と f(i - 1, j - 1) の値から決まることがわかるので，i の小さい方から f(i, j) の値を順に求めていくことが可能である．(i, j) の値は約 M × N 通り (厳密にはもう少し小さい) あり，ひとつの f(i, j) の計算は 2 通りの値を見るだけでよいから，全体で M × N に比例する時間で f の値をすべて計算することが可能である．この手法を用いれば，すべての入力データに対して高速に答えを得ることができる．

上に用いた手法のように，より小さい問題 (この場合は日数や都市数が小さい問題) の答えから，より大きい問題の答えを順に計算していく手法は一般に動的計画法と呼ばれている．情報オリンピックでは過去にも動的計画法を用いる問題を出題しているので，さまざまなタイプの動的計画法を知るために過去の問題やその解説を参照するのもよいだろう．