[Topcoder] SRM 422 DIV2

書くの忘れてた！！

日曜日にあったSRM 422 DIV2でやっとrateが４桁になりました。





・２５０点問題(MultiNumber)
1236とか与えられたら、それを前・後ろに２つに分割して(123, 6)、
それぞれについて、１桁ずつかけ算した結果(1*2*3, 6)が、前半後半で等しければ"YES"、違えば"NO"と返すだけの簡単なお仕事。


・500点問題（PrimeSoccer）
５分間にチームAが得点する確率をskillOfTeamAパーセント。Bチームが得点するか確率をskillOfTeamBパーセント。それぞれは互いに独立。
９０分間の試合で、少なくとも１チームの得点結果が素数になる確率を求める。

最初問題文読んでて、prime numberが素数と分からず。重要な数字になればいいのはわかったけど重要な数字っていくつだよ！！とか思ってた笑

id:nishiohirokazuさんのiVocaで「TopCoderに出てくる英単語」を学習できるようにしました
に載ってる単語は読めるようにしとこう。

フツーに各チームずつ素数の点を取る確率を計算すればいいんだけど、
最初、チームAが素数点を取る確率とチームBが素数点を取る確率を単純に足してて、
少なくともだから、素数にならないの余事象をとらなきゃいけないのをド忘れしてたりした。

いつもにくらべれば簡単だった気がするー。

public class PrimeSoccer {
	final int[] PRIMES = {2, 3, 5, 7, 11, 13, 17};
	
	public double getProbability(int skillOfTeamA, int skillOfTeamB) {
		double probA = 0.0;
		double probB = 0.0;
		double prob = 0.0;
		
		for(int i=0; i%lt;PRIMES.length; i++) {
			probA += getProb(skillOfTeamA, PRIMES[i]);
		}
		for(int i=0; i%lt;PRIMES.length; i++) {
			probB += getProb(skillOfTeamB, PRIMES[i]);
		}
		
		prob = 1-(1-probA)*(1-probB);
		
		return prob;
	}
	
	/** skill%の確率で得点するとき、point点とる確率を返す */
	private double getProb(int skill, int point) {
		double skillPercent = skill/100.0;
		double rskillPrcent = (100-skill)/100.0;
		double a = 1;
		int i;

		for(i=0; i<point; i++) {
			a*=skillPercent;
		}
		for( ; i<18; i++) {
			a*=rskillPrcent;
		}
		return a*combination(18, point);
	}
	
	/** nCrを返す */
	private int combination(int n, int r) {
		int i,p=1;
		
		for(i=1; i<=r; ++i) {
			p *= (n-i+1);
			p /= i;
		}
		
		return p;
	}
	
}

・１０００点問題（BirthdayCake）
intだと桁が足りないのでlongを多用するんだけど、キャスト忘れがひどかった。
doubleを使う時は例えば
  double a = 3/2;
とかってやると、 int/intは小数点以下切り捨てでintになるから、aには1が入っちゃうから、どっちかを事前にキャストして、
  double a = (double)3/2;
とかにするんだけど、

longを使うのは久々だったから完全に忘れてた。
５０桁のビットフラグを使いたいから、1をシフトさせてってやるんだけど、
1はint型だから、1シフトさせた数(1 << 50)もint型になっちゃう。

正しくするには、1L << 50とかってしなきゃダメ！！

javaでは、
1, 2, 3　→ int型
1.2 3.14 → float型
1.0d 5.4d → double型
1L 1000L → long型
になる。


んで、ループの仕方で、最初はフルーツの全ての組合せについて調べてたら、
Exampleでtimeアウトになってしまい、問題文の、
fruiteは最大５０個、friendは最大２０人ってあるので、

調べなきゃいけないフルーツの組合せは、最大50C25 > 10^14で、
全ての人の組合せは、2^20 > 10^6で
明らかに後者の方が少なくって、

実際にプログラム書いてみたら、後者の方は最大10^6だけど、実際は途中でbreakしたりreturnしたりでフツーにtimeoutにならなかった！！


combinationはよく使うかもだからもっと高速化した方がいいかも。
昔課題でやった気がする。

あと、順番に調べていくやつで、6個中3個とる場合だと、
000111 -> 001011 -> 010011 -> 100011 -> 001101 -> 010101 -> 100101みたいな感じで調べて行ったんだけど、もっといい方法あるのかな？？

あんま探索けいは得意じゃないんだよね汗

import java.util.HashMap;

public class BirthdayCake {

	public int howManyFriends(String[] availableFruits, String[] friendsDislikings, int K) {
		// その人が食べれるものを1としたlong型のビットフラグzの配列
		long[] availableTable = new long[friendsDislikings.length];

		// 全部1で初期化
		long allAvaiable = (1L << availableFruits.length) - 1;
		for(int i=0; i<availableTable.length; i++) {
			availableTable[i] = allAvaiable;
		}

		// フルーツ名(String)と桁(int)の対応を設定
		HashMap<String, Integer> fruitsMap = new HashMap<String, Integer>();
		for(int i=0; i<availableFruits.length; i++) {
			fruitsMap.put(availableFruits[i], i);
		}

		// 食べれないものを0にしていく
		for(int i=0; i<friendsDislikings.length; i++) {
			String[] dislikes = friendsDislikings[i].split(" ");
			for(int j=0; j<dislikes.length; j++) {
				if(!fruitsMap.containsKey(dislikes[j])) continue;
				int index = fruitsMap.get(dislikes[j]);
				availableTable[i] -= 1L << index;
			}
		}

		
		int max = 0;

		// 最大の人数を返せばよく、１人から順に調べる。
		for(int n=1; n<=friendsDislikings.length; n++) {
			int[] choice = new int[n];
			for(int i=0; i<choice.length; i++) {
				choice[i] = i;
			}
			
			int loop = combination(availableTable.length, n);
			for(int count=0; count<loop; count++) {

				// n人の食べれるものをANDを使って取得。
				long temp = availableTable[choice[0]];
				for(int i=1; i<choice.length; i++) {
					temp = temp & availableTable[choice[i]];
				}
				
				// K個以上食べれればok
				if(Long.bitCount(temp) >= K) {
					max=n;
					// n人はokと分かったのでbreakしてn+1人を調べる。
					break;
				}
					
	
				if(count==loop) {
					// n人でダメなのでn+1がokなはずがなく、ここで終了。
					return max;
				}
				
				// n人の取り方を設定する。
				if(choice[choice.length-1] == friendsDislikings.length-1) {
					int cnt;
					for(cnt=1; cnt<choice.length; cnt++) {
						if(choice[choice.length-1-cnt] != friendsDislikings.length-1-cnt) {
							choice[choice.length-1-cnt]++;
							break;
						}
					}
					for(int j=choice.length-1-cnt; j<choice.length-1; j++) {
						choice[j+1] = choice[j]+1;
					}
	
				} else {
					choice[choice.length-1]++;
				}
					
			}
		}
		return max;		
	}

	private int combination(int n, int r) {
		int i;int p=1;
		
		for(i=1; i<=r; ++i) {
			p *= (n-i+1);
			p /= i;
		}
		
		return p;
	}
}