| 第22回日本情報オリンピック 二次予選 |
|
|
2022年12月13日
情報オリンピック日本委員会
|
解説担当：星井智仁
この問題は実行時間制限がやや厳しいため，Python などの実行速度が遅い言語ではこの解説のアルゴリズムをそのまま実装しても満点が得られないかもしれません．
小課題 1 では，駅に置かれている貨物の価値 Ai がすべて 1 であり， かつ列車に詰める荷物の最大値 W も 1 です．
このとき，Ai がすべて等しいので， 駅 1 に近い駅の貨物を優先して輸送するのが明らかに最適です．
駅 i の貨物を駅 1 に輸送するためには， 往復するのに距離 (i-1) × 2 だけ列車が走行する必要があります．
駅 2, 3, …, k の貨物を駅 1 に輸送するために列車が走行する距離は， Σi=2,…,k { (i-1) × 2 } = (2-1) × 2 + (3-1) × 2 + … + (k-1) × 2 です． この値が D 以下となる最大の整数 k を求めると，k-1 が答えとなります． （制約より，Σi=2,…,N { (i-1) × 2 } = N2 - N ≧ D なので k の上限 N を気にする必要はありません．）
方程式を解いて計算量 O(1) で解いたり， 二分探索を用いて計算量 O(log N) で解くこともできますが， 愚直にループを回して計算量 O(N) で解いても実行時間制限には問題なく間に合うでしょう．
小課題 2 では，小課題 1 と同様に貨物の価値 Ai がすべて 1 ですが， W に特別な制約がかかっているわけではありません．
Ai がすべて等しいので， 駅 1 に近い駅の貨物を優先して輸送するのが最適ですが， 複数の貨物を列車に積むことができるため，どのように列車を走行させるのが最適か考察する必要があります．
駅 2, 3, …, k の貨物を駅 1 に輸送することを考えましょう．このとき，以下のように列車を運行させるのが最適です．
以上のような輸送方法ができる k の最大値を調べればよいです．
これを愚直に実装すると計算量は O(N2) でしょうか． もっと工夫して計算量を削減することはできますが，計算量 O(N2) でも十分実行時間制限には間に合うでしょう．
解説の都合上，先に小課題 4 について説明します．
小課題 4 では，駅の数 N が 15 以下です．N が小さいため，bit 全探索という手法を用いることができます．
bit 全探索とは，ある集合の大きさを M としたとき， その集合の部分集合 2M 通りすべてについて調べ上げるという手法です．
どの駅の貨物を駅 1 に輸送するか，というのは 2N-1 通りあります． この 2N-1 通りの中の，輸送可能な選び方のうち貨物の価値の合計が最大となるものが答えです．
輸送可能か否かは，小課題 2 と同様の方法で距離を計算することができます．
例えば，W=2 で，駅 2，3，5，7，11 の貨物を選んだとき，以下のように列車を運行させるのが最適です．
なお，小課題 1，2 と異なり，各駅に置かれている貨物の価値 A がすべて同じ値というわけではありませんが，途中駅で貨物を降ろすことを考える必要はありません．
なぜなら，選んだ貨物は必ず駅 1 まで輸送しなければならず，選ばなかった貨物はそもそも列車に積む必要がありません．なので，貨物を途中駅で降ろしたり，積み替えたりするメリットはありません．
この方法により，計算量 O(N × 2N) で解くことができます．
小課題 3 では，列車に積める貨物の数の最大値 W が 1 です．小課題 4 の説明で既に述べたように，途中駅で貨物を降ろすメリットはありません．そのため，各駅に置かれている貨物について独立に考えることができます．
これはナップサック問題に帰着できます．ナップサック問題とは，動的計画法 という手法で解くことができることが知られている，非常に有名な問題です．
ナップサック問題の形に書き換えると，以下のような問題になります．（ナップサック問題にはいくつかバリエーションがあります．ここでは，同じ種類の品物を 2 つ以上選ぶことを許していません．許すものもあります．）
これは以下のように動的計画法を用いて解くことができます．
二次元配列を用意します．ここでは，この配列の名前を dp とします．
dp[i][j] := 品物 2，3，…， i について，それぞれナップサックに入れるか否か決め，
その重さの合計が j であるときのナップサックに入れられる価値の最大値（存在しない時は -∞）
と定義します．
このとき，漸化式は dp[i][j] = max( dp[i-1][j],dp[i-1][j-(i-1) × 2] + Ai ) です．
初期値として dp[1][0]=0，dp[k][l]=-∞（(k,l) ≠ (1,0)）を設定し，i，j が小さい方から順々にこの漸化式を計算して dp[i][j] を求めていくと二次元配列 dp の各値が求まります．
そうして求めた dp[N][0]，dp[N][1]，…，dp[N][D] の最大値が答えとなります． 計算量は O(ND) です．D ≦ N2-N なので，計算量は O(N3) です．
制約は駅の数 N ≦ 50 のみです．W に特別な制約はかかっていません．
小課題 3，4 と同様に，いくつかの駅に置いてある貨物を選び，選んだ貨物のみを駅 1 に運ぶことを考えます．
小課題 3 では 品物 2（駅 2 の貨物），品物 3（駅 3 の貨物），…，品物 N（駅 N の貨物） と，駅 1 に近い方から順番にそれぞれの品物（貨物）を選ぶか選ばないか決めていましたが，逆に，駅 N の貨物，駅 N-1 の貨物，…，駅 2 の貨物という順番で選ぶか選ばないかを考えることにします．動的計画法に落とし込めないか考えると，以下のような漸化式が立ちます．
dp[i][j][k] := 駅 i，駅 i+1，…，駅 N の貨物を選ぶか選ばないか決めたとき，ここまでに選んだ貨物の数が j であり，列車の総走行距離が k であるときの貨物の価値の合計の最大値
と定義します．
漸化式は以下のようになります．
初期値として，dp[N+1][0][0]=0，dp[l][m][n]=-∞（(l,m,n) ≠ (N+1,0,0)）を設定し， i が大きい方， j，k が小さい方からこの漸化式を順々に計算して dp[i][j][k] を求めていくと三次元配列 dp の各値が求まります．
そうして求めた dp[2][0][0]，dp[2][0][1]，…，dp[2][0][N-1]，dp[2][1][0]，…，dp[2][1][N-1]，…，dp[2][D][0]，…，dp[2][D][N-1] の最大値が答えとなります． 計算量は O(N2 D) です．D ≦ N2 - N なので，計算量は O(N4) です．
小課題 5 の解法を改善することで満点を得ることができます．
小課題 5 では
dp[i][j][k] := 駅 i，駅 i+1，…，駅 N の貨物を選ぶか選ばないか決めたとき，ここまでに選んだ貨物の数が j であり，列車の総走行距離が k であるときの貨物の価値の合計の最大値
として漸化式を立てました．
まず，j の値の範囲を狭めることができます．「ここまでに選んだ貨物の数」ではなく「ここまでに選んだ貨物の数を W で割った余り」としても問題ありません．漸化式は以下のようになります．
ここで，t = W-1 (j = 0のとき)，j-1 (j ≠ 0のとき) とします．
このときの計算量は O(NWD) です． 一見改善されているように見えますが，W ≦ N-1，D ≦ N2-N なので計算量は O(N4) のまま変わりません．
しかし，よく考えてみましょう．D は総走行距離の上限として与えられていますが，すべての貨物を駅 1 に輸送するために走行しなければならない総距離の最小値は本当に N2 - N なのでしょうか？
W=1 のとき，小課題 1 の説明に書いたように，上限は Σi=2,…,N { (i-1) × 2 } = N2 - N です．
しかし，W=N-1 のときはどうでしょうか．列車は駅 1 と駅 N を 1 往復するだけですべての貨物を駅 1 に輸送することができます． つまり，W=N-1 のときは (N-1) × 2 が実質的な D の上限なのです．
W が大きくなればなるほど実質的な D の上限は小さくなります．具体的には，
D の実質的な上限 Dmax=(N-1) × 2 + (N-W-1) × 2 + (N-2W-1) ×2 + … ≒ N2/W となります．（これは雑な見積もりなので上限値を N2/W としたプログラムを提出すると不正解になります．プログラム上で (N-1) × 2 + (N-W-1) × 2 +(N-2W-1) × 2 + … を計算しましょう．）
D の値が Dmax 以上のとき，A_2 + A_3 + … + A_N を出力，そうでないとき動的計画法を行う，とすると，計算量は O(NWDmax) です．O(Dmax) = O(N2/W) なので，O(NWDmax)=O(N^3) となり満点を得ることができます．