TopCoder SRM 715 Div1 Med: ClassicTowers

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

ハノイの塔をアレンジしたゲームを考える。

つの棒に、左から 個、 個、 個のディスクが刺さっている (ハノイの塔と同じように、大きさは相異なる)。これらのディスクをハノイの塔と同じルールで、どれか つの棒に全てまとめたい。この最短手順が ステップであるとき、それぞれのディスクについて、はじめはどの棒にあれば良いかを求めよ (答えが複数ある場合はどれを出力しても良い)。状況としてこれがあり得ない場合は、例外を出力せよ。

解説

Writer の解説 (Topcoder SRM 715 - Codeforces) を読んだのですが、理解に数時間かかったので忘れないように残しておきます。

まず有名な事実として、 段からなる (通常の) ハノイの塔を解くために必要な最小手数は 手です。よって、これを超える数であれば弾いてよいです。

それぞれのディスクの初期位置が決定しているものとして、数が大きいディスクから順に、最終状態にするために何手が必要になるかを考えることにしましょう。便宜上、最終的に全てのディスクを棒 に置きたいとします。

大きさ のディスクを に置くことを考えます。すでに に置かれていれば、当然動かす必要が無いため、手数は増えません。そうでなければ、操作が必要になります。

さて、 番目のディスクを に動かすには、どのような条件が必要でしょうか？ いま、大きさ のディスクが ではない棒 にあるとすると (こう仮定しても一般性を失いません)、 でも でもない棒、すなわち棒 に 未満のディスクが全て配置されている 必要があります。

具体的にこれはどういうことでしょうか？まず、大きい方から確定させているため、 より大きいディスクは全て棒 に位置します。そして、今動かしたいのは に位置する大きさ のディスクです。このとき、 未満のディスクが全て棒 に位置していないと、大きさ のディスクを に移動させることができません。そのため、上の条件が必要になります。

のディスクを に移動させるには 手必要です。また、 未満のディスクを に全て置いた状態から、それらを に移す手数は です (0-indexed の場合)。よって、大きさ のディスクを目標としている棒に入れるために、合計で 手が必要になることが分かります。

さて、 未満のディスクについては棒 にいてほしいことが分かりましたが、本当に に位置しているかどうかによって必要な手数が変わります。・・・ここで、先ほどの議論を再帰的に適用することによって、この手数を計算することができます (さきほどまでは「棒 に置きたい」という気持ちのもとで進んでいたものが、今度は「棒 に置きたい」という気持ちのもとで進むことに注意します)

必要な情報は 「既にそれぞれ 個のディスクが置かれている状態で、次のディスクを棒 に置きたい」という状態が存在しうるか と、 上で定義した状態において、その次はどの棒が目標となるか の つです。

ソースコード

自分にとっては相当難しい問題でした、また復習します。

class ClassicTowers {
    public:
    bool dp[3][51][51][51];
    int move[3][51][51][51];

    string findTowers(long long k, vector<int> count) {
        memset(dp, false, sizeof(dp));
        memset(move, -1, sizeof(move));
        int sum = count[0] + count[1] + count[2];
        if(k >= (1LL << (sum - 1))) return "";
        dp[0][0][0][0] = dp[1][0][0][0] = dp[2][0][0][0] = true;
        for(int cur=sum-1; cur>=0; cur--) {
            int disks = sum - cur - 1;
            if(k >> cur & 1) {
                // 移動回数が 2^k 増える → target の変動
                for(int target=0; target<3; target++) {
                    for(int h1=0; h1<=disks; h1++) {
                        for(int h2=0; h2<=disks-h1; h2++) {
                            int h3 = disks - h1 - h2;
                            if(!dp[target][h1][h2][h3]) continue;
                            for(int nxt=0; nxt<3; nxt++) {
                                if(target == nxt) continue;
                                int nh1 = h1, nh2 = h2, nh3 = h3;
                                int disk_idx = 3 - nxt - target;
                                if(disk_idx == 0) nh1++;
                                if(disk_idx == 1) nh2++;
                                if(disk_idx == 2) nh3++;
                                dp[nxt][nh1][nh2][nh3] = true;
                                move[nxt][nh1][nh2][nh3] = target;
                            }
                        }
                    }
                }
            }
            else {
                // 移動回数が増えない → target そのまま
                for(int target=0; target<3; target++) {
                    for(int h1=0; h1<=disks; h1++) {
                        for(int h2=0; h2<=disks-h1; h2++) {
                            int h3 = disks - h1 - h2;
                            if(!dp[target][h1][h2][h3]) continue;
                            int nh1 = h1, nh2 = h2, nh3 = h3;
                            if(target == 0) nh1++;
                            if(target == 1) nh2++;
                            if(target == 2) nh3++;
                            dp[target][nh1][nh2][nh3] = true;
                            move[target][nh1][nh2][nh3] = target;
                        }
                    }
                }
            }
        }
        for(int i=0; i<3; i++) {
            if(dp[i][count[0]][count[1]][count[2]]) {
                string ret = "";
                int target = i;
                for(int k=0; k<sum; k++) {
                    int nxt = move[target][count[0]][count[1]][count[2]];
                    int idx = (target == nxt ? target : 3 - target - nxt);
                    ret += (char)('A' + idx);
                    count[idx]--;
                    target = nxt;
                }
                return ret;
            }
        }
        return "";
    }
};

