CSAcademy Round #72: Spring Cleaning

問題概要

原文 → CS Academy

頂点からなる有向グラフがある。このグラフは各頂点から 本ずつ有向辺が出ており、自己ループがないことが保証されている。

はじめ、全ての頂点に対して駒が 個ずつ置かれている。ここから、以下のルールにしたがって駒を取り除くことができる。

• 頂点 から出る有向辺によって繋がっている頂点を とおくとき、 ともに駒がある場合、 にある駒を取り除くことができる。

できるだけ多くの駒を取り除くとき、この操作列を出力せよ。

解説

頂点 辺の有向グラフなので、いわゆるなもりグラフで、ループが必ず つあるグラフです。なので、それぞれの頂点に対して「ループに繋がっている頂点」であるか「ループ内の頂点」であるかのどちらかです。

ループ内の頂点から探索を始めると、ループに繋がっている頂点を取れない可能性があるので、ループに繋がっている頂点から優先的に探索をすればよいです。これをするには、入次数が である頂点から先に探索すれば良いです。

なお、ひとつの大きな閉路になっていて入次数が である頂点がひとつもない場合もあることなどに注意してください。

ソースコード

void solve(vector<int>& edge, vector<int>& visited, int cur) {
    visited[cur] = true;
    if(visited[ edge[cur] ]) return;
    solve(edge, visited, edge[cur]);
    printf("%lld %lld\n", cur+1, edge[cur]+1);
}

signed main() {
    int N; cin >> N;
    vector<int> to(N, -1), deg(N, 0), visited(N, 0);
    rep(i,0,N) {
        int p; cin >> p; p--;
        to[i] = p;
        deg[p]++;
    }

    deque<int> deq;
    rep(i,0,N) {
        if(deg[i] == 0) deq.push_front(i);
        else deq.push_back(i);
    }

    rep(i,0,N) {
        solve(to, visited, deq[i]);
    }
}

CSAcademy Round #72: Beautiful Matrix

問題概要

原文 → CS Academy

の行列 から、 の行列 を作る。 (作り方は原文参照)

を作る前に、 について行どうし、または列どうしのスワップを合計 回まで行える (何もしなくても良い) とき、 の最大値を求めよ。

解説

ある要素が、 の要素のうちいくつに関係しているか、要するに何回足されるかを調べてみます。

すると、端は に、それ以外は になることが分かります。

つまり、総和を変更するには「端とそれ以外のスワップ」にだけ着目すれば良いことになります。 (端の最大) と (中の最小) をスワップすると最適になり、これを全て試すのは で行えます。

実装方針がアだと面倒になるので注意してください。端であってもそうでなくても、増減の絶対値は になる (伝わって) ので、それを利用すると楽です。

ソースコード

int N, M;
vector< vector<int> > board;

int solve_row() {
    int outside_val = -INF, inside_val = INF;
    rep(i,0,N) {
        int val = 0;
        rep(j,0,M) {
            if(j == 0 || j == M-1) val += board[i][j];
            else val += 2 * board[i][j];
        }
        if(i == 0 || i == N-1) {
            chmax(outside_val, val);
        }
        else {
            chmin(inside_val, val);
        }
    }
    return outside_val - inside_val;
}

int solve_col() {
    int outside_val = -INF, inside_val = INF;
    rep(j,0,M) {
        int val = 0;
        rep(i,0,N) {
            if(i == 0 || i == N-1) val += board[i][j];
            else val += 2 * board[i][j];
        }
        if(j == 0 || j == M-1) {
            chmax(outside_val, val);
        }
        else {
            chmin(inside_val, val);
        }
    }
    return outside_val - inside_val;
}

signed main() {
    cin >> N >> M;
    board.resize(N, vector<int>(M));
    int orig_sum = 0;
    rep(i,0,N) rep(j,0,M) {
        cin >> board[i][j];
    }

    rep(i,0,N-1) rep(j,0,M-1) {
        rep(k,0,4) {
            int nx = i + dx[k], ny = j + dy[k];
            orig_sum += board[nx][ny];
        }
    }

    int diff = 0;
    chmax(diff, solve_row());
    chmax(diff, solve_col());
    cout << orig_sum + diff << endl;
    return 0;
}

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