CEDEC_AI_CHALLENGE2014決勝用プログラム

compile.sh

javac -encoding UTF8 *.java

ProbAI.java

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

//確定でない部の期待値を、熱狂度で重み付けしているバージョン
//重みが熱狂度の2乗に比例してるバージョン
//さらに、3〜7ターン目において、nターン目に、残りの使える好感度の(n+2)割以上使わないとダメな場合はターゲットから外す。
public class ProbAI {
	static int MaxTurn, Turn, PlayersNum, JoshisNum, CanGet, CanGet2, CanGet_after_next, Left_turn, NotKaburi, DatedCount, NowSum;
	static char Day;
	static Joshi[] Joshis;

	static int[] WeightArray;
	static int[] WeightArray2;


	static final Scanner scanner = new Scanner(System.in);
	static final PrintWriter writer = new PrintWriter(System.out, true);


	public static void main(String[] args) {
		writer.println("READY");
		readInitialData();
		boolean canchoose = false;
		for (int t = 0; t < MaxTurn; t++) {
			readData();
			updateTarget();

			updateRank();

			updateNeed();
			
			for(int tt = 0; tt < JoshisNum; tt++){
				if(Joshis[tt].target){
					canchoose = true;
					break;
				}
			}

			if(Turn==2){
				writeCommand_second();
			}else if(canchoose){
				if(Turn%2==1){
					writeCommand_W();
				}else{
					writeCommand_H();
				}
			}else{
				write7();
			}
		}	
		scanner.close();
		writer.close();
	}

	static void readInitialData() {
		MaxTurn = scanner.nextInt();
		PlayersNum = scanner.nextInt();
		JoshisNum = scanner.nextInt();
		Joshis = new Joshi[JoshisNum];
		WeightArray = new int[JoshisNum+1];
		WeightArray2 = new int[JoshisNum+1];
		WeightArray[0] = 0;
		WeightArray2[0] = 0;
		int sum_of_weight = 0;
		int sum_of_weight2 = 0;
		NotKaburi = 0;
		DatedCount = 0;
		for (int i = 0; i < JoshisNum; i++) {
			int enthusiasm = scanner.nextInt();
			sum_of_weight += enthusiasm;
			sum_of_weight2 += enthusiasm * enthusiasm;
			WeightArray[i+1] = sum_of_weight;
			WeightArray2[i+1] = sum_of_weight2;
			Joshi h = new Joshi(enthusiasm);
			Joshis[i] = h;
			Joshis[i].target = true;
			Joshis[i].holiday_max = 0;
			Joshis[i].holiday_kakutei = 0;
			Joshis[i].holiday_kitaichi = 0;
			Joshis[i].holiday_min = 0;
			Joshis[i].need_now = 0;
		}
	}

