#1157400 (C++23) No.3496 協力カード当て

• 問題: No.3496 協力カード当て
• ユーザー: 👑 sgfc
• 提出日時: 2026-04-15 03:53:47
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 52 ms / 2,000 ms
• コード長: 3,942 bytes
• コンパイル時間: 1,874 ms
• コンパイル使用メモリ: 180,436 KB
• 実行使用メモリ: 30,064 KB
• スコア: 132
• 平均クエリ数: 40.00
• 最終ジャッジ日時: 2026-04-15 03:53:53
• 合計ジャッジ時間: 5,672 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
other	AC * 16

ソースコード

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;
using ll = long long;
constexpr int cblim = 60;

ll comb[cblim][cblim];
void init_comb() {
    for (int i = 0; i < cblim; ++i) {
        comb[i][0] = 1;
        for (int j = 1; j <= i; ++j) {
            comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
        }
    }
}

ll nCr_multi(int n, int r) {
    if (n < 0 || r < 0) return 0;
    if (r == 0) return 1;
    return comb[n + r - 1][r];
}

ll hand_to_rank(const vector<int>& counts, int N, int M) {
    ll rank = 0;
    int remaining_N = N;
    for (int i = 1; i < M; ++i) {
        for (int v = 0; v < counts[i]; ++v) {
            // 値iにv枚置いたとき、残りの(M-i)種類で(remaining_N - v)枚を分ける方法数
            rank += nCr_multi(M - i, remaining_N - v);
        }
        remaining_N -= counts[i];
    }
    return rank;
}

vector<int> rank_to_hand(ll rank, int N, int M) {
    vector<int> counts(M + 1, 0);
    int remaining_N = N;
    for (int i = 1; i < M; ++i) {
        for (int v = 0; v <= remaining_N; ++v) {
            ll ways = nCr_multi(M - i, remaining_N - v);
            if (rank < ways) {
                counts[i] = v;
                remaining_N -= v;
                break;
            }
            rank -= ways;
        }
    }
    counts[M] = remaining_N;
    return counts;
}

vector<int> rank_to_perm(ll rank, int M) {
    vector<ll> fact(M + 1, 1);
    for (int i = 2; i <= M; ++i) fact[i] = fact[i - 1] * i;

    vector<int> elements(M);
    iota(elements.begin(), elements.end(), 1);
    vector<int> perm;
    for (int i = M - 1; i >= 0; --i) {
        int idx = rank / fact[i];
        perm.push_back(elements[idx]);
        elements.erase(elements.begin() + idx);
        rank %= fact[i];
    }
    return perm;
}

ll perm_to_rank(const vector<int>& perm, int M) {
    vector<ll> fact(M + 1, 1);
    for (int i = 2; i <= M; ++i) fact[i] = fact[i - 1] * i;

    vector<int> elements(M);
    iota(elements.begin(), elements.end(), 1);
    ll rank = 0;
    for (int i = 0; i < M; ++i) {
        auto it = find(elements.begin(), elements.end(), perm[i]);
        int idx = distance(elements.begin(), it);
        rank += (ll)idx * fact[M - 1 - i];
        elements.erase(it);
    }
    return rank;
}

int main() {
    init_comb();
    int my_id, N, M;
    if (!(cin >> my_id >> N >> M)) return 0;

    vector<int> my_hand_counts(M + 1, 0);
    for (int i = 0; i < N; ++i) {
        int c; cin >> c;
        my_hand_counts[c]++;
    }

    ll my_rank = hand_to_rank(my_hand_counts, N, M);
    vector<int> my_ask_order = rank_to_perm(my_rank, M);

    vector<int> total_counts(M + 1, 0);
    vector<int> other_ask_order;
    int my_turn_idx = 0;

    for (int q = 0; q < 2 * M; ++q) {
        string status; cin >> status;
        if (status == "TURN") {
            cout << "ASK " << my_ask_order[my_turn_idx++] << endl;
        }
        //else if (status == "WAIT") {

        string res; int x, k;
        cin >> res >> x >> k; // COUNT X K
        total_counts[x] = k;
        if ((my_id == 1 && q % 2 == 1) || (my_id == 2 && q % 2 == 0)) {
            other_ask_order.push_back(x);
        }
    }

    ll other_rank = perm_to_rank(other_ask_order, M);
    vector<int> other_hand_counts = rank_to_hand(other_rank, N, M);

    vector<int> c_hand;
    for (int v = 1; v <= M; ++v) {
        int c_count = total_counts[v] - my_hand_counts[v] - other_hand_counts[v];
        for (int i = 0; i < c_count; ++i) c_hand.push_back(v);
    }

    for (int i = 0; i < 2; ++i) {
        string status; cin >> status;
        if (status == "TURN") {
            cout << "GUESS";
            for (int val : c_hand) cout << " " << val;
            cout << endl;
        }
        string res; int id, ok;
        cin >> res >> id >> ok; // GUESSED id ok
    }

    int final_q; string end_tag;
    cin >> end_tag >> final_q;

    return 0;
}