読者です 読者をやめる 読者になる 読者になる

hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

ICPC 国内予選 2016 D: ダルマ落とし

AOJ ICPC

昨年歯が立たなかっただけに解けてうれしい。

問題概要

原文を参照してください → Daruma Otoshi | Aizu Online Judge

解説

take[i][j] := 区間 [i, j] のブロックを全て取ることができるか となる bool 型の配列を用意します。まずはこの take 配列に対して、真偽値を正しく入れていきます。

条件より、区間の長さが  2 であるときの判定は容易です。問題はその後でしょう。

次の  2 つの事項を確認することによって、より長い区間についても判定できるようになります。

  • 区間  \left[ i, j \right] のブロックを全て取ることができ、かつ  i-1 番目と  j+1 番目のブロックの重さの差が  1 以下であれば、区間  \left[ i-1, j+1 \right] のブロックを全て取ることができる
  • 区間  \left[ i, k \right] 区間  \left[ k+1, j \right] について、両区間に対して全て取ることができるならば、区間  \left[ i, j \right] のブロックを全て取ることができる

したがって、以下のようにすれば take 配列を正しく構築できます。

  • 区間の長さが短い順に以下を行う
  • 長さが  2 であれば、重さの差が  1 以下であるかを判定して配列を更新する
  • それ以外の長さであれば、より短い区間の結果を使って配列を更新する

この配列を元に答えを出すのですが、これに答えるには以下の補題を解かなければなりません。

 \left[ 1, N \right] の中に、長さが  N 以下の区間がたくさんある。その中から、区間どうしが同じ頂点を被覆しないようにいくつかの区間を選ぶときの、被覆できる頂点数の最大値を求めよ。

これは DP で解くことができます。

dp[i][j] := 区間 [i, j] において被覆できる頂点数の最大値 となるような配列 dp を用意します。

この配列の初期化は各区間を見ることによって行います。例えば 長さ  M区間  \left[ a, b \right] があったとします。 \left[ a, b \right] において被覆できる頂点数の最大値は当然  M なので、dp[a][b] = M が成り立ちます。これを全区間に対して行うことで初期化します。

あとは dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j]) と更新してあげることで正答が得られます (発想としては前述の「より長い区間に対しても判定できる」の箇条書きの  2 つめと一緒です)、 O(N^{3}) パワーを信じましょう。答えになるのは dp[0][N-1] です。

ソースコード

bool take[310][310];
int dp[310][310];

signed main() {
    int n;
    while(cin >> n, n) {
        int w[310];
        rep(i,0,n) cin >> w[i];
        memset(take, false, sizeof(take));
        memset(dp, 0, sizeof(dp));

        rep(i,0,n) {
            rep(j,0,n-i) {
                int len = i+1;
                int s = j, t = j+i;
                rep(k,s,t) {
                    if(take[s][k] && take[k+1][t]) take[s][t] = true;
                }
                if(len == 2) {
                    if(abs(w[s] - w[t]) < 2) {
                        take[s][t] = true;
                    }
                }
                if(take[s][t]) {
                    int x = s-1, y = t+1;
                    while(1) {
                        if(x < 0 || x >= n || y < 0 || y >= n) break;
                        if(abs(w[x] - w[y]) >= 2) break;
                        take[x][y] = true;
                        x--; y++;
                    }
                }
            }
        }

        rep(i,0,n) rep(j,i+1,n) {
            if(take[i][j]) dp[i][j] = j-i+1;
        }

        rep(i,0,n) rep(j,i,n) rep(k,i,j) {
            dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j]);
        }
        cout << dp[0][n-1] << endl;
    }
    return 0;
}

当時は「DP を  2 回やる」みたいなことを呟いている人がたくさんいるのを見て、こんなんできるわけ無いだろうと思っていたけど、今見ると DP を  2 回やる気持ちが確かに分かる。