[Topcoder] SRM 418 DIV 2

1000点問題始めて解けた。時間外だけどww


せっかくなので復習。


・250点問題
[問題文]
あなたは始めmyUnits人の兵士を持っており、各兵士は毎ターンやぐらに１のダメージを与える。相手は兵士を持っておらず、その代わり、ライフがhpTのやぐらをnumT持っている。各やぐらは、毎ターンattackT人の兵士を倒す。

戦闘の流れは、
1. あなたの兵士が、任意のやぐらに1pointずつダメージを与える。
2. 相手が、残っているやぐらの数*attackTの数のあなたの兵士倒す。

相手を倒すのに必要な最小のターン数を返しなさい。ただし、倒せない場合は-1を返す。


[定義]
Class: Towers
Method: attack
Parameters: int, int, int, int
Returns: int
Method signature: int attack(int myUnits, int hpT, int attackT, int numT)


[制約]
・myUnitは、1以上1000000以下
・hpT, attackT, numTは、1以上10000以下


[方針]
普通に片っ端からやぐらを倒していく。


[ソース]

public class Towers {
	
	public int attack(int myUnits, int hpT, int attackT, int numT) {
		// 現在のターン
		int turn = 0;
		// 攻撃中のtowerの残りhp
		int hp = hpT;
		
		while(numT > 0) {
			// 全滅したらゲームオーバー
			if(myUnits <= 0) return -1;
			turn++;

			// 自分のターン
			hp -= myUnits;
			while(hp <= 0) {
				hp += hpT;
				numT--;
			}
			
			// 相手のターン
			myUnits -= numT * attackT;
			
		}
		
		return turn;
	}
}

・500点問題
[問題文]
1からnまでの数字の中からm個の数字を選ぶ。同様に、ランダムに選ばれたm個の数字と少なくともk個が一致していればあなたの勝ちとする。
n, m, kが与えられたときあなたの勝つ確率をdouble型で返しなさい。


[定義]
Class:　TwoLotteryGames
Method:　getHigherChanceGame
Parameters:　int, int, int
Returns:　double
Method signature:　double getHigherChanceGame(int n, int m, int k)


[制約]
・nは、2以上 8以下
・mは、1以上 n-1以下
・kは、1以上 m以下


[方針]
高校の確率でやる計算をプログラムでさせる。
ランダムとか一致とかはどうでもよくて、数A風に、
「(n-m)個の白玉とm個の赤玉があります。玉をm個取り出す時に少なくともk個が赤玉である確率を求めよ」と解釈。

少なくともk個一致すればいいのだから、
「1つも一致しない確率 + 1つ一致する確率 + ・・・ + (k-1)個一致する確率」の余事象でok

コンビネーションの求め方は再帰の方が良さげだけど、n, m, kがmax 8なので
これでもオーバーフローしなかった。

（変数名とかメソッド名がわやなのはスルーな方向で）


[ソース]

public class TwoLotteryGames {
	
	public double getHigherChanceGame(int n, int m, int k) {
		int bunshi = 0;
		int bunbo = 1;
		
		// 勝つ場合の数を求める
		for(int i=0; i<k; i++) {
			// i(<k)個一致する確率
			bunshi += getA(n, m, i);
		}
		
		// 全事象を求める
		for(int i=n; i>(n-m); i--) {
			bunbo *= i;
		}
		
		return 1-(double)bunshi/bunbo;
		
	}
	
	/** n個中m個が当たりで、それをm個引きi個当たる当て方を求める */
	private int getA(int n, int m, int i) {
		int result = 1;
		
		// はずれを(m-i)個ひく
		for(int j=(n-m); j>(n-m-m+i); j--) {
			result *= j;
		}
		
		// あたりをi個ひく
		for(int j=0; j<i; j++) {
			result *= (m-j);
		}
		
		// 何番目で当たりをひくかで、mCi通りあるのでそれを掛ける
		result *= combination(m,i);
		
		return result;
	}
	
