SRM 637 Div. 1 Easy: GreaterGame

問題

TopCoder Statistics - Problem Statement

snukeさん

解法

見えている部分については、勝てるカードがあればできるだけ小さいカードで勝ち、勝てない時は小さいカードで負けるようにする。見えていない部分はどうしようもないので期待値を出す。

コード

import java.util.ArrayList;
import java.util.Arrays;

public class GreaterGame {

	public double calc(int[] hand, int[] sothe) {
		int N = hand.length;
		Arrays.sort(hand);
		Arrays.sort(sothe);
		double point = 0;
		boolean[] used = new boolean[N];
		for (int i = 0; i < sothe.length; i++) {
			if (sothe[i] <= 0) {
				continue;
			}

			for (int j = 0; j < hand.length; j++) {
				if (!used[j] && hand[j] > sothe[i]) {
					used[j] = true;
					point += 1.0;
					break;
				}
				if (j == hand.length - 1) {
					for (int k = 0; k < hand.length; k++) {
						if (!used[k]) {
							used[k] = true;
							break;
						}
					}
				}
			}
		}

		boolean[] revealed = new boolean[2 * N];
		for (int i = 0; i < N; i++) {
			revealed[hand[i] - 1] = true;
			if (sothe[i] > 0) {
				revealed[sothe[i] - 1] = true;
			}
		}

		ArrayList<Integer> unrevealed = new ArrayList<>();
		for (int i = 0; i < revealed.length; i++) {
			if (!revealed[i]) {
				unrevealed.add(i + 1);
			}
		}

		for (int i = 0; i < used.length; i++) {
			if (!used[i]) {
				for (Integer sothe_j : unrevealed) {
					if (hand[i] > sothe_j) {
						point += 1.0 / unrevealed.size();
					}
				}
			}
		}
		return point;
	}
}