Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-02-20SRM395 (Practice)

正解率30%以上のmediumが解けなかった。

309/420位 過去最低順位・・・

問題結果ポイントその他
250StreetWalkingAccepted156.52慎重にやった
500SkyscrapersOpened0.00解けなかった
1000 PubTriviaUnopened0.00見てない

SRM 395 StreetWalking

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

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

コーディングフェーズ

  • 縦横ナナメに進める。
  • 方針検討
    • 以下の2パターン検証する
      • 斜めにmin(X, Y)進み、その後で直進する
      • 全部直進する
  • サンプル合わない。
    • んー?
    • 斜めにmin(X, Y)進んだ後でも、斜めに進んだほうが得なケースがある
    • 上記3パターンの最小値を返すよう実装。
      • コーディングに手間取る・・・
  • サンプル通った
    • 自分ルールであと5分は提出しない。
    • プログラムを見直す。
      • コーディングのミスを発見。気付いてよかった・・・
  • 出した

public class StreetWalking {

	public long req(long X, long Y, long w, long s) {
		X = Math.abs(X);
		Y = Math.abs(Y);
		long ans = 0;
		long total = 0L + X + Y;
		long mintimeA = total * w;
		
		long maxs = Math.min(X, Y);
		long lefts = Math.max(X, Y) - Math.min(X, Y);

		long mintimeB = lefts * w + maxs * s;
		ans = Math.min(mintimeA, mintimeB);
		
		if (lefts >= 1) {
			long first = Math.min(X, Y) * s;
			if (lefts % 2 == 0) {
				ans = Math.min(ans, first + lefts * s);
			} else {
				ans = Math.min(ans, first + (lefts - 1) * s + w);
			}
		}
		return ans;
	}
	
	
	public long minTime(int X, int Y, int w, int s) {
		long mintime = req(X, Y, w, s);
		{
			int[] dx = {1, 0, -1, 0};
			int[] dy = {0, -1, 0, 1};
			for (int d = 0 ; d < 4 ; d++) {
				mintime = Math.min(mintime, req(X+dx[d], Y+dy[d], w, s) + w);
			}
		}
		
		{
			int[] dx = {1, 1, -1, -1};
			int[] dy = {1, -1, 1, -1};
			for (int d = 0 ; d < 4 ; d++) {
				mintime = Math.min(mintime, req(X+dx[d], Y+dy[d], w, s) + s);
			}
		}
		
		return mintime;
	}

}


SRM 395 Skyscrapers

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

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

コーディングフェーズ

  • あからさまに漂うDP
  • 方針検討
    • 一番高い塔をどこに立てるか決めれば、その左と右にあといくつ建てればいいか決まる
    • その次に高い塔から順番に左か右か、何れかの位置に建ててゆく
    • dp[leftPos][rightPos][leftTower][rightTower] みたいなDPができるはず。
    • O(N^4), N<=100 でメモリ足りなくない?
      • leftPos + rightPos <= 100 だし、 leftTower + rightTower <= 101 だから大丈夫。
      • 最大で 50^4+αぐらいで済むはず
  • 実装
    • 最後、余る塔に関してはどうしようか。
    • 途中すっ飛ばした塔の数は固定だから、(余る塔の数)! で予め計算できる
    • 実装できた。とりあえずメモ化は後回し
  • 残り10分、サンプル合わない。
    • あれ?
    • testCase2が18を返すべきところが9を返している
      • 数え漏らし?
    • プログラムを見直す。
      • 特に間違っているところはない・・・
    • 手で書いてみる
      • あっ
      • 僕の方針だと[2, 4, 5, 1, 3] みたいなケースは作れるが [1, 3, 5, 2, 4] みたいなケースは作れない
    • 絶望
      • そのまま時間切れ。


通らないコード

public class Skyscrapers {
	long MOD = 1000000007;
	int N;
	long base;
	
	public long dfs(int left, int right, int lnum, int rnum) {
		if (lnum < 0 || rnum < 0) {
			return 0;
		}
		if (left == 0 && right == 0) {
			if (lnum >= 1 || rnum >= 1) {
				return 0;
			}
			return base;
		}
		
		long ans = 0;
		for (int l = 0 ; l < left ; l++) {
			ans = (ans + dfs(l, right, lnum-1, rnum)) % MOD;
		}
		for (int r = 0 ; r < right ; r++) {
			ans = (ans + dfs(left, r, lnum, rnum-1)) % MOD;
		}
		return ans;
	}
	
	public int buildingCount(int n, int leftSide, int rightSide) {
		N = n;
		if (leftSide + rightSide > n + 1) {
			return 0;
		}

		base = 1;
		long amr = (n - (leftSide + rightSide)) + 1;
		for (long x = 1 ; x <= amr ; x++) {
			base = (base * x) % MOD;
		}
		
		long a = 0;
		for (int i = 0 ; i < N ; i++) {
			a = (a + dfs(i, (N-i-1), leftSide-1, rightSide-1)) % MOD;
			System.out.println(a);
		}
		return (int)a;
	}
}

通したコード

public class Skyscrapers {

	long MOD = 1000000007;
	
	int N;
	long base;
	long[] fact;
	long[][] memo;
	
	public long dfs(int left, int need) {
		if (need > left) {
			return 0;
		}
		if (need < 0) {
			return 0;
		}
		if (left == need) {
			return 1;
		}
		if (memo[left][need] >= 1) {
			return memo[left][need];
		}
		
		long tall = dfs(left-1, need-1);
		long other = (dfs(left-1, need) * (left - 1)) % MOD;
		long ans = (tall + other) % MOD;
		memo[left][need] = ans;
		
		return ans;
	}
	
	public int buildingCount(int n, int leftSide, int rightSide) {
		N = n;
		if (leftSide + rightSide > n + 1) {
			return 0;
		}
		
		fact = new long[101];
		fact[0] = 1;
		for (int i = 1 ; i < 101 ; i++) {
			fact[i] = (fact[i-1] * i) % MOD;
		}
		
		
		long[][] ncr = new long[101][101];
		ncr[0][0] = 1;
		for (int i = 1 ; i < 101 ; 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]) % MOD;
			}
		}	
		
		memo = new long[201][201];
		
		long ans = 0;
		for (int i = 0 ; i < N ; i++) {
			long mul = (dfs(i, leftSide-1) * dfs(N-i-1, rightSide-1)) % MOD;
			long add = (ncr[N-1][i] * mul) % MOD;
			ans = (ans + add) % MOD;
			
		}
		return (int)ans;
	}
}