#1156767 (C#) No.3496 協力カード当て

• 問題: No.3496 協力カード当て
• ユーザー: yuki2006
• 提出日時: 2026-04-07 20:27:49
• 言語: C# (.NET 10.0.201)
• 結果: AC
• 実行時間: 175 ms / 2,000 ms
• コード長: 4,083 bytes
• コンパイル時間: 17,211 ms
• コンパイル使用メモリ: 175,108 KB
• 実行使用メモリ: 52,776 KB
• スコア: 132
• 平均クエリ数: 40.00
• 最終ジャッジ日時: 2026-04-14 23:48:42
• 合計ジャッジ時間: 22,102 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

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

コンパイルメッセージ

  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (149 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net10.0/main.dll
  main -> /home/judge/data/code/bin/Release/net10.0/publish/

ソースコード

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static 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 res = 1;
        for (int i = 0; i < r; i++) res = res * (n - i) / (i + 1);
        return res;
    }

    static long RankMultiset(int[] c, int N, int M)
    {
        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;
    }

    static int[] UnrankMultiset(long idx, int N, int M)
    {
        int[] c = new int[M];
        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 cnt = Comb(rem - v + M - i - 2, M - i - 2);
                if (idx < cnt) { c[i] = v; rem -= v; break; }
                idx -= cnt;
            }
        }
        return c;
    }

    static int[] EncodePerm(long idx, int M)
    {
        int[] perm = new int[M];
        var avail = new List<int>();
        for (int i = 1; i <= M; i++) avail.Add(i);
        for (int i = M; i >= 1; i--)
        {
            long f = 1;
            for (int j = 1; j < i; j++) f *= j;
            int q = (int)(idx / f);
            idx %= f;
            perm[M - i] = avail[q];
            avail.RemoveAt(q);
        }
        return perm;
    }

    static long DecodePerm(List<int> perm, int M)
    {
        long idx = 0;
        var avail = new List<int>();
        for (int i = 1; i <= M; i++) avail.Add(i);
        for (int i = M; i >= 1; i--)
        {
            long f = 1;
            for (int j = 1; j < i; j++) f *= j;
            int pos = avail.IndexOf(perm[M - i]);
            idx += pos * f;
            avail.RemoveAt(pos);
        }
        return idx;
    }

    static void Main()
    {
        var line1 = Console.ReadLine().Split();
        int id = int.Parse(line1[0]);
        int N = int.Parse(line1[1]);
        int M = int.Parse(line1[2]);

        var handTokens = Console.ReadLine().Split();
        int[] myCount = new int[M];
        for (int i = 0; i < N; i++)
            myCount[int.Parse(handTokens[i]) - 1]++;

        int[] qorder = EncodePerm(RankMultiset(myCount, N, M), M);

        int qpos = 0;
        var oppQueries = new List<int>();
        int[] total = new int[M + 1];
        bool afterWait = false;

        string line;
        while ((line = Console.ReadLine()) != null)
        {
            var parts = line.Split();
            if (parts[0] == "END") break;

            if (parts[0] == "TURN")
            {
                afterWait = false;
                if (qpos < M)
                {
                    Console.WriteLine("ASK " + qorder[qpos++]);
                    Console.Out.Flush();
                }
                else
                {
                    int[] oppCount = UnrankMultiset(DecodePerm(oppQueries, M), N, M);
                    var guess = new List<int>();
                    for (int v = 0; v < M; v++)
                    {
                        int c = total[v + 1] - myCount[v] - oppCount[v];
                        for (int j = 0; j < c; j++) guess.Add(v + 1);
                    }
                    guess.Sort();
                    Console.WriteLine("GUESS " + string.Join(" ", guess));
                    Console.Out.Flush();
                }
            }
            else if (parts[0] == "WAIT")
            {
                afterWait = true;
            }
            else if (parts[0] == "COUNT")
            {
                int x = int.Parse(parts[1]);
                int k = int.Parse(parts[2]);
                total[x] = k;
                if (afterWait) { oppQueries.Add(x); afterWait = false; }
            }
            else if (parts[0] == "GUESSED")
            {
                // nothing
            }
        }
    }
}