TopCoder SRM 718 Div1 Easy (Div2 Med): InterleavingParenthesis

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

括弧列 と が与えられる。

に の各文字を、 の文字間の相対位置関係を変えずに挿入することを考える。このとき、 valid な括弧列になるパターンは何通りあるか？ただし、文字として同じであっても、もともと の文字であったか の文字であったかは区別される。

解説

まず、ここでいう valid な括弧列 とは、'(' を と、 ')' を と見たとき、以下と同値です。

• 全要素の総和が
• 先頭からの累積和が一度も負にならない

したがって、 の累積和と の累積和の和を取った時に でなければ、どう並べても valid な括弧列は作れません。

さて、 の 文字目、 の 文字目までを既に使用したとしましょう。この後の文字を適切に並べることで valid な括弧列を作れるかどうかの判定は、累積和が非負であるかどうかで可能です。

先ほどの状態から つ進んだ状態、すなわち または から新たに 文字使うことを考えましょう。ここでの valid な括弧列判定も、やはり累積和で行えます。

ここまで来ると の 文字目、 の 文字目までを使用したときの valid になる可能性のある括弧列の総数 という DP が構成でき、 で解くことができます。

ソースコード

class InterleavingParenthesis {
    public:
    int sum1[2510], sum2[2510];
    int dp[2510][2510];
    int d1[2] = {1, 0};
    int d2[2] = {0, 1};
    int countWays(string s1, string s2) {
        int N = s1.length(), M = s2.length();
        memset(sum1, 0, sizeof(sum1));
        memset(sum2, 0, sizeof(sum2));
        for(int i=0; i<N; i++) {
            sum1[i+1] = sum1[i] + (s1[i] == '(' ? 1 : -1);
        }
        for(int i=0; i<M; i++) {
            sum2[i+1] = sum2[i] + (s2[i] == '(' ? 1 : -1);
        }
        if(sum1[N] + sum2[M] != 0) return 0;

        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for(int i=0; i<=N; i++) {
            for(int j=0; j<=M; j++) {
                int cur_sum = sum1[i] + sum2[j];
                if(cur_sum < 0) continue;

                for(int k=0; k<2; k++) {
                    int ni = i + d1[k], nj = j + d2[k];
                    if(ni > N || nj > M) continue;
                    int nxt_sum = sum1[ni] + sum2[nj];
                    if(nxt_sum < 0) continue;
                    (dp[ni][nj] += dp[i][j]) %= MOD;
                }
            }
        }
        return dp[N][M];
    }
};

蟻本練習問題解説 Part3 (2-3)

蟻本練習問題の解説をします。今回のトピックは動的計画法です！

今回は難易度が割と混在しているため、水色 〜 青 の方でも解きごたえがある (ありそう、完全に主観) な問題に★をつけました。競技プログラミングにある程度慣れている方も、★がついている問題を解くことをオススメします。

シリーズ目次はこちらからどうぞ。

tsutaj.hatenablog.com

TopCoder SRM 719 Div1 Easy (Div2 Med): LongMansion

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

行無限列のマス目がある。 行目のマスを踏むとき、どの列においてもコストが かかる。

から まで移動するとき、コスト和の最小値を求めよ。

解説

横方向に移動するとき、複数の行を利用するメリットはありません (途中でどこかの行に移動するほうが得である場合は、最初からより得になる行にいたほうが良いため、結局 つの行しか使いません)。なので、どの行を利用して横方向に移動するかを全探索すればよいです。

横方向の移動に 行目を利用するとき、 という移動経路を取るため、コストを計算するにはこの つをそれぞれ計算すれば良いです。累積和を用いると になりますが、 が小さいので愚直にやっても通ります。

ソースコード

class LongMansionDiv1 {
    public:
    int sum[60];
    long long minimalTime(vector<int> t, int sX, int sY, int eX, int eY) {
        int N = t.size();
        for(int i=0; i<N; i++) {
            sum[i+1] += sum[i] + t[i];
        }

        long long int ans = INF;
        for(int i=0; i<N; i++) {
            long long int tmp = 0;
            // sX -> i
            int mi = min(i, sX), ma = max(i, sX) + 1;
            tmp += sum[ma] - sum[mi];

            // y
            long long int width = abs(sY - eY);
            tmp += width * t[i];

            // i -> eX
            mi = min(i, eX), ma = max(i, eX) + 1;
            tmp += sum[ma] - sum[mi] - t[i];
            ans = min(ans, tmp);
        }
        return ans;
    }
};