#1157296 (Java) No.3496 協力カード当て

• 問題: No.3496 協力カード当て
• ユーザー: yuki2006
• 提出日時: 2026-04-14 20:57:04
• 言語: Java (openjdk 25.0.2)
• 結果: AC
• 実行時間: 245 ms / 2,000 ms
• コード長: 4,351 bytes
• コンパイル時間: 5,517 ms
• コンパイル使用メモリ: 84,504 KB
• 実行使用メモリ: 68,080 KB
• スコア: 132
• 平均クエリ数: 40.00
• 最終ジャッジ日時: 2026-04-14 23:50:23
• 合計ジャッジ時間: 15,868 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

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

ソースコード

 import java.util.*;
  import java.io.*;

  public class Main {
      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];
          List<Integer> avail = new ArrayList<>();
          for (int i = 1; i <= M; i++) avail.add(i);
          int p = 0;
          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[p++] = avail.get(q);
              avail.remove(q);
          }
          return perm;
      }

      static long decodePerm(int[] perm, int M) {
          long idx = 0;
          List<Integer> avail = new ArrayList<>();
          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 = avail.indexOf(perm[M - i]);
              idx += (long) q * f;
              avail.remove(q);
          }
          return idx;
      }

      public static void main(String[] args) {
          Scanner sc = new Scanner(System.in);
          PrintWriter out = new PrintWriter(new BufferedWriter(new
  OutputStreamWriter(System.out)));

          int id = sc.nextInt();
          int N = sc.nextInt();
          int M = sc.nextInt();

          int[] myCount = new int[M];
          for (int i = 0; i < N; i++) {
              int v = sc.nextInt();
              myCount[v - 1]++;
          }

          int[] qorder = encodePerm(rankMultiset(myCount, N, M), M);

          int qpos = 0;
          List<Integer> oppQueries = new ArrayList<>();
          int[] total = new int[20];
          boolean afterWait = false;

          while (sc.hasNext()) {
              String cmd = sc.next();
              if (cmd.equals("END")) {
                  sc.nextInt();
                  break;
              } else if (cmd.equals("TURN")) {
                  afterWait = false;
                  if (qpos < M) {
                      out.println("ASK " + qorder[qpos++]);
                      out.flush();
                  } else {
                      int[] oppArr = new int[oppQueries.size()];
                      for (int i = 0; i < oppArr.length; i++) oppArr[i] = oppQueries.get(i);
                      int[] oppCount = unrankMultiset(decodePerm(oppArr, M), N, M);
                      StringBuilder sb = new StringBuilder("GUESS");
                      for (int v = 0; v < M; v++) {
                          int c = total[v + 1] - myCount[v] - oppCount[v];
                          for (int j = 0; j < c; j++) sb.append(' ').append(v + 1);
                      }
                      out.println(sb);
                      out.flush();
                  }
              } else if (cmd.equals("WAIT")) {
                  afterWait = true;
              } else if (cmd.equals("COUNT")) {
                  int x = sc.nextInt();
                  int k = sc.nextInt();
                  total[x] = k;
                  if (afterWait) {
                      oppQueries.add(x);
                      afterWait = false;
                  }
              } else if (cmd.equals("GUESSED")) {
                  sc.nextInt();
                  sc.nextInt();
              }
          }
      }
  }