TECH PLAYで連載されている「パズルのアルゴリズム問題」を解いてみた

パズルのアルゴリズム問題 とは

増井敏克さんによる，TECH PLAY Magazineの連載です．
毎月出題・解説は翌月とのこと．

モチベーション

自由に公開しても良いとの事なので，公開します．
解説コードがRubyなので，なるべくRuby以外で書くことにします．
ほとんどの場合でC++14を使用します．

ソースコードについて

検証はしていませんが，ideone C++14なら動くと思います．
visual studioの場合，bits/stdc++.h を準備する必要があります．

更新履歴

2018/11/06 追加：多倍長整数実装のコインロッカー
2018/11/05 追加：コインロッカー
2018/09/22 魔方陣・ソースコードについて少し加筆
2018/09/20 投稿

解法

以降はネタバレです．

魔方陣

問題文URL https://techplay.jp/column/298

# include "bits/stdc++.h"
using namespace std;

int main() {
    int N;
    cin >> N;

    vector<int> mat(9);

    for (int i = 0; i < 9; ++i)
        mat[i] = N + i;

    do {
        int sum = mat[0] + mat[1] + mat[2];
        if (sum == mat[3] + mat[4] + mat[5] &&
            sum == mat[6] + mat[7] + mat[8] &&
            sum == mat[0] + mat[3] + mat[6] &&
            sum == mat[1] + mat[4] + mat[7] &&
            sum == mat[2] + mat[5] + mat[8] &&
            sum == mat[0] + mat[4] + mat[8] &&
            sum == mat[2] + mat[4] + mat[6]) {
            printf("%2d%2d%2d\n", mat[0], mat[1], mat[2]);
            printf("%2d%2d%2d\n", mat[3], mat[4], mat[5]);
            printf("%2d%2d%2d\n", mat[6], mat[7], mat[8]);
            break;
        }
    } while (next_permutation(mat.begin(), mat.end()));

    return 0;
}

マスに入れたい数字が既に決まっているので，next_permutationで全探索すればよいです．

ループ回数は9!で，大体37万回なので十分高速です．

タイトルが「複数の解き方を考えて実装してみよう！」なので，複数の解き方を考えてみたんですが，

• 再帰枝刈り
• P(9,3)を全探索
  の2つしか思いつきませんでした．

階段でよく遊んだゲーム

問題文URL https://techplay.jp/column/328

# include "bits/stdc++.h"
using namespace std;

map<array<int, 3>, int> memo; // メモ化再帰

// n: じゃんけんを行う回数
// ma: aさんがゴールに到達するまでに必要な段数
// mb: bさんがゴールに到達するまでに必要な段数
// @return: Aさんが先にゴールに到達するようなそれぞれの出す手が何通りあるか
int solve(int n, int ma, int mb) {
    if (ma <= 0) return 1; // 既にゴールラインを超えているので勝ち
    if (mb <= 0) return 0; // 既にゴールラインを超えているので負け
    if (n <= 0) return 0; // じゃんけんしないので勝つことも無い

    // メモ化再帰(キャッシュ)
    array<int, 3> key = { n, ma, mb };
    if (memo.count(key)) return memo[key];

    int ans = 0;

    ans += solve(n - 1, ma, mb)*3; // あいこのパターンは3つ
    ans += solve(n - 1, ma - 1, mb) * 1; // GでAが勝つパターンは1つ
    ans += solve(n - 1, ma - 2, mb) * 2; // G以外でAが勝つパターンは2つ
    ans += solve(n - 1, ma, mb - 1) * 1; // GでBが勝つパターンは1つ
    ans += solve(n - 1, ma, mb - 2) * 2; // G以外でBが勝つパターンは2つ

    return memo[key] = ans;
}


int main() {
    int n, m;

    cin >> m >> n;
    cout << solve(n, m, m) << endl;

    return 0;
}

元の問題を複数に部分問題に分割して解く問題です．
連載の方とほぼ同じなので解説は省略．

メモ化再帰については，「もっとプログラマ脳を鍛える数学パズル」にもかなり詳しく書かれています．

山手線

# include "bits/stdc++.h"
using namespace std;


// 駅の個数
const int M = 29;
// 間隔
const int D[] = {
    13,  7, 10, 06, 11,
    11,  5,  8, 16, 07,
    11, 18, 12,  9, 14,
    13,  7, 15, 12, 16,
    15, 12,  9, 20, 22,
    15, 12, 11,  8
};
// 円周
const int Dtotal = accumulate(D, D + M, 0);

// 人の数
int N;


// base駅に必ず1人置いて，marginずつ間隔を開けて座れるか？
bool check(int margin, int base) {
    int len = 0;
    int ptr = 0;
    for (int i = 1; i < N; ++i) {
        int x = 0;
        while (x < margin) {
            x += D[(base + ptr++) % M];
            if (ptr >= M) return false;
        }
        len += x;
    }
    return Dtotal - len >= margin;
}

