TwitCasting2018SummerQual

問題概要

相手が持っている数を当てる、Hit and Blow/Bulls and Cows/numer0nと呼ばれるゲームがある。全部ルールは一緒。
相手は$N$桁の重複のない数字を持っている。自分が予想して数字を言うと、予測した数の各桁の数が存在するか/位置も正しいかを教えてくれる。 回答の時間が短いほど得点が高い。得点を最大化せよ。
ただし、0987654321という数字も存在する。(leading zero)

https://twitcasting.tv/internship2018.php (問題はもう掲載されていない)

解法

自分は2つ解法を考えたのでどちらも書いておく。
基本的な方針は一緒で、答えとなりうるN桁の数を先に列挙しておいて、質問から得られるhit/blowの情報に一致しないものを削除していく。
次に質問する候補は、残ったものから適当に選択する。
これを繰り返すと6-10回ぐらいで解を求めることができる。

プログラムのボトルネックは削除のパートだったのとhttp通信を手軽に書きたかったことから、通信はPythonで予測の部分はC++で書いた。pybind11というライブラリがとても便利だった。

方針1

先に列挙してから削除を行うので、削除を高速に行いたい。また、集合の中の値をランダムに選択できると嬉しい。
setを考える。削除・検索を$O(logX)$でできるので良さそう。ランダムアクセスはできないが、存在しない値を入れて、

string s = "ランダムな値" 
SET.insert(s);
auto it = SET.find(s);
it++; 
auto origin = SET.find(s);
SET.erase(origin)

をすれば実質ランダムな値を選択することができる。
したがって操作は$O(logX)$でできる。速そう。 unordered_setにすると更に少し速くなった。ここまで書くだけで110万点。

次に10桁の候補の数が$3628800$個しか無いので、配列に入れれそうな気がしてくる。
0/1の値をもつ配列を使用するとすると、削除は$O(1)$で、検索は$O(X)$になる。BITを用いると削除$O(logX)$,検索はBIT上を二分探索で$O(logX)$で行うことができる。113万点。

10回以内に当てられるとすると、$O(logX)$も馬鹿にできない気持ちになる。
削除がたくさん行われるので、削除は$O(1)$で行ってまだ候補になっている数をrand()で発見したほうがいいかもしれないので試す。113万点で変わらないが、スコアの期待値は高くなった。

結局、set→unordered_set→自作平衡二分木→BIT+二分探索→配列→bitsetとたくさんプログラムを書いたが、BITが一番良かった。

方針2

並列化する。
方針1ではBITを用いて要素の削除や検索を操作1回につき$O(logX)$に高速化していたが、視点を変えて並列化する。
すると愚直$O(X)$でも各操作は独立しているのでとても高速に処理をすることができる。
僕はC++を使っていたので、openMPを使ってfor文を並列化した。家のパソコンはコア数が8だったが、方針1と一緒の速度が出た。
コア数を増やすとオーべーヘッドを加味してももっと速くする事ができそう。 1-3位の人にはこれをやった人がいるらしい。

感想

21位　プロ達はすごい
大学の先輩は僕より順位が高かったので悔しかった。
大学のスパコンかEC2/HPCが使えたら何点取れたかとても気になるけど申請が必要みたいで時間切れになってしまった。

みんなが知っているゲームだけど一般化できるとは思っていなかったので面白かったです！
トップの人にも追いつけそうで追いつけなかったので力の差を感じました。

他の方の解法

(/^^)/⌒●~*$ a(){ a|a& };a ツイキャスエンジニアインターンシップ2018応募前チャレンジでランキング1位を取った(@new_paradigm_9さん) 募集要項のどこにも「これを解くプログラムを公開してはいけない」とは書いていなかったので,募集期間(7/11:23:59:59)を越えたので公開します

ソース

(通信部は書くだけなので割愛します)

