GCJ2022 1-A C問題「Weightlifting」とDPの考え方

Pocket

1 問題概要
2 考察と解法
3 おわりに
4 コード例
5 共通ウェイトを置きっぱなしにすることの最適性

問題概要

問題ページ：Weightlifting – Code Jam

ウェイトリフティングのトレーニングをします。

$E$ 個のトレーニング項目があり、 $1$ 番目から $E$ 番目まで順番に実行します。

トレーニングに使う重りは $W$ 種類あり、$i$ 番目のトレーニングでは、$j$ 番目の重りを $X_{i,j}$ 個使います。

重りは、下から上へ積み上げる形で組み合わせます。

トレーニングが変わるとき、不要な重りを上からいくつか取り除き、足りない重りを上に追加することで重りの組合せを変えます。

スタックが空の状態からスタートし、すべてのトレーニングを終えて、スタックを空にするまでに必要な「重りを外す回数と追加する回数の和」の最小値を出力してください。

制約

実行時間制限：20秒

テストケースが $T=100$ 個あります。

入出力例は問題ページをご覧ください。

$1\le E\le 100$
$1\le W\le 100$
$1\le X_{i,j}\le 100, (1\le i\le E, 1\le j\le W)$

実行時間制限が 20 秒で、すべての値が $100$ 以下なので、 $T$ を含めて 4 乗くらいは余裕で許容されそうですね。5 乗は厳しそうですかね。定数倍が軽ければいけるかも？

考察と解法

トレーニング内容は最初から全て把握できています。

まず、「すべてのトレーニングに共通するウェイトがある場合、その全てを一番下に置いて、最後まで置き続けるべき」ということが考えられます。正しいんでしょうか。

正しそうな気がする（実際正しい）ので、一旦これを正しいとします。証明はこの記事の最後で考えます。

ということで、すべてのトレーニングに共通するウェイトの集合を最初に一番下に置きます。これらは最後まで外しません。

そうすると、すべてのトレーニングから共通ウェイトを除外して考えることができます。共通ウェイトを除外すると、「すべてのトレーニングに共通するウェイトが無い」という状態になります。これからこの状態で考えます。

すべてのトレーニングに共通するウェイトが無い場合、「必ず途中（最初と最後以外）でスタックが空になる」ということが言えます。なぜなら、これが成り立たない場合、つまり「最後までスタックが空にならない場合」は、一番下のウェイトがすべてのトレーニングで共通してしまっているので「すべてのトレーニングに共通するウェイトが無い」という前提と矛盾します。

この「必ず途中でスタックが空になる」という性質は非常に重要です。

この問題では、最初と最後にはスタックが空になります。

そのため、もし途中でスタックが空になる場所が分かれば「最初から空になる場所まで」と「空になる場所から最後まで」に分割して、元の問題と全く同じ問題（ただしトレーニングの数が少ない）を解いて、その結果を足して全体の問題の答えが計算できるからです。

「元の問題と全く同じ問題を、与えられる入力の一部だけに対して解く」というのは、「部分問題」と呼ばれるもので、DP（動的計画法）を使うための重要な要素です。

問題を分割することができることが分かったので、どうやら DP が使えそうだと考えましょう。

ただ、今考えている解法は面倒な点があります。それは「スタックが途中で空になる」とはいうものの実際には共通ウェイトが残っているということです。つまり実際には「スタックが全体共通ウェイトのみになる」ということなのです。これだとすっきり部分問題になってくれません。

そこで、「スタックが全体共通ウェイトのみになる」場所で、あえてマジでスタックを空にしてみましょう。全体の共通ウェイトを外すのです。しかし、すぐに全体の共通ウェイトを再び置きます。この操作をいれることで、途中でスタックが完全に空になるので、その場所の前後それぞれについて元と同じ問題（最初と最後にスタックを空にする）を解くことができます。

しかし、その操作を入れると、無駄な動作が発生するため最適解より移動回数が大きくなります。

何回多くなるのでしょうか。それは「共通ウェイトの個数×2」になります。共通ウェイト全てを外してまた置くので。

したがって、空にする場所の前後について問題を解いて、それぞれの最小移動回数の和から「共通ウェイトの個数×2」を引いた値が、全体の最適解になります。共通ウェイトを置きっぱなしにすることで、それをつけ外しするコストが削減できるということですね。

立式するため、詳しく整理しましょう。

最初、この問題の $1$ 番目から $E$ 番目までのトレーニング（つまりトレーニング全体）について、ウェイト移動の最小回数を計算しようとしています。

全てのトレーニングに共通するウェイトは最初から最後まで置きっぱなしにしますが、途中で必ず「スタックが共通ウェイトだけになる瞬間」があります。

ここで、神の囁きによって、最適な動かし方では $k$ 番目のトレーニングが終わった段階でスタックが共通ウェイトだけになるのだということが分かったとします。仮にですよ。

