Codeforces Round #204 (Div. 1) C. Jeff and Brackets

問題

解法

Darsein さんの解法を参考にしました。

方針としては, dp[m][l][r] = (m 個の n 文字で作ったカッコを並べた時, regular bracket sequence にするために左側に "(" を l 個つける必要があって, 右側に ")" を r 個つける必要があるようなもののうち, コストが最小のもの) という dp を行列累乗で解く感じです。

これがわかれば答えは dp[m][0][0] ですね。

まず, dp[1][l][r] が知りたいですが, これは n 文字のカッコの並びを bit で全探索すれば良いです。
適当にカッコを並べた時, regular bracket sequence にするために左側に "(" をつける個数は, diff[i] = (i 番目まで見た時点での, 右カッコと左カッコの差)の最大値として求められます。同様に ")" をつける個数もやります。

あとは行列累乗パートです。
左側につけるカッコ文字列の状態が [a][b] となっていて(左側に "(" をつける個数は a, 右側に ")" をつける個数は b), 右側につけるカッコ文字列の状態が [c][d] となっているようなものを結合させたいとします。
このとき, b-c >= 0 ならば, 結合させた文字列では真ん中部分に左カッコが b-c 個過剰にあるので, 結局全体としては [a][d+b-c] という状態になります。同様に c-b >= 0 ならば全体としては [a+c-b][d] という状態になります。

よって, これらの組み合わせでコスト最小のものを求めれば良いです。

ただ, これだと行列のサイズがかなり大きくなる可能性があります。しかし, 行列のサイズは 2*n だけあれば十分です。これは, 左カッコと右カッコは結局同じ個数ないといけないことから言えます。

typedef long long number;
typedef vector<number> vec;
typedef vector<vec> matrix;

const ll INF = 1ll<<55;

// O( n )
matrix identity(int n) {
    matrix A(n, vec(n));
    for (int i = 0; i < n; ++i) A[i][i] = 1;
    return A;
}
// O( n^3 )
matrix mul(const matrix &A, const matrix &B) {
    matrix C(A.size(), vec(B[0].size(), INF));
    int n = A.size();
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) for (int l = 0; l < n; l++) {
            if (j-k >= 0) {
                if (l+j-k < n) C[i][l+j-k] = min(C[i][l+j-k], A[i][j] + B[k][l]);
            } else {
                if (i+k-j < n) C[i+k-j][l] = min(C[i+k-j][l], A[i][j] + B[k][l]);
            }
        }
    }
    return C;
}
// O( n^3 log e )
matrix pow(const matrix &A, ll e) {
    if (e == 0) return identity(A.size());
    if (e == 1) return A;
    if (e % 2 == 0) {
        matrix tmp = pow(A, e/2);
        return mul(tmp, tmp);
    } else {
        matrix tmp = pow(A, e-1);
        return mul(A, tmp);
    }
}

int n, m;
const int MAXN = 22;
int a[MAXN], b[MAXN];
int dp[MAXN][MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    matrix T(2*n, vec(2*n, INF));
    for (int s = 0; s < (1<<n); s++) {
        int k = 0, l = 0, r = 0;
        ll cost = 0;
        for (int i = 0; i < n; i++) {
            if ((s>>i)&1) {
                cost += a[i];
                k--;
            } else {
                cost += b[i];
                k++;
            }
            l = max(l, k);
        }
        k = 0;
        for (int i = n-1; i >= 0; i--) {
            if ((s>>i)&1) k++;
            else k--;
            r = max(r, k);
        }
        T[l][r] = min(T[l][r], cost);
    }
    cout << pow(T, m)[0][0] << endl;
    return 0;
}

mayoko’s diary

プロコンとかいろいろ。

Codeforces Round #204 (Div. 1) C. Jeff and Brackets

問題

解法