	static void readData() {
		Turn = scanner.nextInt();
		Day = scanner.next().charAt(0);
		NotKaburi = 0;
		DatedCount = 0;
		NowSum = 0;
		for (int i = 0; i < JoshisNum; i++) {
			int[] revealedScore = new int[PlayersNum];
			for (int j = 0; j < PlayersNum; j++) {
				revealedScore[j] = scanner.nextInt();
			}
			Joshis[i].revealedScore = revealedScore;
		}
		for (int i = 0; i < JoshisNum; i++) {
			int realScore = scanner.nextInt();
			Joshis[i].realScore = realScore;
		}
		
		int my_choice_count = 0;
		if (Day == 'W') {
			for (int i = 0; i < JoshisNum; i++) {
				if(Joshis[i].my_choice){my_choice_count++;}
				int dated = scanner.nextInt();
				Joshis[i].dated = (dated == 1);
				if(Joshis[i].dated && !Joshis[i].my_choice){
					NotKaburi++;
					DatedCount++;
					NowSum = NowSum + WeightArray[i+1] - WeightArray[i];
				}else if(Joshis[i].dated){
					DatedCount++;
					NowSum = NowSum + WeightArray[i+1] - WeightArray[i];
				}
			}
		
			if(NotKaburi >= 6){
				for(int i = 0; i < JoshisNum; i++){
					if(Joshis[i].dated && !Joshis[i].my_choice){
						Joshis[i].holiday_kakutei += 2;
					}
				}
			}else{
				for(int i = 0; i < JoshisNum; i++){
					if(Joshis[i].dated){
						// Joshis[i].holiday_kitaichi += 4 / DatedCount;
						//(WeightArray[i+1]-WeightArray[i])はi番目の女性の熱狂度を
						 // (WeightArray[8] / 8)は全女性の熱狂度の平均を表している。
						Joshis[i].holiday_kitaichi += 4 * ((WeightArray[i+1]-WeightArray[i]) / NowSum);						
					}
				}
			}

			for(int i = 0; i < JoshisNum; i++){
				Joshis[i].holiday_sum = Joshis[i].holiday_kakutei + Joshis[i].holiday_kitaichi;
			}
		}

		CanGet2 = 0;
		Left_turn = 11 - Turn;
		CanGet = (Left_turn / 2) * 9 + (Left_turn % 2) * 4;
		if(3 <= Turn && Turn <= 7){
			CanGet2 = (CanGet * (Turn+2)) / 10;
		}else{
			CanGet2 = CanGet;
		}

		Left_turn--;
		CanGet_after_next = (Left_turn / 2) * 9 + (Left_turn % 2) * 4;
	}

//さらに、3〜7ターン目において、nターン目に、残りの使える好感度の(n+2)割以上使わないとダメな場合はターゲットから外す。
//Canget2が、その何割かの調整分にあたる。
	static void updateTarget() {
		boolean check1 = false;
		boolean check2 = false;

		for(int i = 0; i < JoshisNum; i++){
			Joshis[i].target =true;
		}


//1位(おそらく)確定なら、その女の子は狙わない(狙わない=false)
		for(int i = 0; i < JoshisNum; i++){
			check1 = false;
			for(int j = 0; j < PlayersNum; j++){
				if(Joshis[i].realScore <= Joshis[i].revealedScore[j] + Joshis[i].holiday_sum + CanGet){
					check1 = true;
					break;
				}
			}
			Joshis[i].target = check1;
		}

//4位確定なら、その女の子は狙わない
		for(int i = 0; i < JoshisNum; i++){
			if(!Joshis[i].target){continue;}
			check1 = false;
			for(int j = 0; j < PlayersNum; j++){
				if(Joshis[i].realScore + CanGet2 >= Joshis[i].revealedScore[j] + Joshis[i].holiday_sum){
					check1 = true;
					break;
				}
			}
			Joshis[i].target = check1;
		}

//2or3位確定なら、その女の子は狙わない
//check1が、絶対自分に追いつけない相手がいるかどうか(いるならfalse)
//check2が、絶対自分が追いつけない相手がいるかどうか(いるならfalse)
		for(int i = 0; i < JoshisNum; i++){
			if(!Joshis[i].target){continue;}
			check1 = true;
			check2 = true;
			for(int j = 0; j < PlayersNum; j++){
				if(Joshis[i].realScore > Joshis[i].revealedScore[j] + CanGet + Joshis[i].holiday_sum){
					check1 = false;
				}else if(Joshis[i].realScore + CanGet < Joshis[i].revealedScore[j] + Joshis[i].holiday_sum){
					check2 = false;
				}
			}
			Joshis[i].target = (check1 && check2);
		}

	}

//現在の順位。1か4位が確定ならそれを、そうでないなら2をつける。
	static void updateRank() {
		for(int i = 0; i < JoshisNum; i++){
			boolean check = true;
			for(int j = 0; j < PlayersNum; j++){
				if(Joshis[i].realScore <= Joshis[i].revealedScore[j] + Joshis[i].holiday_max){
					check = false;
					break;
				}
			}
			if(check){
				Joshis[i].my_rank = 1;
				continue;
			}
			check = true;
			for(int j = 0; j < PlayersNum; j++){
				if(Joshis[i].realScore >= Joshis[i].revealedScore[j] + Joshis[i].holiday_min){
					check = false;
					break;
				}
			}
			if(check){
				Joshis[i].my_rank = 4;
			}else{
				Joshis[i].my_rank = 2;
			}
		}
	}


	static void updateNeed() {
//まだ諦めていない(つまりtarget=trueとなっている)女の子に対して、今週は最低これくらいいかないと意味ないっすよ->need_now
		for(int i = 0; i < JoshisNum; i++){
			if(!Joshis[i].target){continue;}
			int need = 45;
			if(Joshis[i].my_rank==2){
				Joshis[i].need_now = 0;
				continue;
			}else if(Joshis[i].my_rank==1){
				for(int j = 0; j < PlayersNum; j++){
					if(Joshis[i].realScore - Joshis[i].revealedScore[j] - Joshis[i].holiday_max < need){
						need = Joshis[i].realScore - Joshis[i].revealedScore[j] - Joshis[i].holiday_max;
					}
				}
				Joshis[i].need_now = need;
			}else{
				for(int j = 0; j < PlayersNum; j++){
					if(Joshis[i].revealedScore[j] + Joshis[i].holiday_min - Joshis[i].realScore < need){
						need = Joshis[i].revealedScore[j] + Joshis[i].holiday_min - Joshis[i].realScore + 1;
					}
				}
				Joshis[i].need_now = need;
			}
		}
	}
/*
	static void writeCommand() {
		for(int i = 0; i < JoshisNum; i++){
			Joshis[i].my_choice = false;
		}
		StringBuilder command = new StringBuilder();
		Random random = new Random();
		for (int i = 0; i < (Day == 'W' ? 5 : 2); i++) {
			int c = random.nextInt(JoshisNum);
			command.append(c);
			Joshis[i].my_choice = true;
			if (i < 4) {
				command.append(" ");
			}
		}
		writer.println(command.toString());
	}
*/

