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

• 問題: No.3496 協力カード当て
• ユーザー: yuki2006
• 提出日時: 2026-04-06 22:06:41
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 71 ms / 2,000 ms
• コード長: 3,911 bytes
• コンパイル時間: 623 ms
• コンパイル使用メモリ: 96,144 KB
• 実行使用メモリ: 30,064 KB
• スコア: 132
• 平均クエリ数: 40.00
• 最終ジャッジ日時: 2026-04-14 23:48:20
• 合計ジャッジ時間: 3,045 ms
• ジャッジサーバーID （参考情報）: <nil> / judge1_1

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

ソースコード

/**
 * カード推理問題 AC解法
 *
 * 戦略: 質問順序で自分の手札をエンコード
 * - 手札 (count[1]..count[M]) を多重集合のランクに変換
 * - ランクを階乗進法で 1..M の順列にエンコード
 * - その順列の順に ASK → 相手は質問順序をデコードして手札を復元
 * - C[v] = total[v] - A[v] - B[v] で確定
 * - 質問数: 2M (各プレイヤー M 回)
 */
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

long long comb(int n, int r) {
    if (r < 0 || n < 0 || r > n) return 0;
    if (r == 0) return 1;
    if (r > n - r) r = n - r;
    long long res = 1;
    for (int i = 0; i < r; i++) res = res * (n - i) / (i + 1);
    return res;
}

long long rank_multiset(vector<int>& c, int N, int M) {
    long long r = 0;
    int rem = N;
    for (int i = 0; i < M; i++) {
        for (int v = 0; v < c[i]; v++)
            r += comb(rem - v + M - i - 2, M - i - 2);
        rem -= c[i];
    }
    return r;
}

vector<int> unrank_multiset(long long idx, int N, int M) {
    vector<int> c(M, 0);
    int rem = N;
    for (int i = 0; i < M; i++) {
        if (i == M - 1) { c[i] = rem; break; }
        for (int v = 0; v <= rem; v++) {
            long long cnt = comb(rem - v + M - i - 2, M - i - 2);
            if (idx < cnt) { c[i] = v; rem -= v; break; }
            idx -= cnt;
        }
    }
    return c;
}

vector<int> encode_perm(long long idx, int M) {
    vector<int> perm, avail;
    for (int i = 1; i <= M; i++) avail.push_back(i);
    for (int i = M; i >= 1; i--) {
        long long f = 1;
        for (int j = 1; j < i; j++) f *= j;
        int q = idx / f;
        idx %= f;
        perm.push_back(avail[q]);
        avail.erase(avail.begin() + q);
    }
    return perm;
}

long long decode_perm(vector<int>& perm, int M) {
    long long idx = 0;
    vector<int> avail;
    for (int i = 1; i <= M; i++) avail.push_back(i);
    for (int i = M; i >= 1; i--) {
        long long f = 1;
        for (int j = 1; j < i; j++) f *= j;
        auto it = find(avail.begin(), avail.end(), perm[M - i]);
        idx += (it - avail.begin()) * f;
        avail.erase(it);
    }
    return idx;
}

int main() {
    int id, N, M;
    scanf("%d %d %d", &id, &N, &M);

    vector<int> my_count(M, 0);
    for (int i = 0; i < N; i++) {
        int v; scanf("%d", &v);
        my_count[v - 1]++;
    }

    // 自分の手札をランク→順列にエンコード
    vector<int> qorder = encode_perm(rank_multiset(my_count, N, M), M);

    int qpos = 0;
    vector<int> opp_queries;
    int total[20] = {};
    bool after_wait = false;

    char cmd[16];
    while (scanf("%s", cmd) == 1) {
        if (strcmp(cmd, "END") == 0) { int q; scanf("%d", &q); break; }
        if (strcmp(cmd, "TURN") == 0) {
            after_wait = false;
            if (qpos < M) {
                printf("ASK %d\n", qorder[qpos++]);
                fflush(stdout);
            } else {
                // 相手の手札をデコード
                vector<int> opp_count = unrank_multiset(
                    decode_perm(opp_queries, M), N, M);
                // C = total - mine - opponent
                printf("GUESS");
                for (int v = 0; v < M; v++) {
                    int c = total[v + 1] - my_count[v] - opp_count[v];
                    for (int j = 0; j < c; j++) printf(" %d", v + 1);
                }
                printf("\n");
                fflush(stdout);
            }
        } else if (strcmp(cmd, "WAIT") == 0) {
            after_wait = true;
        } else if (strcmp(cmd, "COUNT") == 0) {
            int x, k; scanf("%d %d", &x, &k);
            total[x] = k;
            if (after_wait) { opp_queries.push_back(x); after_wait = false; }
        } else if (strcmp(cmd, "GUESSED") == 0) {
            int g, ok; scanf("%d %d", &g, &ok);
        }
    }
    return 0;
}