方針1

    #include <unordered_set>
    #include <unordered_map>
    #include <string>
    #include <map>
    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <time.h>
    #include <assert.h>
 
    using type = int;
    struct BIT { // 1-index
        int N;
        int nn;
        int data[3628800 + 20];
        BIT(int n) {
            N = n + 1;
            nn = 1;
            while (nn * 2 <= N)nn *= 2;
        }
        void add(int i, type w) { // a[i] += w
            for (int x = i; x <= N; x += x & -x) {
                data[x] += w;
            }
        }
        type sum(int i) { // iまでの和 [1,i]
            type ret = 0;
            for (int x = i; x > 0; x -= x & -x) {
                ret += data[x];
            }
            return ret;
        }
        // [l, r]
        type sum(int l, int r) {
            if (l > r) return 0;
            return sum(r) - sum(l - 1);
        }
    
        int lower_bound(type w) {
            if (w <= 0) return 0;
            int x = 0;
            for (int k = nn; k > 0; k /= 2) {
                if (x + k <= N && data[x + k] < w) {
                    w -= data[x + k];
                    x += k;
                }
            }
            return x + 1;
        }
    };
    
    
    
    /* 適当なlong long の乱数 */
    long long myrand() {
        return abs(rand() * rand() + 2311 * rand() + 1992);
    }
    
    class TwitCastingSummerQual2018
    {
    public:
        TwitCastingSummerQual2018() :BitSet(3628800 + 20), LEN(10) {
            genarateCandidate();
            std::cout << "Candidate :=" << BitSet.sum(3628800 + 20) << std::endl;
            srand(static_cast<unsigned int>(time(NULL)));
        }
        std::string temp;
        std::string GetSetNum() {
            temp = RandomGetFromSet();
            return temp;
        }
        void ClearNum(int a, int b) {
            std::pair<int, int > result = { a, b };
            clearSet(temp, result);
        }
    private:
        BIT BitSet;
        const int LEN;
        std::unordered_map<std::string, int> StoI;
        std::string ItoS[3628820];
    
    
    
    
        // 削除：BIT =0にする(O(logN))
        // 存在する要素はBIT.lowerでできる
        // 1の要素を発見したら、この位置に対応するstring をmapから持ってくる
        void clearSet(const std::string &guessNum, const std::pair<int, int>& hitAndBlow)
        {
    
            for (int i = 1; ;) {
                int pos = BitSet.lower_bound(i);
                if (pos == 3628800 + 10)break;;
                if (removeIt(guessNum, ItoS[pos], hitAndBlow)) {// 実体は削除しないほうが速いと思ったがそうでもない…
                    BitSet.add(pos, -1);
                }
                else {
                    i++;
                }
            }
        }
    
    
        // ランダムに取る
        std::string RandomGetFromSet()
        {
            int Sum = BitSet.sum(3628800 + 10) - 1;// 番兵の分
            if (Sum == 0) {
                std::cerr << "Sum:= ZERO (p_p)" << std::endl;
                assert(0);
            }
            int randPosSum = myrand() % Sum + 1;
            int pos = BitSet.lower_bound(randPosSum);
            return ItoS[pos];
        }
    
        void genarateCandidate()
        {
            std::unordered_set<std::string>Se;
            std::vector<int>ordernum(10, 0);
            for (int i = 0; i < 10; i++) {
                ordernum[i] = i;
            }
            do {
                std::string S = std::string(LEN, '0');
                for (int i = 0; i < LEN; i++) {
                    S[i] += ordernum[i];
                }
                if (IsCandidateNum(S))Se.insert(S);
    
            } while (next_permutation(begin(ordernum), end(ordernum)));
    
            int id = 1;
            for (auto & it : Se) {
                StoI[it] = id;
                ItoS[id] = it;
                BitSet.add(id, 1);
                id++;
            }
            BitSet.add(3628800 + 10, 1);
    
        }
    
        bool IsCandidateNum(std::string& s)
        {
            for (auto si : s) {
                if (count(s.begin(), s.end(), (si)) > 1) {
                    return false;
                }
            }
            return true;
        }
    
        bool removeIt(const std::string &guessNum, const std::string &ts, const std::pair<int, int>& hitAndBlow)
        {
            std::pair<int, int> checkState;// hit and blow
    
            checkState.first = checkState.second = 0;
            for (int i = 0; i < LEN; ++i) {
                if (guessNum[i] == ts[i]) ++checkState.first;
                else {
                    for (int j = 0; j < LEN; ++j)
                        if (guessNum[i] == ts[j]) ++checkState.second;
                }
                if (checkState.first > hitAndBlow.first)return true;
                if (checkState.second > hitAndBlow.second)return true;
            }
    
            return checkState != hitAndBlow;
        }
    };

