/** * カード推理問題 AC解法 * * 戦略: 質問順序で自分の手札をエンコード * - 手札 (count[1]..count[M]) を多重集合のランクに変換 * - ランクを階乗進法で 1..M の順列にエンコード * - その順列の順に ASK → 相手は質問順序をデコードして手札を復元 * - C[v] = total[v] - A[v] - B[v] で確定 * - 質問数: 2M (各プレイヤー M 回) */ #include #include #include #include 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& 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 unrank_multiset(long long idx, int N, int M) { vector 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 encode_perm(long long idx, int M) { vector 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& perm, int M) { long long idx = 0; vector 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 my_count(M, 0); for (int i = 0; i < N; i++) { int v; scanf("%d", &v); my_count[v - 1]++; } // 自分の手札をランク→順列にエンコード vector qorder = encode_perm(rank_multiset(my_count, N, M), M); int qpos = 0; vector 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 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; }