// marginずつ間隔を開けて配置できるか
bool check(int margin) {
    for (int i = 0; i < M; ++i) {
        if (check(margin, i)) return true;
    }
    return false;
}


int main() {
    cin >> N;

    // 二分探索
    int tval = 0, fval = Dtotal;

    while (fval - tval > 1) {
        int v = (fval + tval) / 2;
        if (check(v))
            tval = v;
        else
            fval = v;
    }

    cout << tval << endl;

    return 0;
}

小数点以下1桁だったので，10倍して整数にしました．

まず，関数bool check(int margin) を用意します．
marginずつ間隔を開けて配置できるかどうか判定する関数です．

この関数を使って解（間隔の最小値が最大になるような配置の間隔の最小値）を探索すれば良いです．
二分探索がオススメですが，各駅の間の距離の精度も高くないので，線形探索でも答えを計算できるはずです．

コインロッカー

# include "bits/stdc++.h"
using namespace std;
using ll = long long;


int width, height;

// 幅1高さhのサイズに積み重ねて隙間なく配置するとき
// その配置が何通りあるか求める
ll calculate_col(int h) {
    if (h == 0) return 1; // 選ばない，の1通り
    if (h == 1) return 1; // 1つ選ぶ，の1通り
    return calculate_col(h - 1) + calculate_col(h - 2);
}

// calculate x**p
inline ll my_pow(ll x, ll p) {
    ll ans = 1;
    for (ll i = 0; i < p; ++i)
        ans *= x;
    return ans;
}

int main() {
    cin >> width >> height;
    cout << my_pow(calculate_col(height), width);
    return 0;
}

m,n は紛らわしいので，ソースコード・説明ではwidth = m，height = nと置き換えることにします．

2種類のロッカーの幅がどちらも1である点に注目．
1列ごとにパターンの数を別々に計算して，最後に纏めれば良さそうです．
全ての列において高さは同じなので，列ごとのパターンの数は同じです．
1列のパターンの数をcと置くと，1列目からcパターンある中で1つ，2列目からcパターンある中で1つ，…と選んでいく組み合わせなので，最終的な答えはcのwidth乗です．

未だ1列のパターンの数の求め方が残っています．これは再帰的に求めることが出来ます．
「高さheightの1列のパターンの数」をf(height)と書くことにします．
height = 0の時，「選ぶことが出来ない」の1通りなので，f(0) = 1です．
height = 1の時，「1x1のロッカーを配置する」の1通りなので，f(1) = 1です．
height >= 2の場合は再帰的に計算します．一番下に「1x1」を置く場合を考えると，高さが1減ります．同様に，「1x2」を置く場合を考えると，高さは2減ります．この2つのパターンの和なので，f(height) = f(height-2) + f(height-1)です．
以上により，高さheightの1列のパターンの数を求めることができ，最終的な答えも得られます．

ところで，calculate_col関数をよく眺めると，これはフィボナッチ数列になっています．
上のC++のcalculate_col関数の計算時間は指数関数的ですが，線形時間に落とすことも簡単そうです．
「m <= $10^{18}$，n <= $10^{18}$の制約の下で，ロッカーの配置が何通りあるか，10007で割った余りを出力せよ」も面白そうですね．

制約の話を書きましたが，この問題の制約『m, nともに10以下の整数とします』には少し引っ掛けがあります．
height = 10, width = 10 の時，解は$3.1\times 10^{19}$程度になります．
この値は64bitで表現出来る範囲を超えるため，上記のコードでは正しく動作しないことになります．
この問題を回避するためには，128bit整数を使う，多倍長整数を準備する等があります．

javascript

// calculate bigx *= y
function multiply(bigx, y) {
    let carry = 0;
    for (let i = 0; i < bigx.length; ++i) {
        carry += bigx[i] * y;
        bigx[i] = carry % 10000;
        carry = Math.floor(carry / 10000);
    }
    if (carry > 0) bigx.push(carry);
    return bigx;
}


function bignum_to_string(bigx) {
    let str = "";
    for (let i = 0; i < bigx.length-1; ++i) {
        let s = "" + bigx[i];
        while (s.length < 4) s = "0" + s;
        str = str + s;
    }
    return "" + bigx[bigx.length-1] + str;
}


function fibo(n) {
    let a = 1, b = 1;
    while (--n)
        [a, b] = [b, a+b];
    return b;
}


function solve(width, height) {
    const cl = fibo(height);
    
    let ans = [1];
    for (let i = 0; i < height; ++i)
        multiply(ans, cl);
    
    console.log(bignum_to_string(ans));
}

solve(10, 10);

多倍長整数どころか64bit整数すら無いjavascriptで回答してみました．

実装しなければならないメソッドは「多倍長整数ｘ小さな整数」「多倍長整数を10進数表記の文字列に変換」の2つだけです．

「多倍長整数っぽいもの」を10進数4桁区切りの配列で表現します．
10のべき乗区切りにすることで，bignum_to_string の実装を簡単なものにします．