Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-01SRM391 (Practice)

172/440位 2完最下位

問題結果ポイントその他
250IsomorphicWordsAccepted230.74サンプルに助けられる
500KeysInBoxesAccepted188.65デバッグに時間かかった・・・
1000TransformationUnopened0.00見てない

SRM 391 IsomorphicWords

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

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

  • 方針を検討
    • 各文字列ペアに対して、Isomorphicかどうか確認する
    • 先頭から1文字ずつ比較してmapに突っ込んで、矛盾(既に他の文字にマップ済)しなければOKでよさそう
  • サンプル通らない。なんで・・・
    • 問題文に戻る。
    • 同じ文字にマップしちゃいけないのか、アブナイアブナイ
    • マップ済の文字をメモしておき、2度出現したら false を返すように変更
  • サンプル通った。
    • 自明なケース {a, b}などを確認
    • !?このサンプル文字列長が全部同じじゃないか!?
      • All elements of words will have the same length. あ、そうですか・・・よかった
  • 提出

public class IsomorphicWords {
	int al;
	public boolean isok(String a, String b) {
		char[] map = new char[512];
		boolean[] used = new boolean[512];
		for (int i = 0 ; i < al ; i++) {
			char ca = a.charAt(i);
			char cb = b.charAt(i);
			if (map[ca] == 0) {
				map[ca] = cb;
				if (used[cb]) {
					return false;
				}
				used[cb] = true;
			} else if (map[ca] != cb) {
				return false;
			}
		}
		return true;
	}
	
	
	public int countPairs(String[] words) {
		int len = words.length;
		al = words[0].length();
		int count = 0;
		for (int i = 0 ; i < len ; i++) {
			for (int j = i + 1 ; j < len ; j++) {
				if (isok(words[i], words[j])) {
					count++;
				}
			}
		}
		return count;
	}
}

SRM 391 KeysInBoxes

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

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

  • 方針を検討
    • 答えを分数で返さなきゃいけないのか。むずくね・・・
      • 分子分母で共通する因数を計算中ずっとメモしておくのかな・・・
    • とりあえず分子分母がlongに収まる場合を考えよう
  • 箱と鍵の対応は、グラフで表せるはず
    • 爆破する箱の番号は常に若いものを選ぶとして・・・
<1> -> [2] -> [3]  <4> -> [5] 
   ↑─────┘  ↑──┘
    • 例えば上のようなグラフの場合、爆弾が2個必要だ
    • グラフの形の場合の数を得られるようなDPを考える
      • dp[残りノード数][残り使える爆弾の数]
    • 1個爆弾を使う時、x個連続して箱が開けられた場合、
      • dp[N-x][M-1] * (得られる鍵の選び方 = ncr[N-1][x-1]) * (その鍵の並び順 = (x-1)!)
    • だよね。
    • これらの合計が dp[N][M] の答えになる
    • 実装・・・
  • サンプル通った。
  • さて、問題は N= 20, M = 19などのでかいケース
    • 20! > 10^18 なので、longじゃ収まらないかな・・・(←?)
    • 計算量自体は大したことないし、BigInteger使っちゃおう
      • DPをBigIntegerに置き換え。
  • N = 20, M = 19 でテスト
    • あれ、答えが違う気がする
      • N - M = 1 の場合、答えは (分母) - (分子) = 1 の形になってるはず。だがそうなってない
    • ひたすらデバッグ。
    • ncr[0][0] = 1 とするのを忘れてた
  • 今度こそOK。実行時間も問題ない。提出

import java.math.BigInteger;

public class KeysInBoxes {
	
	public long[][] ncr;
	
	public BigInteger[] fact;
	public BigInteger[][] memo;
	
	public BigInteger dfs(int node, int left) {
		if (node == 0) {
			return BigInteger.ONE;
		} else {
			if (left <= 0) {
				return BigInteger.ZERO;
			}
		}
		if (memo[node][left] != null) {
			return memo[node][left];
		}
		
		BigInteger ans = BigInteger.ZERO;
		for (int u = 1 ; u <= node ; u++) {
			BigInteger val = dfs(node - u, left - 1);
			val = val.multiply(BigInteger.valueOf(ncr[node-1][u-1]));
			val = val.multiply(fact[u-1]);
			ans = ans.add(val);
		}
		memo[node][left] = ans;
		
		return ans;
	}

	public String getAllKeys(int N, int M) {
		if (N <= M) {
			return "1/1";
		} else if (M == 1) {
			return "1/" + N;
		}
		
		ncr = new long[21][21];
		ncr[0][0] = 1;
		for (int i = 1 ; i <= 20 ; i++) {
			ncr[i][0] = 1;
			ncr[i][i] = 1;
			for (int j = 1 ; j < i ; j++) {
				ncr[i][j] = ncr[i-1][j] + ncr[i-1][j-1];
			}
		}
		
		fact = new BigInteger[21];
		fact[0] = BigInteger.ONE;
		for (int i = 1 ; i <= 20 ; i++) {
			fact[i] = fact[i-1].multiply(BigInteger.valueOf(i));
		}
		
		memo = new BigInteger[21][21];
		
		BigInteger ans = dfs(N, M);
		BigInteger divisor = ans.gcd(fact[N]);
		
		BigInteger bs = ans.divide(divisor);
		BigInteger bb = fact[N].divide(divisor);

		return bs.toString() + "/" + bb.toString();
	}
}