TopCoder SRM 727 Div2 Hard: ManageSubsequences

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

文字列 が与えられる。 に対して、部分列として を含むが は含まないように、いくつか文字を挿入したい。この条件を満たす文字挿入個数の最小値を求めよ。不可能な場合は を出力せよ。

解説

いったん のことは無視して、 に文字をいくつか追加して を部分列として含むにはどうすればよいかを考えることにしましょう。これは要するに LCS とほぼ同じで、「 の 文字目までを使って の 文字目までを含むようにするために必要な文字挿入個数の最小」を解けば良いことになります。状態遷移としては、 の次の文字を普通に入れるか、 の 文字目に相当する文字を挿入する パターンがありますので、次のような DP になります。

const int INF = 1 << 25;
int dp[310][310];
int main() {
    string S, A; cin >> S >> A;
    int len_s = S.length(), len_a = A.length();
    for(int i=0; i<=len_s; i++) {
        fill(dp[i], dp[i]+len_a+1, INF);
    }
    dp[0][0] = 0;
    for(int i=0; i<=len_s; i++) {
        for(int j=0; j<=len_a; j++) {
            // insert S[i]
            if(i < len_s) {
                int nxt_s = i+1;
                int nxt_a = j + (j < len_a && S[i] == A[j]);
                dp[nxt_s][nxt_a] = min(dp[nxt_s][nxt_a], dp[i][j]);
            }

            // insert A[j]
            if(j < len_a) {
                int nxt_s = i + (i < len_s && A[j] == S[i]);
                int nxt_a = j+1;
                dp[nxt_s][nxt_a] = min(dp[nxt_s][nxt_a], dp[i][j] + 1);
            }
        }
    }
    cout << dp[len_s][len_a] << endl;
    return 0;
}

ここに が増えても同様で、要するに が最後まで一致する前に と について最後まで一致すれば良いということになります。よって、 の DP で解くことができます。

ソースコード

int dp[2][310][310];
class ManageSubsequences {
    public:
    int minAdded(string S, string A, string B) {
        int len_s = S.length();
        int len_a = A.length();
        int len_b = B.length();

        for(int i=0; i<2; i++) {
            for(int j=0; j<=len_a; j++) {
                for(int k=0; k<=len_b; k++) {
                    dp[i][j][k] = INF;
                }
            }
        }
        dp[0][0][0] = 0;

        for(int i=0; i<=len_s; i++) {
            int cur = i % 2, nxt = cur ^ 1;
            for(int j=0; j<=len_a; j++) {
                for(int k=0; k<len_b; k++) {
                    // insert S[i]
                    if(i < len_s) {
                        int nxt_a = j + (j < len_a && S[i] == A[j]);
                        int nxt_b = k + (k < len_b && S[i] == B[k]);
                        chmin(dp[nxt][nxt_a][nxt_b], dp[cur][j][k]);
                    }

                    // insert A[j]
                    if(j < len_a) {
                        int nxt_mo = (cur + (i < len_s && A[j] == S[i])) % 2;
                        int nxt_b  = k + (k < len_b && A[j] == B[k]);
                        chmin(dp[nxt_mo][j+1][nxt_b], dp[cur][j][k] + 1);
                    }

                    if(i != len_s) dp[cur][j][k] = INF;
                }
            }
        }

        int ans = INF;
        for(int k=0; k<len_b; k++) chmin(ans, dp[len_s%2][len_a][k]);
        return (ans == INF ? -1 : ans);
    }
};

TopCoder SRM 728 Div1 Easy: Halving

するめうめ

tsutaj.hatenablog.com

問題概要

自然数が 個与えられる。各数字 に対して、次の操作を何度でも行える。

• が偶数のとき、その数字を に変える。
• が奇数のとき、その数字を か のどちらかに変える。

操作を何回か行い、 個全てが同じ数字になるようにしたい。これを実現するために必要な操作回数の最小値を求めよ。

解説

ある数字 に対してこの操作をするとき、その状態数は 程度なので、全て列挙することができます。

あとは、ある状態を持ってきたときに全ての要素においてその状態になりえるかをチェックして、最小を求めればよいです。

ソースコード

class Halving {
    public:
    map<int, int> mp[110];
    int minSteps(vector<int> a) {
        int N = a.size();
        for(int i=0; i<N; i++) {
            mp[i].clear();
            queue<int> que;
            mp[i][a[i]] = 0, que.push(a[i]);

            while(que.size()) {
                int cur = que.front(); que.pop();
                vector<int> x;
                if(cur % 2 == 0) {
                    x.push_back(cur / 2);
                }
                else {
                    x.push_back((cur-1) / 2);
                    x.push_back((cur+1) / 2);
                }
                    
                for(auto nxt : x) {
                    if(mp[i].count(nxt)) continue;
                    mp[i][nxt] = mp[i][cur] + 1, que.push(nxt);
                }
            }
        }

        int ans = INF;
        for(auto x : mp[0]) {
            int tmp = 0, val = x.first;
            for(int i=0; i<N; i++) {
                if(mp[i].count(val)) tmp += mp[i][val];
                else tmp = INF;
            }
            ans = min(ans, tmp);
        }
        return ans;
    }
};

状態数が少ないことを見抜くまでに時間がかかって、かなり手間取りました・・・

TopCoder SRM 728 Div2 Hard: TrisomorphismEasy

するめうめ

問題概要

原文 → TopCoder Statistics - Problem Statement

頂点の有向グラフがあり、各頂点はそれぞれ から までの番号でラベル付けされている。

ある つの頂点を選び、ラベルをローテーションするという操作を何回か行い、元のグラフのラベリングを変更する。

これによってできる、元のグラフと異なる unique なグラフは何通りあるか。

解説

回の操作は長さ の巡回置換です。

と、 つの互換の積で表せることから、これは偶置換です。偶置換を何回か適用したものもまた偶置換なので、結局「元の順列に対して、全ての偶置換を適用することを考えれば良い」ことがわかります。実際に が小さいため、全て試すことができます。

さて、ある順列 に対して、その転倒数の偶奇は置換の偶奇に等しいという重要な性質があります。つまり、順列を試すときはその転倒数を調べ、それが奇数であれば無視する必要があります。

あとは unique なグラフの調べ方ですが、「頂点 から出ている辺が につながっている」という情報が一つでも異なれば unique です。したがって、各頂点についてどこにつながっているかを見て、それを適当に hash にして管理すればよいです。

ソースコード

class TrisomorphismEasy {
    public:
    int count(vector<int> edgeTo) {
        int N = edgeTo.size();
        vector<ll> pw(N, 1), trans(N);
        iota(trans.begin(), trans.end(), 0);

        for(int i=1; i<N; i++) {
            pw[i] = pw[i-1] * 10;
        }

        unordered_set<ll> S;
        do {
            bool rev = false;
            for(int i=0; i<N; i++) {
                for(int j=i+1; j<N; j++) {
                    if(trans[i] > trans[j]) rev ^= 1;
                }
            }
            if(rev) continue;

            ll hash = 0;
            for(int i=0; i<N; i++) {
                hash += pw[ trans[i] ] * trans[ edgeTo[i] ];
            }
            S.insert(hash);
        }while(next_permutation(trans.begin(), trans.end()));

        return (int)S.size() - 1;
    }
};

個人的には、かなり苦手なタイプの問題でした・・・