	static void writeCommand_W_kako() {
		for(int i = 0; i < JoshisNum; i++){
			Joshis[i].my_choice = false;
		}
		StringBuilder command = new StringBuilder();
		Random random = new Random();
		for(int i = 0; i < 5; i++){
			boolean clear = false;
			int kouho = 0;
			while(!clear){
				int c = random.nextInt(WeightArray[JoshisNum]);
				for(int ind = 0; ind < JoshisNum; ind++){
					if(WeightArray[ind] <= c && c < WeightArray[ind+1]){
						kouho = ind;
						break;
					}
				}
				if(Joshis[kouho].target){
					clear = true;
				}
			}
			Joshis[kouho].my_choice = true;
			command.append(kouho);
			if(i < 4){
				command.append(" ");
			} 
		}
		writer.println(command.toString());
	}


	static void writeCommand_W() {
		int[] chosen_Joshi = new int[JoshisNum];
		for(int i = 0; i < JoshisNum; i++){
			Joshis[i].my_choice = false;
		}
		StringBuilder command = new StringBuilder();
		Random random = new Random();
		boolean check = false;

		while(!check){
			for(int i = 0; i < JoshisNum; i++){
				chosen_Joshi[i] = 0;
			}
			for(int i = 0; i < 5; i++){
				boolean clear = false;
				int kouho = 0;

				while(!clear){
					int c = random.nextInt(WeightArray[JoshisNum]);
					for(int ind = 0; ind < JoshisNum; ind++){
						if(WeightArray[ind] <= c && c < WeightArray[ind+1]){
							kouho = ind;
							break;
						}
					}
					if(Joshis[kouho].target){
						clear = true;
						chosen_Joshi[kouho] = chosen_Joshi[kouho] + 1;
					}
				}
			}
			boolean  fill_need = true;
			for(int i = 0; i < JoshisNum; i++){
				if(chosen_Joshi[i] > 0 && chosen_Joshi[i] < Joshis[i].need_now){
					fill_need = false;
					break;
				}
			}
			if(fill_need){
				check = true;
			}
		}

		for(int i = 0; i < JoshisNum; i++){
			while(chosen_Joshi[i] > 0){
				Joshis[i].my_choice = true;
				chosen_Joshi[i]--;
				command.append(i);
				command.append(" ");
			}
		}

		writer.println(command.toString());
	}

	static void writeCommand_H() {
		int[] chosen_Joshi = new int[JoshisNum];
		for(int i = 0; i < JoshisNum; i++){
			Joshis[i].my_choice = false;
		}
		StringBuilder command = new StringBuilder();
		Random random = new Random();
		boolean check = false;

		while(!check){
			for(int i = 0; i < JoshisNum; i++){
				chosen_Joshi[i] = 0;
			}
			for(int i = 0; i < 2; i++){
				boolean clear = false;
				int kouho = 0;

				while(!clear){
					int c = random.nextInt(WeightArray[JoshisNum]);
					for(int ind = 0; ind < JoshisNum; ind++){
						if(WeightArray[ind] <= c && c < WeightArray[ind+1]){
							kouho = ind;
							break;
						}
					}
					if(Joshis[kouho].target){
						clear = true;
						chosen_Joshi[kouho] = chosen_Joshi[kouho] + 1;
					}
				}
			}
			boolean  fill_need = true;
			for(int i = 0; i < JoshisNum; i++){
				if(chosen_Joshi[i] > 0 && chosen_Joshi[i] * 2 < Joshis[i].need_now){
					fill_need = false;
					break;
				}
			}
			if(fill_need){
				check = true;
			}
		}

		for(int i = 0; i < JoshisNum; i++){
			while(chosen_Joshi[i] > 0){
				Joshis[i].my_choice = true;
				chosen_Joshi[i]--;
				command.append(i);
				command.append(" ");
			}
		}

		writer.println(command.toString());
	}

	static void writeCommand_second() {
		StringBuilder command = new StringBuilder();
		Random random = new Random();
		boolean check = false;

		int kouho = 0;
		int c = random.nextInt(WeightArray[JoshisNum]);
		for(int ind = 0; ind < JoshisNum; ind++){
			if(WeightArray[ind] <= c && c < WeightArray[ind+1]){
				kouho = ind;
				break;
			}
		}

		Joshis[kouho].my_choice = true;
		command.append(kouho);
		command.append(" ");
		command.append(kouho);

		writer.println(command.toString());
	}

	static void write7() {
		StringBuilder command = new StringBuilder();
		Random random = new Random();
		for (int i = 0; i < (Day == 'W' ? 5 : 2); i++) {
			command.append(7);
			if (i < 4) {
				command.append(" ");
			}
		}
		writer.println(command.toString());
	}

}

class Joshi {
	int enthusiasm, revealedScore[], realScore, need_now, holiday_max, holiday_min, my_rank, holiday_kakutei;
	double holiday_kitaichi, holiday_sum;
	boolean dated, target, my_choice;

	Joshi(int enthusiasm) {
		this.enthusiasm = enthusiasm;
	}
}

run.sh

java ProbAI