TopCoder SRM 715 Div1 Med: ClassicTowers

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

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

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

解説

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

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

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

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

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

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

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

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

必要な情報は $\mathrm{dp} \left[ i \right] \left[ h_{1} \right] \left[ h_{2} \right] \left[ h_{3} \right] :=$ 「既にそれぞれ $h_{1}, h_{2}, h_{3}$ 個のディスクが置かれている状態で、次のディスクを棒 $i$ に置きたい」という状態が存在しうるかと、 $\mathrm{move} \left[ i \right] \left[ h_{1} \right] \left[ h_{2} \right] \left[ h_{3} \right] :=$ 上で定義した状態において、その次はどの棒が目標となるかの $2$ つです。

ソースコード

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

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 "";
    }
};

hogecoder

tsutaj 競技プログラミングの記録

TopCoder SRM 715 Div1 Med: ClassicTowers

問題概要

解説

ソースコード