Codeforces Round #385 (Div. 1) B. Hongcow's Game

問題

http://codeforces.com/contest/744/problem/B

n x n の行列があります。行列の要素は全て非負整数で、対角成分はすべて0です。この行列に対して、n以下の自然数の集合Sをクエリとして投げると、各行についてとなる x 列目の要素のうち最小のものを返します。20クエリ以内で各行の対角成分以外の最小値を求めてください。

解法

集合Sをクエリとして投げた時に返ってくる数列 のうち、 は i 行目の最小値である可能性があります。つまり、j 行目の最小値が知りたいときは j を含まない集合 S をいくつか作り、かつ、それらの和集合が j 以外の全ての n 以下の自然数を含むようにしなければなりません。

を j と i ビット目が異なる自然数の集合とします。

は j を含みませんが、j 以外の 10 ビット以下のすべての自然数を含みます。n は 1000 以下で 10 ビット以内に収まるので、各jについて上記のような和集合をクエリとして投げれば良いです。

コード

import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;
import java.util.TreeSet;

public class B {
  private void solve(Scanner in, PrintWriter out) {
    int N = in.nextInt();
    int[] ans = new int[N];
    Arrays.fill(ans, Integer.MAX_VALUE);
    TreeSet<Integer>[] sets = new TreeSet[2];
    for (int i = 0; i < 2; i++) sets[i] = new TreeSet<>();
    for (int i = 0; i < 10; i++) {
      sets[0].clear();
      sets[1].clear();
      for (int j = 0; j < N; j++) {
        sets[(j >> i) & 1].add(j);
      }

      if (!sets[0].isEmpty()) {
        query(sets[0]);
        read(sets[0], ans, in);
      }

      if (!sets[1].isEmpty()) {
        query(sets[1]);
        read(sets[1], ans, in);
      }
    }

    System.out.println(-1);
    for (int a : ans) System.out.print(a + " ");
    System.out.println();
  }

  private void query(TreeSet<Integer> s) {
    System.out.println(s.size());
    for (int a : s) System.out.print((a + 1) + " ");
    System.out.println();
  }

  private void read(TreeSet<Integer> s, int[] ans, Scanner in) {
    int N = ans.length;
    for (int j = 0; j < N; j++) {
      int x = in.nextInt();
      if (!s.contains(j)) ans[j] = Math.min(ans[j], x);
    }
  }

  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);
    new B().solve(in, out);
    in.close();
    out.close();
  }
}