TopCoder SRM 582 Div 2 ○○- 1126->1160

102th, 0/0 challenge
また青コーダー(レート1200以上)に近づいて来ました

250: SemiPerfectSquare

与えられた正整数N(<= 1000)が2つの正整数a<bを用いてa*b*bとして表せるかどうかを答える。
総当りするだけ。

public class SemiPerfectSquare {

	public String check(int N) {
		for(int i = 1; i < Math.sqrt(N) + 1; i++) {
			for(int j =i + 1; j < Math.sqrt(N) + 1; j++) {
				if(i * j * j == N) {
					return "Yes";
				}
			}
		}
		return "No";
	}

}

500: SpaceWarDiv2

魔法少女N人のパワーと、敵の数とパワーが与えられた時に、一人あたりの魔法少女が倒さなければいけない最大値の最小値を答える。
ただし魔法少女は自分のパワー以下の敵しか倒せない。

求めるべき最大値がn人以下かどうかを調べるときには、パワーが上の魔法少女から順に最大n人ずつ敵を強い順に取れるだけ取っていけば簡単に敵を全員倒せるか判断できる。
よって求めるべきnを二分探索すれば良い。

二分探索はあまり書いたことがないので書いている最中は色々と間違えてグダグダでした
以下はちょっと非効率的なコードですが通りました。

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

public class SpaceWarDiv2 {
	public boolean check(int[] magicalGirlStrength, ArrayList<Integer> enStr, int n) {
		int L = magicalGirlStrength.length;
		int size = enStr.size();

		int index = 0;
		for(int i = L - 1; i >= 0; i--) {
			for(int j = 0; j < n; j++) {
				if(index >= size) {
					return true;
				}
				if(magicalGirlStrength[i] >= enStr.get(index)) {
					index++;
				} else {
					break;
				}
			}
		}
		if(index >= size) {
			return true;
		}
		System.out.println(index + ", " + size);
		return false;
	}

	public int minimalFatigue(int[] magicalGirlStrength, int[] enemyStrength, int[] enemyCount) {
		int L = magicalGirlStrength.length;
		int maxStr = -1;
		for(int m: magicalGirlStrength) {
			maxStr = Math.max(maxStr, m);
		}
		int maxEn = -1;
		for(int m: enemyStrength) {
			maxEn = Math.max(maxEn, m);
		}
		if(maxStr < maxEn) {
			return -1;
		}

		Arrays.sort(magicalGirlStrength);
		ArrayList<Integer> enStr = new ArrayList<Integer>();

		int L2 = enemyStrength.length;
		for(int i = 0; i < L2; i++) {
			for(int j = 0; j < enemyCount[i]; j++) {
				enStr.add(enemyStrength[i]);
			}
		}
		Collections.sort(enStr);
		Collections.reverse(enStr);

		int size = enStr.size();

		int low = (int) Math.ceil(size / L);
		int up = size;

		while(low <= up) {
			int mid = (low + up) / 2;
			System.out.println("low:" + low + ", up:" + up + ", mid:" + mid);
			System.out.println("check" + mid + ": " + check(magicalGirlStrength, enStr, mid));
			if(check(magicalGirlStrength, enStr, mid)) {
				if(low == mid) {
					return mid;
				}
				up = mid;
			} else {
				low = mid + 1;
			}
		}
		System.out.println("low:" + low + ", up:" + up);
		return 0;
	}

}