Project Euler - Problem 185

Number Mind

Number Mind は, 有名なゲームMaster Mindの変種である.

色つきのペグの代わりに, 秘密の数字を推理する. 推理するごとに, 正しい桁がいくつあったかのみが伝えられる. つまり, 答えが1234で, 2036と推理した場合, 1つの桁が正しいと伝えられる. 数字は正しいが場所が違うということは伝えられない.

例えば, 5桁の数に対して6個の推理

90342 ;2 桁正しい
70794 ;0 桁正しい
39458 ;2 桁正しい
34109 ;1 桁正しい
51545 ;2 桁正しい
12531 ;1 桁正しい

があったとすると,答えの数字は39542の唯一つとなる.

22 個の推理

5616185650518293 ;2 桁正しい
3847439647293047 ;1 桁正しい
5855462940810587 ;3 桁正しい
9742855507068353 ;3 桁正しい
4296849643607543 ;3 桁正しい
3174248439465858 ;1 桁正しい
4513559094146117 ;2 桁正しい
7890971548908067 ;3 桁正しい
8157356344118483 ;1 桁正しい
2615250744386899 ;2 桁正しい
8690095851526254 ;3 桁正しい
6375711915077050 ;1 桁正しい
6913859173121360 ;1 桁正しい
6442889055042768 ;2 桁正しい
2321386104303845 ;0 桁正しい
2326509471271448 ;2 桁正しい
5251583379644322 ;2 桁正しい
1748270476758276 ;3 桁正しい
4895722652190306 ;1 桁正しい
3041631117224635 ;3 桁正しい
1841236454324589 ;3 桁正しい
2659862637316867 ;2 桁正しい

に基づいて,16桁の唯一つの答えの数字を答えよ.

(日本語訳より)

深さ優先の枝刈り探索を書いてなんとか通した．実装が激重

イメージとしては初期状態を s = "????????????????" として，correct の値が大きい順に全てのパターンを試していく感じ．例えば 3 行目の

5855462940810587 ;3 桁正しい

を最初の条件として採用したとすると，? を埋める方法

s = "585?????????????", "58?5????????????", "58??4???????????", ..., "?????????????587"

₁₆C₃ 通りを全て試していくことになる．

最初に correct の降順に推理をソートして nums に格納する．最初の方にたくさん桁を確定させることで探索空間を減らす効果がある（昇順にソートするといつまでも終わらない）．

再帰関数 rec(string s, vector<int> valid, int depth) は，

