Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-06SRM388 (Practice)

SRM389に引き続き簡単回 89/627位

問題結果ポイントその他
250SmoothNumbersAccepted229.09
500InformFriendsAccepted366.11bitDP
1000TelephoneNumbersOpened0.00規則ゲーのような気がする

SRM 388 SmoothNumbers

|  SRM 388 SmoothNumbers - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 388 SmoothNumbers - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=8519

  • 方針を検討
    • 最大kまでの素因数が使えるのか
    • k+1以上の素因数を持つ数をエラトステネスの篩みたいな感じで除外していけばよさそう
      • 念のため、予め素数を列挙しておこう
  • 実装
    • 午前中emacsでAOJやってたのでeclipseでのコーディングに戸惑う
  • サンプル通る。
  • 疑心暗鬼フェーズ
    • 自明なケース (k=1) などでテスト
    • 問題分を読みなおす
      • 最大の素因数がkっていうところが妙に引っかかる
      • 本当にこのやり方で合ってるのか?
    • いや、大丈夫なはず。k+1以上の素因数を持つ数が全部除外されてるのだから
  • 提出

import java.util.Arrays;

public class SmoothNumbers {
	public int countSmoothNumbers(int N, int k) {
		boolean[] isprime = new boolean[200000];
		Arrays.fill(isprime, true);
		isprime[1] = false;
		for (int i = 2 ; i < 200000 ; i++) {
			if (isprime[i]) {
				for (int j = i * 2 ; j < 200000 ; j += i) {
					isprime[j] = false;
				}
			}
		}
		
		boolean[] isksmooth = new boolean[N+1];
		Arrays.fill(isksmooth, true);
		for (int i = k+1 ; i <= N ; i++) {
			if (isprime[i]) {
				for (int j = i ; j <= N ; j += i) {
					isksmooth[j] = false;
				}
			}
		}

		int cnt = 0;
		for (int i = 1 ; i <= N ; i++) {
			if (isksmooth[i]) {
				cnt++;
			}
		}
		return cnt;
	}
}


SRM 388 InformFriends

|  SRM 388 InformFriends - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 388 InformFriends - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=8473

  • グラフゲーきた
  • 方針を検討
    • ふむ。あるノードを選んだ時、それと直接つながっているノードに話が行き渡るのか
    • ノードを複数選んで、全員に話を行き渡らせる。一度使ったノードは使えないとすると、それが最大何回できるか・・ということか
      • なんとなく最大流っぽい
    • 制約を読む。Nが15以下と小さめだ
    • まず、全パターン(2^15)に話をしたとき、全員に行き渡るかどうかチェックしよう
  • 前計算実装
    • んー、これ 2^15 * 15 *15 = 7M もかかる・・・
      • 前計算フェーズでこんなに時間使いたくない
    • とりあえず、(一度全員に話が伝わったパターン) | (なんとか) なパターンを全部trueにしてみる
      • これで多少計算量が落ちてることを祈る
  • さて、パターンは求まった。
    • これ、あとはsubset同士の和の最大を取っていくだけか。
      • いつぞやのKiwiJiceを思い出した。
  • DP実装
    • できた。
  • サンプル通った。
  • 疑心暗鬼フェーズ
    • 念のため最大ケースでテスト。時間は問題なし
    • 自明なケース(友達いない場合など)をテスト。OK
  • 提出

public class InformFriends {

	public int maximumGroups(String[] friends) {
		int len = friends.length;
		int mptn = (1<<len);
		boolean[] ptn = new boolean[mptn];
		for (int i = 0 ; i < mptn ; i++) {
			if (ptn[i]) {
				continue;
			}
			int row = 0;
			for (int j = 0 ; j < len ; j++) {
				if ((i & (1<<j)) >= 1) {
					row |= (1<<j);
					for (int k = 0 ; k < len ; k++) {
						if (friends[j].charAt(k) == 'Y') {
							row |= (1<<k);
						}
					}
				}
			}
			if (row == (mptn - 1)) {
				ptn[i] = true;
				for (int n = i+1 ; n < mptn ; n++) {
					if ((n & i) >= i) {
						ptn[n] = true;
					}
				}
			}
		}
		
		int[] dp = new int[mptn];
		dp[0] = 0;
		for (int i = 0 ; i < mptn ; i++) {
			if (ptn[i]) {
				dp[i] = 1;
			}
		}
		for (int i = 0 ; i < mptn ; i++) {
			for (int sub = (i - 1) & i ; sub > 0 ; sub = (sub - 1) & i) {
				dp[i] = Math.max(dp[i], dp[sub] + dp[i^sub]);
			}
		}
		return dp[mptn-1];
	}
}