ACM-ICPC 2016 Asia Tsukuba Regional 国内予選, D 解答

D: ダルマ落とし

問題

長さnの数列aが与えられる。次の操作を好きなだけ繰り返す。

  • 数列の任意の隣り合う2数を一つ選び、その差の絶対値が1以下ならばその2数を数列から取り除き、数列は詰めて長さが2短くする

最大で幾つ取り除くことができるか。

制約

テストケース <= 50
n <= 300

解法

区間DP。以下、左閉右開区間[i, j) i以上j未満の区間を使って説明する。

dp[i][j] := 区間[i, j)の数列に対して、この区間だけで取り除くことができる最大の個数

とする。重要なのはdp[i][j]を計算するのには、その外側の区間は全く関係無いということ。

dp[i][j]とdp[j][k]がわかっているとすると、この区間を並べて[i, k)が考えられる。 つまり

for j in { i+1 <= j <= k-1 }:
    dp[i][k] は dp[i][j] + dp[j][k] 以上

dp[i][k]が2つに分けることができないパターンとして、 A[i]とA[k-1]を同時に取り除く場合がある。
ただし、[i+1, k-1)が全て取り除くことができないなら、A[i], A[k-1]のペアを取り除くことはできない。

if |A[i] - A[k-1]| <= 1 and dp[i+1][k-1] == k-i-2:
    dp[i][k] = k - i

取り除き方はこれで全て列挙されている。このことから、[i, k)を計算するにはその間の小さい区間が全て計算されていればいい。
これを区間DPと呼ぶ、わかりにくいなら再帰関数で書けばいい。
三重ループで書くと

for l in 1 .. n:
    for i in 1 .. n:
        for j in i .. i+l:
	    dp[i][i+l] は dp[i][j] + dp[j][i+l] 以上
	    ...

のように、外側から、長さ・左端のインデックス・中間のインデックスとできる。速さを意識するなら、2次配列の1番目のインデックスのループをなるべく外側にするとよい。

for i in n-1 .. 0:
    for j in i+1 .. n:
        for k in j+1 .. k:
	    dp[i][k] は dp[i][j] + dp[j][k] 以上
	    ...

コード

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }

int N, W[311];
int dp[311][311];


int main() {

    while (scanf("%d", &N), N) {
	REP (i, N) scanf("%d", W + i);
	memset(dp, 0, sizeof dp);

	for (int i=N-1; i>=0; i--) {
	    dp[i][i] = 0;
	    dp[i][i+1] = 0;
	    for (int j=i+1; j<=N; j++) {
		if (i + 1 < j && abs(W[i] - W[j-1]) <= 1 && dp[i+1][j-1] == j-i-2)
		    dp[i][j] = j - i;

		for (int k=j+1; k<=N; k++)
		    amax(dp[i][k], dp[i][j] + dp[j][k]);
	    }
	}

	printf("%d\n", dp[0][N]);
    }

    return 0;
}

日記

この辺りから高校数学の知識だけでは難しくなる。メモリを潤沢に使うことで性能の高いアルゴリズムを得る。