TopCoder SRM 569 Div 2 ○○- 1079->1127

575.05, 117th
Challengeを2回失敗した(´・ω・｀)

small

全パターン試せばよい。

public class TheJediTestDiv2 {

	public int countSupervisors(int[] students, int Y, int J) {
		int L = students.length;
		int result = 100000;
		for(int i = 0; i < L; ++i) {
			int[] temp = new int[L];
			for(int j = 0; j < L; ++j) {
				temp[j] = students[j];
			}
			temp[i] -= Y;
			int count = 0;
			for(int j = 0; j < L; ++j) {
				while(temp[j] > 0) {
					count += 1;
					temp[j] -= J;
				}
			}
			result = Math.min(result, count);
		}
		return result;
	}

}

medium

入力を回路に投げた時にANDとORとXORを判別できるか答える。
各桁について0が1つ以上1が2つ以上あればよい。

public class TheDeviceDiv2 {

	public String identify(String[] plates) {
		int L = plates.length;
		int strL = plates[0].length();
		boolean success = true;
		for(int j = 0; j < strL; j++) {
			int count1 = 0;
			int count0 = 0;
			for(int i = 0;i < L; i++) {
				if(plates[i].charAt(j) == '1') {
					count1 += 1;
				}
				if(plates[i].charAt(j) == '0') {
					count0 += 1;
				}
			}
			if(count1 < 2 || count0 < 1) {
				success = false;
				break;
			}
		}
		if(success) {
			return "YES";
		} else {
			return "NO";
		}
	}

}

large

素因数分解して↓約数の個数の公式から求めるという方針だったが、プログラムが間違っているのか方針がそもそも違うのかで、サンプルすら合わず。

• 約数 - Wikipedia

以下サンプルが通らないコード。
サンプル通ったらDPにしようと思っていたけど……。

public class MegaFactorialDiv2 {
	int[][] div = new int[1001][1001];

	public int dp(int n, int k, int[] prime) {
		if(n == 1) {
			return 1;
		}
		if(k == 0) {
			for(int i = 2; i < 1001; i++) {
				prime[i] += div[n][i];
			}
			return 0;
		}

		dp(n, k - 1, prime);
		dp(n - 1, k, prime);
		long result = 1;
		for(int i = 2; i < 1001; i++) {
			result *= (prime[i] + 1);
			result %= 1000000009;
		}
		System.out.println(n + ", " + k);
		/*for(int i = 2; i < 5; i++) {
			System.out.println(n + ", " + k + ", " + i + ", " + prime[i]);
		}*/
		return (int)result;
	}

	public int countDivisors(int N, int K) {
		for(int i = 2; i < 1001; i++) {
			int temp = i;
			for(int j = 2; j < Math.sqrt(i) + 1; j++) {
				while(temp % j == 0) {
					temp /= j;
					div[i][j] += 1;
				}
				if(temp > 1) {
					div[i][temp] += 1;
				}
			}
		}

		int[] prime = new int[1001];

		return dp(N, K, prime);
	}

}