s : 数字の埋まり具合 ( s = "010??68?3?3782?9 など．? は未確定の桁で，数字は確定済みの桁を表す )
valid : ( valid[i] の j ビット目が 1 ) = ( 先頭から i 桁目において数字 j を使うことが可能 )
depth : 現在見ている条件の番号

という状態を保持している．

数字を埋めていく過程で

s と nums[depth] で一致している桁の数を x としたとき，x > correct となったら矛盾
y = correct - x は確定させるべき桁の数になるが，これが (s[i] == '?' かつ valid) であるものの要素数 z (確定させることができる桁の数) を超えても矛盾
z ≧ y のとき，_zC_y 通りの状態を生成し，さらに深く探索
i 桁目を確定させたら valid[i] = 0 とし，y 個確定し終えてなお未確定 ('?') の桁については valid[i] の (nums[depth][i] - '0') ビット目を折る (後の探索で i 桁目に数字 nums[depth][i] を入れると correct 数との整合性が取れなくなるため)
valid[i] が 2 の累乗になっていたら，入るべき数字は 1 つに確定するので桁を埋めることができる．このとき i = 0, ..., depth - 1 の条件との整合性チェックをする必要がある

上に書いたようなことをもれなくダラダラ実装するとなんとか答えを出すことができた．

#include "bits/stdc++.h"

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define all(x) (x).begin(), (x).end()

typedef pair<int, string> pis;

int N = 22;
int M = 16;
vector<pis> nums;
string ans;

void rec(string s, vector<int> valid, int depth) {

    if (depth == N) {
        ans = s;
        return;
    }

    string a = nums[depth].second; // depth 番目の条件
    int correct = nums[depth].first; // ans と一致するべき数字の個数

    // 確定済みの桁について， s[i] == a[i] であるものの個数を x とする
    int x = 0;
    REP(i, M) if (s[i] == a[i]) x++;

    // x > k となった場合，矛盾
    if (x > correct) return;

    // 一致させるべき個数
    int y = correct - x;

    int z = 0; // 一致可能な個数
    vector<int> pos; // 一致可能な場所の情報
    REP(i, M) if (s[i] == '?' && (valid[i] & (1 << (a[i] - '0')))) {
        pos.push_back(i);
        z++;
    }

    if (z < y) return;

    if (y == 0) {
        string ns(s);
        vector<int> nvalid(valid);
        REP(i, z) {
            // pos[i] 桁目で数字 a[pos[i]] は使えない
            nvalid[pos[i]] ^= (1 << (a[pos[i]] - '0'));
        }

        /*マス確定 & 矛盾チェック*/
        bool update = false;
        REP(i, M) {
            // i 桁目に関して，nvalid[i] == (1 << k) である場合は，その桁の数字は k 以外でありえない
            REP(k, 10) if (nvalid[i] == (1 << k)) {
                ns[i] = (k + '0');
                update = true;
            }
        }
        // nums[i] (i = 0, ..., depth - 1) に対して矛盾がないかチェックする
        if (update) {
            REP(i, depth) {
                int ncorrect = 0;
                REP(j, M) if ((nums[i].second)[j] == ns[j]) ncorrect++;
                if (ncorrect != nums[i].first) return;
            }
        }
        rec(s, nvalid, depth + 1);
        if (ans != "") return;
    }
    else {
        // z C y 通りの状態を生成する
        for (int c = (1 << y) - 1; c < (1 << z); ) {
            string ns(s);
            vector<int> nvalid(valid);

            REP(i, z) {
                if (c & (1 << i)) {
                    ns[pos[i]] = a[pos[i]]; // マスを確定させる
                    nvalid[pos[i]] = 0; // pos[i] 桁目のすべてのフラグを折る
                }
                else {
                    nvalid[pos[i]] ^= (1 << (a[pos[i]] - '0')); // pos[i] 桁目で数字 a[pos[i]] は使えない
                }
            }

            /*マス確定 & 矛盾チェック*/
            bool update = false;
            REP(i, M) {
                // i 桁目に関して，nvalid[i] == (1 << k) である場合は，その桁の数字は k 以外でありえない
                REP(k, 10) if (nvalid[i] == (1 << k)) {
                    ns[i] = (k + '0');
                    update = true;
                }
            }
            // nums[i] (i = 0, ..., depth - 1) に対して矛盾がないかチェックする
            bool flag = true;
            if (update) {
                REP(i, depth) {
                    int ncorrect = 0;
                    REP(j, M) if ((nums[i].second)[j] == ns[j]) ncorrect++;
                    if (ncorrect != nums[i].first) {
                        flag = false;
                        break;
                    }
                }
            }

            if (flag) {
                rec(ns, nvalid, depth + 1);
                if (ans != "") return;
            }

            int t = c & -c, u = c + t;
            c = ((c & ~u) / t >> 1) | u;
        }
    }
}

int main()
{
    clock_t start, end;
    start = clock();

    //cin.tie(0);
    //ios::sync_with_stdio(false);

    {
        string tmp;
        REP(i, N) {
            pis p;
            cin >> tmp;
            p.second = tmp;
            cin >> tmp;
            p.first = tmp[1] - '0';
            nums.push_back(p);
            cin >> tmp;
        }
    }

    sort(all(nums));

    // i 桁目において数字 j が使えるかどうか
    vector<int> valid(M, (1 << 10) - 1);

    rec(string(M, '?'), valid, 0);

    cout << ans << endl;
    
    end = clock();
    printf("%d msec.\n", end - start);

    return 0;
}

5 sec くらい．

絶滅

どうでもいい

Project Euler - Problem 185

Number Mind