このとき、全体の問題の答えは「（$1$ 番目から $k$ 番目までのトレーニングに対する問題の答え）＋（$k+1$ 番目から $E$ 番目までのトレーニングに対する問題の答え）ー2×全体の共通ウェイト数」になります。最後の項は共通ウェイトを最初に置いて最後に外すコストです。

この部分区間に対する問題がすでに解けていれば、その解答を利用することで全体の問題がすぐに解けます。

しかし、実際には神の囁きはありません。スタックが空になる場所が分からない状態でどうやって解くのでしょうか。

考えられる解き方は、「スタックが空になる場所を $1\le k\le E-1$ の範囲で全部試して、すべてのパターンのうち全体問題の解答がもっとも小さくなるものを採用する」というものです。

数式で書くと、以下のようになります。

$$Ans(1,E)=\min_{1\le k\le E-1}(Ans(1,k)+Ans(k+1,E)-2C_{1,E})$$

ただし、$Ans(i,j)$ は $i$ 番目から $j$ 番目までのトレーニングに対する問題の答え（その区間の前と後でスタックを空にするときの最小移動回数）で、$C_{i,j}$ は $i$ 番目から $j$ 番目までの共通ウェイトの個数です。

これは俗に「区間 DP」と呼ばれる形です。

元の問題を解くために、 $Ans(1,k)$ を計算する必要があり、それを計算するために、さらにどこかで分割したときの部分問題を解きます。これを繰り返すと、最終的に長さ 1 の区間に行き着きます。

長さ 1 の区間に対する問題の答えは、明らかにそのトレーニングで使うウェイトの合計個数の 2 倍です。全部置いて全部外すだけですから。この値は、最初に全てのトレーニングに対して計算しておくことで、すぐに（$O(1)$ で）得られます。この前計算は $EW$ 回の計算で実行できます。

また、$i$ 番目から $j$ 番目までの共通ウェイトの個数 $C_{i,j}$ の値は、最初に全ての区間について計算しておくことですぐに参照できます。

この計算は $O(E^2W)$ でできます。区間の個数が $E(E-1)$ 個あり、1 区間に対して区間長×$W$ 回の計算をすると $O(E^3*W)$ になってしまいますが、区間 $[i, j+1]$ の計算をするときに区間 $[i,j]$ の計算に使った値を再利用することでオーダーを落とすことができます。

したがって、以下のように問題を解くことができます。

$$Ans(i,j)=
\begin{cases}
2\sum_{k=1}^W X_{i,k} & (i=j)\\
\min_{i\le k\le j-1}(Ans(i,k)+Ans(k+1,j)-2C_{i,j}) & (i<j)
\end{cases}
$$

一回の区間の計算に対して、$i<j$ の方だと $\min_{i\le k\le j-1}$ の部分で区間長-1 回の計算を行うことになります。$Ans(i,k)+Ans(k+1,j)-2C_{i,j}$ は、すべて計算済みとすれば $O(1)$ で計算できます。メモ化再帰でも、短い区間から順に計算していっても大丈夫です。

区間が $E(E-1)$ 個あるので、全体の計算量は $O(E^3)$ となります。

前計算も合わせると、この問題は $O(E^2(E+W))$ で解くことができ、テストケースが $T$ 個渡されるので、実行時間制限 20 秒以内に $O(TE^2(E+W))$ の計算が完了すれば大丈夫です。これは 4 次ですし定数倍が特別重いということもなさそうなので大丈夫そうですね。

ということで、この問題が解けました。

おわりに

久しぶりに競プロをやったので解説記事を書いてみました。

この問題は、問題の性質を考える中で部分問題に分解できることが分かり、そこから区間 DP の発想に至るという自然な考察の流れで解けるのが面白いですね。

DP で解けそうかどうかをなんとなくで判断している方は、ぜひ「部分問題に分解できるか」という観点で考えてみてください。

以下に AC するコード例と「共通ウェイトを置きっぱなしにすることの最適性の証明」を載せておきます。

コード例

上記の説明では「$i$ 番目から $j$ 番目まで」という閉区間で考えましたが、コーディングしやすさのために下記のコードでは「$i$ 番目から $j$ 番目の手前（$j-1$ 番目）まで」という閉区間で考えています。こうすると余分な $+1$ が発生せず書きやすくなります。

#include <iostream>
#include <vector>

using namespace std;

#define INF 1050000000

int E,W;
vector<int> weight_sum;             // i 番目のトレーニングに使うウェイトの合計個数
vector<vector<int>> common_weight;  // i 番目から j-1 番目までのすべてに共通するウェイトの合計個数
vector<vector<int>> memo;           // i 番目から j-1 番目までの答え

// 区間 [i, j) の答え。メモ化再帰で計算する。
int Ans(int i, int j){
    if(j-i==1){  // 区間の長さが 1 なら 2*ウェイト個数
        return 2 * weight_sum[i];
    }
    if(memo[i][j] != INF){  // メモに値がある場合はそれを出力
        return memo[i][j];
    }

    int ans = IN
    // 全ての分割箇所 k に対して、「[i,k)の答え+[k,j)の答え-2*[i,j)の共通ウェイト個数」を
    // 計算し、その最小値を答えとする
    for(int k = i + 1; k < j; k++){
        ans = min(ans, Ans(i,k) + Ans(k, j) - 2 * common_weight[i][j]);
    }
    return memo[i][j] = ans;
}

