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

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

解説

単純な解法として，それぞれの日に対して着る服の選び方をすべて試すという方法が考えられる．しかし，選び方は最大で N^D 通りとなるため，D や N が大きいデータに対しては短時間で答えを求めることができない．

注目すべきは，i 日目までの服の選び方を決めたとき，i + 1 日目以降について服を選んで目的の値を最大化する際には，1 日目から i - 1 日目までの服の選び方は関係ないという点である．「i 日目に服 j を選ぶとしたときの，i 日目までの連続する日に着る服の派手さの差の絶対値の合計」の最大値を f(i, j) とする．すなわち，f(i, j) は，問題の条件および x_i = j を満たすときの |C_x1 - C_x2| + |C_x2 - C_x3| + … + |C_xi-1 - C_xi| の最大値である．すると，f(i + 1, j') は f(i, j) から計算できる： f(i + 1, j') は，f(i, j) + |C_j - C_j'| のうち最大の値となる．このように，サイズの小さい問題から順番に解いていくような手法は，動的計画法と呼ばれている．

この方法によって，計算すべき f(i, j) の値は最大で D × N 個であり，f(i + 1, j') を計算するのに最大 N 通りの j の値を試すので，D × N × N に比例する時間で答えを求めることができる．実装するにあたっては，i 日目の服の候補に j が含まれないときは f(i, j) を参照しない，あるいは十分小さい値に設定しておくとよいだろう．

なお，この問題に対しては，より効率の良い方法が存在する．実は，各日の服の候補のうち，C_j が最大のものまたは最小のものの 2 通りのみを考えればよいことが証明できる．興味のある人は考えてみるとよいだろう．