方針2

    #include <unordered_set>
    #include <unordered_map>
    #include <string>
    #include <map>
    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <bitset>
    #include <time.h>
    #include <assert.h>
    #include <omp.h>
    
    
    
    /* 適当なlong long の乱数 */
    long long myrand() {
        return abs(rand() * rand() + 2311 * rand() + 1992);
    }
    
    class TwitCastingSummerQual2018
    {
    public:
        TwitCastingSummerQual2018() :LEN(10) {
            genarateCandidate();
            srand(static_cast<unsigned int>(time(NULL)));
        }
        std::string temp;
        std::string GetSetNum() {
            temp = RandomGetFromSet();
            return temp;
        }
        void ClearNum(int a, int b) {
            std::pair<int, int > result = { a, b };
            clearSet(temp, result);
        }
    
    private:
        std::bitset<36288020>bs;
        const int LEN;
        std::unordered_map<std::string, int> StoI;
        std::string ItoS[3628820];
    
    
    
        void clearSet(const std::string &guessNum, const std::pair<int, int>& hitAndBlow)
        {
    #pragma omp parallel for 
            for (int i = 1; i < 3628810; i++) {
                if (bs[i]) {
                    if (removeIt(guessNum, ItoS[i], hitAndBlow)) {
                        bs[i] = 0;
                    }
                }
    
            }
        }
    
    
        // ランダムに取る
        std::string RandomGetFromSet()
        {
            while (1) {
                {
                    int ran = myrand() % 3628;
                    if (bs[ran]) {
                        return ItoS[ran];
                    }
                }
                {
                    int ran = myrand() % 3628801;
                    if (bs[ran]) {
                        return ItoS[ran];
                    }
                }
            }
    
    
        }
    
        void genarateCandidate()
        {
            std::unordered_set<std::string>Se;
            std::vector<int>ordernum(10, 0);
            for (int i = 0; i < 10; i++) {
                ordernum[i] = i;
            }
            do {
                std::string S = std::string(LEN, '0');
                for (int i = 0; i < LEN; i++) {
                    S[i] += ordernum[i];
                }
                if (IsCandidateNum(S))Se.insert(S);
    
            } while (next_permutation(begin(ordernum), end(ordernum)));
    
            int id = 1;
            for (auto & it : Se) {
                StoI[it] = id;
                ItoS[id] = it;
    
                bs[id] = 1;
                id++;
    
            }
        }
    
        bool IsCandidateNum(std::string& s)
        {
            for (auto si : s) {
                if (count(s.begin(), s.end(), (si)) > 1) {
                    return false;
                }
            }
            return true;
        }
    
        bool removeIt(const std::string &guessNum, const std::string &ts, const std::pair<int, int>& hitAndBlow)
        {
            std::pair<int, int> checkState;// hit and blow
    
            checkState.first = checkState.second = 0;
            for (int i = 0; i < LEN; ++i) {
                if (guessNum[i] == ts[i]) ++checkState.first;
                else {
                    for (int j = 0; j < LEN; ++j)
                        if (guessNum[i] == ts[j]) ++checkState.second;
                }
                if (checkState.first > hitAndBlow.first)return true;
                if (checkState.second > hitAndBlow.second)return true;
            }
    
            return checkState != hitAndBlow;
        }
    };