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

• 問題: No.3496 協力カード当て
• ユーザー: 👑 sgfc
• 提出日時: 2026-04-15 05:09:02
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 52 ms / 2,000 ms
• コード長: 5,345 bytes
• コンパイル時間: 2,467 ms
• コンパイル使用メモリ: 343,316 KB
• 実行使用メモリ: 30,320 KB
• スコア: 231
• 平均クエリ数: 27.62
• 最終ジャッジ日時: 2026-04-15 05:09:12
• 合計ジャッジ時間: 6,805 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_1

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

ソースコード

#include "bits/stdc++.h"

using namespace std;
using ll = long long;

#define OVERLOAD3(_1, _2, _3, call,...) call
#define REP1(i, n) for (ll i = 0; i < ll(n); ++i)
#define REP2(i, a, b) for (ll i = ll(a); i < ll(b); ++i)
#define REP(...) OVERLOAD3(__VA_ARGS__, REP2, REP1)(__VA_ARGS__)
#define RREP1(i, n) for (ll i = ll(n) - 1; i >= 0; --i)
#define RREP2(i, a, b) for (ll i = ll(a) - 1; i >= b; --i)
#define RREP(...) OVERLOAD3(__VA_ARGS__, RREP2, RREP1)(__VA_ARGS__)
#define REPE(i, c) for (auto&& i : c)
#define TCASE() ll _ttt; cin >> _ttt; while(_ttt--)

ll dp[12][19];

void init_dp(int n, int m) {
	memset(dp, 0, sizeof(dp));
	dp[0][0] = 1;
    REP(i, 1, m + 1) {
        REP(j, n + 1) {
            REP(k, min(i, j) + 1) {
                dp[i][j] += dp[i - 1][j - k];
            }
        }
    }
}

ll get_rk(const vector<int>& hand_counts, int n, int m) {
    ll rk = 0;
    int rem = n;
    for (int i = m; i >= 1; --i) {
        int c = hand_counts[i];
        for (int k = 0; k < c; ++k) {
			rk += dp[i-1][rem - k];
		}
		rem -= c;
    }
    return rk;
}

vector<int> rank_to_hand(ll rank, int n, int m) {
    vector<int> counts(m + 1, 0);
    int rem_n = n;
    for (int i = m; i >= 1; --i) {
        for (int k = 0; k <= min(i, rem_n); ++k) {
            ll ways = dp[i - 1][rem_n - k];
            if (rank >= ways) {
                rank -= ways;
            }
            else {
                counts[i] = k;
                rem_n -= k;
                break;
            }
        }
    }
    return counts;
}

int main() {
    int id, n, m;
	cin >> id >> n >> m;

	init_dp(n, m);
	vector<int> hand_counts(m + 1, 0);
    for (int i = 0; i < n; ++i) {
        int c; cin >> c;
        hand_counts[c]++;
	}

	ll my_rk = get_rk(hand_counts, n, m);
	ll max_rk = dp[m][n];

    ll q = 0;
    ll qc = 1;
    while (qc < max_rk) {
        qc *= m;
		q++;
    }

    vector<int> query(q, 0);
	ll tmp = my_rk;
    REP(i, q) {
        query[i] = tmp % m;
        tmp /= m;
	}

	vector<int> other_query;
    vector<int> total_counts(m + 1, -1);
    vector<int> other_counts(m + 1, 0);
    int turn_idx = 0;
    bool decode_other = false;
	bool guessed = false;

    while (true) {
        string action;
        if (!(cin >> action)) break;

        if (action == "END") {
            int final_q;
            cin >> final_q;
            break;
        }

        if (action == "TURN") {
            if (other_query.size() == q && !decode_other) {
                ll other_rank = 0;
                ll mult = 1;
                for (int i = 0; i < q; ++i) {
                    other_rank += (ll)other_query[i] * mult;
                    mult *= m;
                }
                other_counts = rank_to_hand(other_rank, n, m);
                decode_other = true;
            }

            int next_ask = -1;
            if (turn_idx < q) {
                next_ask = query[turn_idx] + 1;
            }
            else {
                ll sum = 0;
                ll m1count = 0;

                for (int i = 1; i <= m; ++i) {
                    if (total_counts[i] != -1) {
                        sum += total_counts[i];
                    }
                    else {
                        m1count++;
                    }
                }

                if (sum == 3 * n) {
                    for (int i = 1; i <= m; ++i) {
                        if (total_counts[i] == -1) total_counts[i] = 0;
                    }
                }
                else if (m1count == 1) {
                    for (int i = 1; i <= m; ++i) {
                        if (total_counts[i] == -1) {
                            total_counts[i] = 3 * n - sum;
                            break;
                        }
                    }
                }
                else {
                    for (int i = 1; i <= m; ++i) {
                        if (total_counts[i] == -1) {
                            next_ask = i;
                            break;
                        }
					}
                }
            }

            if (next_ask != -1) {
                cout << "ASK " << next_ask << endl;
            }
            else {
                if (!guessed) {
                    vector<int> c_hand;
                    for (int i = 1; i <= m; ++i) {
                        int c = total_counts[i] - hand_counts[i] - other_counts[i];
                        for (int k = 0; k < c; ++k) c_hand.push_back(i);
                    }

                    cout << "GUESS";
                    for (int v : c_hand) cout << " " << v;
                    cout << endl;
                    guessed = true;
                }
            }
        }

        if (action == "TURN" || action == "WAIT") {
            string res;
            cin >> res;
            if (res == "COUNT") {
                int x, k;
                cin >> x >> k;
                total_counts[x] = k;
                if (action == "TURN") {
                    turn_idx++;
                }
                else if (action == "WAIT") {
                    if (other_query.size() < q) {
                        other_query.push_back(x - 1);
                    }
                }
            }
            else if (res == "GUESSED") {
                int id, ok;
                cin >> id >> ok;
            }
        }
    }

    return 0;
}