AOJ2410 Janken

問題リンク Janken

• 解法

すっげぇ強い手の集合を作って、その中から適当に出せば350点くらい稼げるだろう、というのが方針です。
強い手の集合は次のようにして作ってみました

集合のどれかの手を使えば、全ての手に対して負けない(あいこか勝ちになる)
上を満たす集合の中で要素数最小のもの

とりあえず相手がどの手を出しても1点以上稼げる可能性を残すのが最初の条件で、それに2番目の条件を加えると"o"の多い手(強い手)が集まるかなーという魂胆です。
この集合を求めたら、ランダムに集合内の手を選んで出力します。

• ソース

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.Scanner;

//Janken
public class AOJ2410 {

	void run(){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		char[][] a = new char[N][N];
		for(int i=0;i<N;i++)a[i]=sc.next().toCharArray();
		int min = N+1, cand = 0;
		boolean[] win = new boolean[N];
		for(int S=1;S<1<<N;S++){
			int c = Integer.bitCount(S);
			if(min<=c)continue;
			Arrays.fill(win, false);
			for(int j=0;j<N;j++)if(((S>>j)&1)>0){
				for(int i=0;i<N;i++)win[i]|=a[j][i]!='x';
			}
			boolean ok = true;
			for(boolean v:win)ok&=v;
			if(ok){
				min = c; cand = S;
			}
		}
		List<Integer> use = new ArrayList<Integer>();
		for(int i=0;i<N;i++)if(((cand>>i)&1)>0)use.add(i);
		Random rand = new Random();
		for(int i=0;i<1000;i++){
			int me = use.get(rand.nextInt(use.size()));
			System.out.println(me+1);
			System.out.flush();
			sc.nextInt();
		}
	}
	
	public static void main(String[] args) {
		new AOJ2410().run();
	}
}