Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-02-16SRM398 (Practice)

2問早解きセット。

問題結果ポイントその他
250CountExpressionsAccepted160.83問題を難しく勘違いする
500CountPathsAccepted214.89方針ミスで時間を食う
1000 MyFriendsUnopened0.00見てない

SRM 398 CountExpressions

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

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


コーディングフェーズ

  • (サンプルを斜め読みして)げ、めんどくさい系だ
    • 掛け算は先に計算しなきゃいけないし・・・(←間違い)
  • 数字とオペランドの配列を与えると計算結果を返す関数をつくろう
    • 掛け算はどう処理しよう?
      • スタックに積んでいって、掛け算が来たらスタックから一個取り出して掛け算して積もう
    • で、最後にスタックの残りを全部足す。と
    • マイナスが来たらどうする?
      • * -1 してスタックに積もう。-aの足し算をしたことと同じになる
  • 数字の列は4つだから、next_permutationしよう
    • ライブラリを貼り付ける
    • 同じ数列が生成されるから、List<Integer>をマップに突っ込んで既に処理したかどうか調べよう
  • できた。
    • サンプル1が合わない・・・
    • 5 - 3 * 5 - 3 ←このケースが生成されていない。でもこれって 7 じゃなくて -13 じゃん。
      • 何か見落としがあるのか・・・?(ここではじめて問題を斜め読みする)
  • 前から先に計算すればいいだけだった・・・
    • 泣く泣くロジックを修正。提出

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Stack;

public class CountExpressions {
	public int calc(int[] l, int[] operand) {
		int len = l.length;
		int ans = l[0];
		for (int i = 0 ; i < 3 ; i++) {
			if (operand[i] == 2) {
				ans *= l[i+1];
			} else if (operand[i] == 1){
				ans -= l[i+1];
			} else {
				ans += l[i+1];
			}
		}
		return ans;
	}
	
	public int calcExpressions(int x, int y, int val) {
		int cnt = 0;
		int[] li = new int[]{x, x, y, y};
		Arrays.sort(li);
		
		Set<List<Integer>> processed = new HashSet<List<Integer>>();
		
		do {
			List<Integer> nl = new ArrayList<Integer>();
			for (int i = 0 ; i < 4 ; i++) {
				nl.add(li[i]);
			}
			if (processed.contains(nl)) {
				continue;
			}
			processed.add(nl);
			
			for (int ptn = 0 ; ptn < 27 ; ptn++) {
				int[] op = new int[3];
				int p = ptn;
				for (int i = 0 ; i < 3 ; i++) {
					op[i] = p % 3;
					p /= 3;
				}
				if (calc(li, op) == val) {
					cnt++;
				}
			}
		} while (next_permutation(li));
		
		return cnt;
	}

	
	public boolean next_permutation(int[] num) {
		int len = num.length;
		int x = len - 2;
		while (x >= 0 && num[x] >= num[x+1]) {
			x--;
		}
		if (x == -1) return false;

		int y = len - 1;
		while (y > x && num[y] <= num[x]) {
			y--;
		}
		int tmp = num[x];
		num[x] = num[y];
		num[y] = tmp;
		java.util.Arrays.sort(num, x+1, len);
		return true;
	}
}

SRM 398 CountPaths

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

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


コーディングフェーズ

  • さて、あまり時間がないぞ。
  • あるspecial field(以下SF)からあるSFまで行く時、何個SFを通過するか、というDPでどうだろうか
    • つまり dp[from][to][count] を再帰かなんかで計算する
    • スタート地点とゴール地点もSF扱いにしてしまえば後々都合がよさそうだ
    • 更新式を考える
      • dp[x][x+1][1] は (dx+dy)C(dx) を計算すればよさそう
        • nCrを前計算するコードを書く
      • 複数またがる場合(dp[x][x+n][k])は?うまく思い浮かばない。
      • そもそもこれだとspecial fieldを通過しない場合を考慮できない
  • もっとシンプルに考えられないか。
    • 普通に現在地(x,y)に対して通過したSFの数と最後に通過したSFなら
      • dp[count][last used][x][y]
      • 50^4 = 6,250,000 いける!更新も縦と横の一歩分でいい
    • よさげな方針が立った。この時点で残り10分
    • まてよ、移動先(x+1, y) or (x, y+1) がどのSFと一致するか検索しなきゃいけないのか
      • あらかじめ (x, y)が何番目(1-indexed)のSFかを記録するmapを作ることで対処
    • 答えは、各k (0〜n)に対して dp[k][i][c][r] (i=0〜n) の足し算を計算する
  • できた。
    • サンプル3だけ合わない・・・
    • 最後足す時MODを忘れてた・・・修正し提出

import java.util.Arrays;

public class CountPaths {

	int MOD = 1000007;
	long[][] ncr;
	int len;
	int[] row;
	int[] col;
	
	public int[] difPaths(int r, int c, int[] fieldrow, int[] fieldcol) {
		row = fieldrow;
		col = fieldcol;
		len = fieldrow.length;
		ncr = new long[101][101];
		ncr[0][0] = 1;
		for (int i = 1 ; i <= 100 ; i++) {
			ncr[i][0] = 1;
			ncr[i][i] = 1;
			for (int j = 1 ; j <= i - 1 ; j++) {
				ncr[i][j] = (ncr[i-1][j-1] + ncr[i-1][j]) % MOD;
			}
		}
		
		int[][][][] dp = new int[51][51][51][51];
		boolean isfirst = false;
		for (int i = 0 ; i < len ; i++) {
			if (row[i] == 1 && col[i] == 1) {
				isfirst = true;
				dp[1][i+1][1][1] = 1;
				break;
			}
		}
		if (!isfirst) {
			dp[0][0][1][1] = 1;
		}
		
		
		int[][] map = new int[51][51];
		for (int i = 0 ; i < len ; i++) {
			map[col[i]][row[i]] = i+1;
		}
		
		
		
		
		for (int cnt = 0 ; cnt <= len ; cnt++) {
			for (int last = 0 ; last <= len ; last++) {
				for (int x = 1 ; x <= c ; x++) {
					for (int y = 1 ; y <= r ; y++) {
						if (dp[cnt][last][x][y] >= 1) {
							int base = dp[cnt][last][x][y];
							if (x+1 <= c) {
								if (map[x+1][y] == 0) {
									dp[cnt][last][x+1][y] += base;
									dp[cnt][last][x+1][y] %= MOD;									
								} else if (map[x+1][y] > last) {
									int next = map[x+1][y];
									dp[cnt+1][next][x+1][y] += base;
									dp[cnt+1][next][x+1][y] %= MOD;
								}
							}
							
							if (y+1 <= r) {
								if (map[x][y+1] == 0) {
									dp[cnt][last][x][y+1] += base;
									dp[cnt][last][x][y+1] %= MOD;									
								} else if (map[x][y+1] > last) {
									int next = map[x][y+1];
									dp[cnt+1][next][x][y+1] += base;
									dp[cnt+1][next][x][y+1] %= MOD;
								}
							}

						}
					}
				}
			}
		}
		
		
		int[] ans = new int[len+1];
		for (int k = 0 ; k <= len ; k++) {
			for (int last = 0 ; last <= len ; last++) {
				ans[k] += dp[k][last][c][r];
				ans[k] %= MOD;
			}
		}
		
		return ans;
	}

}