絶滅

どうでもいい

Project Euler - Problem 336

Maximix Arrangements

Problem 336 (日本語訳)

汽車を使って, 4 個の貨物を ABCD の順に輸送する. しかし, 汽車が荷物を集めに来た際, ときに貨物が正しい順でないことがある.
並び替えのために貨物はすべて大きな回転台に移される. 特定の点で貨物が切り離されると, 汽車は自身につながったままの貨物ごと回転台から離れる. 残された貨物は 180 度回転する. 貨物はすべて再びつなげられ, 回転台を使う回数がなるだけ少なくなるようにこの手続きが繰り返される.
ADCB のような配置は簡単に解くことができる:貨物を A と D の間で切り離し, DCB を回転すると正しい順が得られる. しかし, 汽車の操縦者であるシンプル・サイモンは効率があまりよくなく, いつも最初に貨物 A を正しい位置に移し, 次に貨物 B を移し, 以下これを繰り返すというやり方でこの問題を解く.

4個の貨物を使うと, Simon にとってあり得る最悪の配置(maximix 配置と呼ぶ)は DACB と DBAC である;それぞれ 5 回の回転を要する(最も効率的なアプローチを使うと 3 回の回転のみで解くことができるが). DACB に対する彼の手順を以下に示す.

f:id:my316g:20171231213915p:plain


6 個の貨物に対する maximix 配置は 24 個あることが確かめられる. そのうち辞書順で 10 番目の maximix 配置は DFAECB である.

11 個の貨物に対し辞書順で 2011 番目の maximix 配置を求めよ.

(日本語訳より)




問題文が長いが素直に書けば通る親切設計だった.

説明はコードの中で適当にやっています.

int process(vector<int> carriages) {
    // 回転台を使う回数
    int step = 0;
    // 整列対象の位置
    int n = 0;
    while (n != carriages.size()) {
        // 貨物 n が正しい位置 (位置 n) にある
        if (carriages[n] == n) {
            // 操作はいらない
            n++;
        }
        // 貨物 n が末尾にある
        else if (carriages.back() == n) {
            // 現在位置 n から末尾まで反転
            reverse(carriages.begin() + n, carriages.end());
            step++; n++;
        }
        // 貨物 n がそれ以外の場所にある
        else {
            // 貨物 n が存在する位置を求める
            int pos;
            for (pos = n; pos < carriages.size() - 1; pos++) {
                if (carriages[pos] == n) break;
            }
            // 貨物 n を末尾に移動する
            reverse(carriages.begin() + pos, carriages.end());
            step++;
            // 貨物 n を先頭に移動する
            reverse(carriages.begin() + n, carriages.end());
            step++; n++;
        }
    }
    return step;
}

int main() {

    clock_t start, end;
    start = clock();

    const int NCARRIAGES = 11;
    const int NUM = 2011;
    
    // 貨物の並び : A は 0, B は 1, C は 2, ... に対応する
    vector<int> carriages;
    for (int i = 0; i < NCARRIAGES; i++) carriages.push_back(i);

    // 最大ステップ数を求めるために,全ての貨物の並び 11! 通りに対して必要ステップ数を求め,
    // map にヒストグラムとして格納していく
    map<int, int> mp;
    do { mp[process(carriages)]++; } while (next_permutation(all(carriages)));

    // map の末尾のキーが最大ステップ数になっている
    int maxStep = (--mp.end())->first;

    // 貨物の並びを初期化
    carriages.clear();
    for (int i = 0; i < NCARRIAGES; i++) carriages.push_back(i);

    // 最大ステップ数を要する ( = Maximix 配置である) 配置の中で,2011 番目のものを出力する
    int cnt = 0;
    do {
        if (process(carriages) == maxStep) cnt++;
        if (cnt == NUM) {
            for (int i = 0; i < carriages.size(); i++) cout << char('A' + carriages[i]);
            cout << endl;
            break;
        }
    } while (next_permutation(all(carriages)));
    
    end = clock();
    printf("%f sec.\n", double(end - start) / CLOCKS_PER_SEC);
    return 0;
}

10.4 sec くらい.