int main(void) {
    int T;
    cin>>T;
    for(int t = 0; t < T; t++){
        cin >> E >> W;
        vector<vector<int>> weight(E, vector<int>(W));
        weight_sum = vector<int>(E, 0);
        for(int e = 0; e < E; e++){
            for(int w = 0; w < W; w++){
                int x;
                cin >> x;
                weight[e][w] = x;
                weight_sum[e] += x;
            }
        }

        // 全区間に対して、区間内の共通ウェイトを前計算
        common_weight = vector<vector<int>>(E, vector<int>(E + 1, 0));
        for(int i = 0; i < E; i++){
            vector<int> min_num(W, INF);
            for(int j = i + 1; j < E + 1; j++){
                for(int w = 0; w < W; w++){
                    min_num[w] = min(min_num[w], weight[j - 1][w]);
                    common_weight[i][j] += min_num[w];
                }
            }
        }

        memo = vector<vector<int>>(E, vector<int>(E + 1, INF));
        int ans = Ans(0, E);
        cout << "Case #" << t + 1 << ": ";
        cout << ans << endl;
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

#define INF 1050000000

int E,W;

vector<int> weight_sum; // i 番目のトレーニングに使うウェイトの合計個数

vector<vector<int>> common_weight; // i 番目から j-1 番目までのすべてに共通するウェイトの合計個数

vector<vector<int>> memo; // i 番目から j-1 番目までの答え

// 区間 [i, j) の答え。メモ化再帰で計算する。

int Ans(int i, int j){

if(j-i==1){ // 区間の長さが 1 なら 2*ウェイト個数

return 2 * weight_sum[i];

}

if(memo[i][j] != INF){ // メモに値がある場合はそれを出力

return memo[i][j];

}

int ans = IN

// 全ての分割箇所 k に対して、「[i,k)の答え+[k,j)の答え-2*[i,j)の共通ウェイト個数」を

// 計算し、その最小値を答えとする

for(int k = i + 1; k < j; k++){

ans = min(ans, Ans(i,k) + Ans(k, j) - 2 * common_weight[i][j]);

}

return memo[i][j] = ans;

}

int main(void) {

int T;

cin>>T;

for(int t = 0; t < T; t++){

cin >> E >> W;

vector<vector<int>> weight(E, vector<int>(W));

weight_sum = vector<int>(E, 0);

for(int e = 0; e < E; e++){

for(int w = 0; w < W; w++){

int x;

cin >> x;

weight[e][w] = x;

weight_sum[e] += x;

}

// 全区間に対して、区間内の共通ウェイトを前計算

common_weight = vector<vector<int>>(E, vector<int>(E + 1, 0));

for(int i = 0; i < E; i++){

vector<int> min_num(W, INF);

for(int j = i + 1; j < E + 1; j++){

for(int w = 0; w < W; w++){

min_num[w] = min(min_num[w], weight[j - 1][w]);

common_weight[i][j] += min_num[w];

}

memo = vector<vector<int>>(E, vector<int>(E + 1, INF));

int ans = Ans(0, E);

cout << "Case #" << t + 1 << ": ";

cout << ans << endl;

}

return 0;

}

共通ウェイトを置きっぱなしにすることの最適性

全てのトレーニングに共通するウェイトの個数を $C$ とし、それらを除外したときの最小移動回数を $N$ とします。

このとき、共通ウェイトを最初から最後まで置きっぱなしにすることで、元の問題について $N+2C$ 回の移動で目的を達成することができます。

ここで、実は元の問題に $N+2C$ よりも少ない移動回数で目的を達成する移動手順があったとします。この回数を $M$ としましょう。$M<N+2C$ です。

その手順を再現する動きの中で、「共通ウェイトに属するウェイトを置く」または「共通ウェイトに属するウェイトを外す」という動作を無視すると、共通ウェイトを除外した問題に対する移動手順の一つを実現できます。

ここで、$M$ 回の移動のうち、共通ウェイトに属するウェイトを動かす動作は必ず $2C$ 回以上含まれています。なぜなら共通ウェイトの全てが必ず一度は置かれ、最後には外されているからです。

したがって、共通ウェイトを除外した問題を $M-2C$ 回の移動で達成することができました。

ただし、$M<N+2C$ なので、$M-2C<N$ です。これは、共通ウェイトを除外したときの最小移動回数が $N$ であることに矛盾します。

したがって、元の問題を $N+2C$ 未満の移動回数で達成することは不可能であり、また、共通ウェイトを置きっぱなしにすることで $N+2C$ 回の移動で達成できることが分かっているので、この方法で $N+2C$ 回の移動をするのが最小移動回数となることが示されました。

Pocket