TopCoder SRM 715 Div1 Easy: MaximumRange

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

と のみからなる数列が与えられる。 (原文は文字列だけどまあ同じことなので)

この数列の (連続とは限らない) 部分列を取ることを考える。部分列の累積和を取った時の最大と最小の差の最大値を求めよ。

解説

打ち消し合ってしまうので、プラスの要素とマイナスの要素を両方使うことにメリットはありません。よってプラスだけ・もしくはマイナスだけ使うのがよいため、プラスの個数とマイナスの個数のうち大きいほうが答えになります。

ソースコード

class MaximumRange {
    public:
    int findMax(string s) {
        int a = 0, b = 0;
        for(auto x : s) {
            (x == '+' ? a : b)++;
        }
        return max(a, b);
    }
};

ABC の B 問題でありそう。少なくとも Div1 Easy ではない・・・。

TopCoder SRM 716 Div1 Easy: ConstructLCS

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

以下の条件を全て満たすような '0' と '1' のみからなる文字列 を構成せよ。

• と の最長共通部分列 (LCS) が
• と の LCS が
• と の LCS が

解説

を仮定すると、次のような文字列を構成すれば良いことが分かります。

• 文字列 → 文字の '0'
• 文字列 → 文字の '0' と、 文字の '1'
• 文字列 → 文字の '1' と、 文字の '0'

なぜ大小関係が必要かというと、これがないと色々と不都合が生じる可能性があるからです ( と の LCS について、 のほうではなく の方が採用されるかも、などなど)

しかし実際にはこの仮定はないため、どうするかと言うと、上と同じ方法で文字列を つ作り、そのうちどれを に、どれを に、どれを に当てはめるかを全て試し、その都度 LCS を取ります。どれかは必ず条件を満たしているので、これで解くことが出来ます。

ソースコード

class ConstructLCS {
    public:
    int calclcs(string a, string b) {
        int dp[1010][1010] = {};
        int n = a.length(), m = b.length();
        rep(i,0,n) rep(j,0,m) {
            if(a[i] == b[j]) dp[i+1][j+1] = dp[i][j] + 1;
            else dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
        }
        return dp[n][m];
    }

    string construct(int ab, int bc, int ca) {
        vector<int> ns = {ab, bc, ca};
        sort(ns.begin(), ns.end(), greater<int>());

        vector<string> strs(3);
        strs[0] = string(ns[0], '1');
        strs[1] = string(ns[0], '1') + string(ns[1], '0');
        strs[2] = string(ns[1], '0') + string(ns[2], '1');
        vector<int> perm = {0, 1, 2};
        do {
            string ra = strs[perm[0]], rb = strs[perm[1]], rc = strs[perm[2]];
            int nab = calclcs(ra, rb);
            int nbc = calclcs(rb, rc);
            int nca = calclcs(rc, ra);
            if(nab == ab && nbc == bc && nca == ca) {
                return ra + " " + rb + " " + rc;
            }
        }while(next_permutation(perm.begin(), perm.end()));
        return "";
    }
};