	/** 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;
	}
}

・1000点問題
[問題文]
あなたは始めmyUnits人の兵士を持っており、相手は、０人の兵士とライフがbarHpの兵舎を持っている。各兵士の攻撃力は1で、 ライフも1である。相手は始め兵士を持っていないがターン終了時に兵舎が倒されていなければ、兵舎unitsPerRound人の兵士が追加される。兵舎のライフはbarHpである。

戦闘の流れは、
1. あなたの兵士が、相手兵士か兵舎を任意に1pointずつダメージを与える。
2. 相手がの兵士が、その数だけあなたの兵士を倒す。
3. 相手の兵舎が倒されていなければ、相手にunitsPerRound人の兵士が追加される。

相手を倒すのに必要な最小のターン数を返しなさい。ただし、倒せない場合は-1を返す。


[定義]
Class: BarracksEasy
Method: attack
Parameters: int, int, int
Returns: int
Method signature: int attack(int myUnits, int barHp, int unitsPerRound)


[制約]
・myUnits, barHp, unitsPerRoundは１以上 ５０以下


[方針]
250と違って、兵士と兵舎のどっちを優先して攻撃するかが問題。
myUnitsは増えることはないので、基本的にはそれを減らさないように兵士を優先して倒し、兵士を全滅させたら余力で少しずつ兵舎のライフを削っていく感じ。

ただ、これだけだと、exampleは通るがSystemテストで落ちる。理由は、最小のターン数でなはいから。

例えば、
myUnits:22, barHp:48, unitsPerRound: 21の場合、

最初のターンで、兵舎に２２のダメージを与えると、その後は1ずつしか減らせない。

初期：myUnits:22, barHp:48, numT:0
1. myUnits:22, barHp:26(-22), numT:21(+21)
2. myUnits:22, barHp:25(-1), numT:21(-21+21)
3. myUnits:22, barHp:24(-1), numT:21(-21+21)
4. myUnits:22, barHp:23(-1), numT:21(-21+21)
　　　　　　・
　　　　　　・
　　　　　　・
13. myUnits:22, barHp:14(-1), numT:21(-21+21)
最小のパターンはここで一斉攻撃
14. myUnits:9, barHp:0(-14), numT:13(-8)
15. myUnits:5, barHp:0, numT:4(-9)
16. myUnits:5, barHp:0, numT:-1(-5)

これを判定しなきゃだめっぽくて、

でも、このフラグは、barHpがmyUnits以下になった時（一斉攻撃すれば倒せる状況になった時）に、
兵舎を一斉攻撃し、numTがあまり減らせなくても全滅せずに倒せるかどうかを調べれば良いので、そういう処理をすればok


[ソース]

public class BarracksEasy {

	public int attack(int myUnits, int barHp, int unitsPerRound) {
		int turn = 0;
		int numT = 0;
		
		while(numT > 0 || barHp > 0) {
			if(myUnits <= 0) return -1;

			// 敵ソルジャーを先に攻撃
			if(unitsPerRound < myUnits && 
					!(
							// 全力でbarを攻撃すればこのターンを倒せる
							myUnits >= barHp
							// barを倒したは良いが、ソルジャーに攻撃されて全滅するということはない
							&& shuoldKillBar(myUnits - (numT-(myUnits-barHp)), numT-(myUnits-barHp))
					)
			) {

				// 敵ソルジャーを先に攻撃
				numT -= myUnits;
				if(numT < 0) {
					barHp += numT;
					numT = 0;
				}
			// barを先に攻撃
			} else {
				barHp -= myUnits;
				if(barHp<0) {
					numT += barHp;
					barHp = 0;
				}
			}
			
			// 相手のターン
			myUnits -= numT;
			
			if(barHp > 0) numT += unitsPerRound;
			turn++;
		}
		
		return turn;
	}
	
	/** Barを一斉攻撃して倒した場合、その後全滅させられないか */
	private boolean shuoldKillBar(int myUnits, int numT) {
		while(numT > 0) {
			numT -= myUnits;
			if(numT <= 0) return true;

			myUnits -= numT;
			if(myUnits <= 0) return false;
		}
		
		return false;
	}
}