Google Code Jam 2019 Round1C : Power Arrangers

問題. Power Arrangers

ABCDE の5文字からなる順列は $5! = 120$ 通りある．その中から1つの順列を取り除いた119個の順列を適当な順番に並べた列 $s$ がある（ $s$ は未公開）．「 $s$ の $i$ 番目の文字が何か」というクエリを高々 $F$ 回行い取り除かれた順列を求めよ．

制約： $F = 475, 150$

解法

取り除かれた順列 $p$ を1番目の文字から順番に求めることを考える． $p$ の1番目の文字は119個の各順列の1番目の文字へのクエリを行い，5文字の中で出現頻度が一番小さいものとなる．次に $p$ の2番目の文字を求めることを考える．このとき，1番目の文字が $p$ と異なる順列は考える必要がないので， $5! / 5 - 1 = 23$ 個の順列の2番目の文字へのクエリのみを行い，上と同様に出現頻度が一番小さく $p$ の 1番目と異なる文字が $p$ の2番目の文字となる．3番目と4番目の文字も同様にして求めると，クエリの総回数は
　 $(5! \,/ \, 5 - 1) + (4! \,/ \, 4 - 1) + (3! \,/ \, 3 - 1) = 148 \le F$
となる．ただし，5番目の文字は $p$ の1番目から4番目に含まれない文字となるのでクエリを行う必要がない．

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

/********************************************************************/
class Solver {
public:
    void solve();
    void print() {
        cout << ans << endl;
        char verdict; cin >> verdict;
        if (verdict == 'N') exit(0);
    }

private:
    // define variable
    string ans;
};

void Solver::solve() {
    const int SIZE = 119;
    vector<bool> valid_set(SIZE, true), valid_char(5, true);
    vector<char> fig(SIZE);

    for (int i = 0; i < 4; ++i) {
        vector<int> cnt(5);

        for (int j = 0; j < SIZE; ++j) {
            if (!valid_set[j]) continue;
            cout << j * 5 + i + 1 << endl;
            cin >> fig[j];
            ++cnt[(int)(fig[j] - 'A')];
        }

        int idx = -1;
        for (int j = 0; j < 5; ++j) {
            if (valid_char[j] && (idx == -1 || cnt[j] < cnt[idx])) idx = j;
        }

        char select = (char)('A' + idx);
        for (int j = 0; j < SIZE; ++j)
            if (valid_set[j] && fig[j] != select)
                valid_set[j] = false;

        valid_char[idx] = false;
        ans += select;
    }

    for (int i = 0; i < 5; ++i)
        if (valid_char[i]) {
            ans += (char)('A' + i);
            break;
        }
}
/********************************************************************/

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    // cout << setprecision(4) << setiosflags(ios::fixed);

    int T, F; cin >> T >> F;
    for (int i_case = 1; i_case <= T; ++i_case) {
        Solver s;
        s.solve();
        s.print();
    }

    return 0;
}