Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-24SRM340, SRM341, SRM342 (Practice)

SRM340 (Practice)

SRM340 (Practice) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM340 (Practice) - hama_DU@TopCoderへの道

DP回 こういうセットばっかりだったらいいのに

問題結果ポイントその他
250ProblemsToSolveAccepted231.59DP
500CsCoursesAccepted329.54DP
1000VegetableGardenOpened0.00

SRM 340 ProblemsToSolve

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

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

  • 動的計画法
    • 座標圧縮して [現在位置][最大][最小] でDPする
import java.util.Arrays;

public class ProblemsToSolve {
	public int minNumber(int[] pn, int variety) {
		int len = pn.length;
		int[] pmap = new int[1001];
		int[] idxscore = new int[1001];
		Arrays.fill(pmap, -1);
		int pidx = 0;
		for (int x : pn) {
			if (pmap[x] == -1) {
				pmap[x] = pidx;
				idxscore[pidx] = x;
				pidx++;
			}
		}
		
		int[][][] dp = new int[len][pidx][pidx];
		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < pidx ; j++) {
				Arrays.fill(dp[i][j], 10000);
			}
		}
		dp[0][pmap[pn[0]]][pmap[pn[0]]] = 1;
		
		int min = len;
		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < pidx ; j++) {
				for (int k = 0 ; k < pidx ; k++) {
					if (dp[i][j][k] >= 10000) {
						continue;
					}
					for (int go = i + 1 ; go <= i + 2 ; go++) {
						if (go >= len) {
							continue;
						}
						
						int solve = dp[i][j][k] + 1;
						int wmin = Math.min(idxscore[j], pn[go]);
						int wmax = Math.max(idxscore[k], pn[go]);
						if (wmax - wmin >= variety) {
							min = Math.min(min, solve);
						}
						int tj = pmap[wmin];
						int tk = pmap[wmax];
						if (dp[go][tj][tk] > solve) {
							dp[go][tj][tk] = solve;
						}
					}
				}
			}
		}
		return min;
	}
}

SRM 340 CsCourses

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

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

  • 動的計画法+辞書順最小経路復元
    • 状態は [month][theoreticalValue][practicalValue]
    • 経路復元付きの場合はメモ化再帰すると楽。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CsCourses {
	int len;
	int[] tv;
	int[] pv;
	int[] exp;
	int bound;
	
	int[][][] memo = new int[51][51][51];
	int[][][] memo_prev = new int[51][51][51];

	
	public int dfs(int month, int ntv, int npv) {
		if (ntv >= bound && npv >= bound) {
			return 0;
		}
		if (memo[month][ntv][npv] >= 0) {
			return memo[month][ntv][npv];
		}
		
		int min = 100000;
		int mini = -1;
		for (int i = 0 ; i < len ; i++) {
			if ((ntv >= tv[i] && npv >= pv[i]) || (ntv < tv[i] - 1 || npv < pv[i] - 1)) {
				continue;
			}
			if (month >= exp[i]) {
				continue;
			}
			int ttv = Math.max(ntv, tv[i]);
			int tpv = Math.max(npv, pv[i]);
			int rec = dfs(month+1, ttv, tpv) + 1;
			if (min > rec) {
				min = rec;
				mini = i;
			}
		}
		memo[month][ntv][npv] = min;
		memo_prev[month][ntv][npv] = mini;
		
		return min;
	}
	
	public int[] getOrder(int[] t, int[] p, int[] expire, int sb) {
		bound = sb;
		tv = t;
		pv = p;
		exp = expire;
		len = tv.length;
		for (int i = 0 ; i < 51 ; i++) {
			for (int j = 0 ; j < 51 ; j++) {
				Arrays.fill(memo[i][j], -1);
				Arrays.fill(memo_prev[i][j], -1);
			}
		}
		
		int num = dfs(0, 0, 0);
		if (num >= 1000) {
			return new int[]{};
		}
		
		int nowmonth = 0;
		int nowtv = 0;
		int nowpv = 0;
		List<Integer> takecourse = new ArrayList<Integer>();
		while (nowtv < sb || nowpv < sb) {
			int c = memo_prev[nowmonth][nowtv][nowpv];
			takecourse.add(c);
			nowmonth++;
			nowtv = Math.max(nowtv, tv[c]);
			nowpv = Math.max(nowpv, pv[c]);
		}
		int[] ret = new int[takecourse.size()];
		for (int i = 0 ; i < ret.length ; i++) {
			ret[i] = takecourse.get(i);
		}
		return ret;
	}
}

SRM 340 VegetableGarden

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

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

  • 面白い問題。
    • グラフに帰着できるような気がするが、どうすればいいかわからない
    • 答えは必ず偶数になる?
  • あとで解く。

SRM341 (Practice)

SRM341 (Practice) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM341 (Practice) - hama_DU@TopCoderへの道

問題結果ポイントその他
250KLastNonZeroDigitsAccepted246.14実装
550LandAndSeaOpened0.00実装、BFS
1000ValidPlatesOpened0.00

SRM 341 KLastNonZeroDigits

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

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

  • やるだけ。
public class KLastNonZeroDigits {
	public String getKDigits(int N, int K) {
		long x = 1;
		for (long a = N ; a >= 1 ; a--) {
			x *= a;
			while (x % 10 == 0 && x >= 1) {
				x /= 10;
			}
		}
		
		String str = String.valueOf(x);
		if (str.length() <= K) {
			return str;
		}
		return str.substring(str.length() - K, str.length());
	}
}

SRM 341 LandAndSea

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

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

  • 実装間に合わず。
import java.util.Arrays;
import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

public class LandAndSea {
	int[][] map;
	int[][] maplevel;
	int[][] islid;
	int[][] islinfo = new int[1000][4];
	int[] levels;
	int idx = 1;
	boolean[][] graph;
	boolean[][] visited;
	
	int[] dx = {1, 0, -1, 0, 1, 1, -1, -1};
	int[] dy = {0, 1, 0, -1, -1, 1, -1, 1};
	
	public int dfs(int isl) {
		int r = 0; 
		for (int i = 1 ; i < idx ; i++) {
			if (graph[isl][i]) {
				r = Math.max(r, dfs(i) + 1);
			}
		}
		return r;
	}
	
	public void paint(int x, int y, int isl) {
		Queue<Integer> q = new ArrayBlockingQueue<Integer>(5000);
		q.add(x);
		q.add(y);
		while (q.size() >= 1) {
			int nx = q.poll();
			int ny = q.poll();
			for (int d = 0 ; d < 4 ; d++) {
				int tx = nx+dx[d];
				int ty = ny+dy[d];
				if (tx <= -1 || ty <= -1 || tx >= visited[0].length || ty >= visited.length) {
					continue;
				}
				if (islid[ty][tx] != isl && !visited[ty][tx]) {
					visited[ty][tx] = true;
					q.add(tx);
					q.add(ty);
				}
			}
		}
	}
	
	public void island(int x, int y) {
		Queue<Integer> q = new ArrayBlockingQueue<Integer>(5000);
		q.add(x);
		q.add(y);
		islid[y][x] = idx;
		islinfo[idx][0] = x;
		islinfo[idx][1] = y;
		islinfo[idx][2] = x;
		islinfo[idx][3] = y;
		while (q.size() >= 1) {
			int nx = q.poll();
			int ny = q.poll();
			for (int d = 0 ; d < 8 ; d++) {
				int tx = nx+dx[d];
				int ty = ny+dy[d];
				if (map[ty][tx] == 1 && islid[ty][tx] == 0) {
					islid[ty][tx] = idx;
					islinfo[idx][0] = Math.min(islinfo[idx][0], tx);
					islinfo[idx][1] = Math.min(islinfo[idx][1], ty);
					islinfo[idx][2] = Math.max(islinfo[idx][2], tx);
					islinfo[idx][3] = Math.max(islinfo[idx][3], ty);
					q.add(tx);
					q.add(ty);
				}
			}
		}
	}

	
	public int[] howManyIslands(String[] seaMap) {
		int w = seaMap[0].length();
		int h = seaMap.length;
		map = new int[h+2][w+2];
		for (int i = 0 ; i < h ; i++) {
			for (int j = 0 ; j < w ; j++) {
				if (seaMap[i].charAt(j) == 'x') {
					map[i+1][j+1] = 1;
					System.out.print(1);
				} else {
					System.out.print(0);
				}
			}
			System.out.println();
		}
		
		levels = new int[501];
		maplevel = new int[h+2][w+2];
		islid = new int[h+2][w+2];
		idx = 1;
		for (int i = 1 ; i <= h ; i++) {
			for (int j = 1 ; j <= w ; j++) {
				if (map[i][j] == 1 && islid[i][j] == 0) {
					island(j, i);
					idx++;
				}
			}
		}
		
		graph = new boolean[idx][idx];
		for (int i = 1 ; i < idx ; i++) {
			visited = new boolean[h+2][w+2];
			paint(0, 0, i);
			for (int y = 0 ; y < h ; y++) {
				for (int x = 0 ; x < w ; x++) {
					int idx = (islid[y][x]);
					if (idx != i && idx >= 1 && !visited[y][x]) {
						graph[i][idx] = true;
					}
				}
			}
		}
		
		for (int i = 1 ; i < idx ; i++) {
			levels[dfs(i)]++;
		}
		int maxlevel = -1;
		for (int l = 0 ; l < 500 ; l++) {
			if (levels[l] >= 1) {
				maxlevel = l;
			}
		}
		int[] ans = new int[maxlevel+1];
		for (int l = 0 ; l <= maxlevel ; l++) {
			ans[l] = levels[l];
		}
		System.out.println(Arrays.toString(ans));
		return ans;
	}
}

SRM 341 ValidPlates

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

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

  • DP
    • 行列累乗すればいい気がする
  • まだ解いてない

SRM342 (Practice)

SRM342 (Practice) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM342 (Practice) - hama_DU@TopCoderへの道

問題結果ポイントその他
250TagalogDictionaryAccepted181.71実装、ソート
500ReverseResourcesOpened0.00DP
1000DrivingAroundTLE0.00グラフ

SRM 342 TagalogDictionary

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

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

  • やるだけ。
    • Comparatorの中に変数を仕込む方法が分からなかったので仕方なくバブルソートでやった
import java.util.Arrays;
import java.util.Comparator;

public class TagalogDictionary {

	int[] ord;
	int ngord;
	
	public int compare(String arg0, String arg1) {
		if (arg0.equals(arg1)) {
			return 0;
		}
		int al = arg0.length();
		int bl = arg1.length();
		int aidx = 0;
		int bidx = 0;
		while (aidx < al && bidx < bl) {
			char a = arg0.charAt(aidx);
			char b = arg1.charAt(bidx);
			int aval = ord[a];
			int bval = ord[b];
			aidx++;
			bidx++;
			if (a == 'n' && aidx < al) {
				if (arg0.charAt(aidx) == 'g') {
					aval = ngord;
					aidx++;
				}
			}
			if (b == 'n' && bidx < bl) {
				if (arg1.charAt(bidx) == 'g') {
					bval = ngord;
					bidx++;
				}
			}
			if (aval < bval) {
				return -1;
			} else if (aval > bval) {
				return 1;
			}
		}
		if (aidx >= al) {
			return -1;
		}
		return 1;
	}
	
	public String[] sortWords(String[] words) {
		String order = "a b k d e g h i l m n ng o p r s t u w y";
		
		
		String[] cp = order.split(" ");
		int cl = cp.length;
		ord = new int[512];
		ngord = 0;
		for (int i = 0 ; i < cl ; i++) {
			if (cp[i].length() == 1) {
				ord[cp[i].charAt(0)] = i;
			} else {
				ngord = i;
			}
		}
		
		int len = words.length;
		for (int y = 0 ; y < len ; y++) {
			for (int x = 0 ; x < len - 1 ; x++) {
				int i = x;
				int j = x + 1;
				String a = words[i];
				String b = words[j];
				int comp = compare(a, b);
				if (comp > 0) {
					String t = words[i];
					words[i] = words[j];
					words[j] = t;
				}
			}
		}
		
		return words;
	}
}

SRM 342 ReverseResources

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

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

  • 動的計画法
    • 典型っぽいのでこのぐらいはサクッと解けるようになりたい
import java.util.Arrays;

public class ReverseResources {
	long MOD = 1000000007;
	
	String match;
	String[] parts;
	int len;
	
	long[][] dp;
	long[][][][] dp2;

	public long dfs(int from, int to, int i, int j) {
		long ptn = 0;
		if (from > to) {
			return 0;
		}
		if (dp2[from][to][i][j] >= 0) {
			return dp2[from][to][i][j];
		}

		boolean lf = (j == parts[i].length());
		boolean gf = (from == to);
		if (lf || gf) {
			if (lf && gf) {
				ptn = 1;
			} else {
				ptn = 0;
			}
			dp2[from][to][i][j] = ptn;
			return ptn;
		}
		
		if (parts[i].charAt(j) == '%') {
			for (int rep = from + 1 ; rep <= to ; rep++) {
				long after = dfs(rep, to, i, j+2) % MOD;
				if (after >= 1) {
					long a = ((dfs(from, rep) % MOD) * after) % MOD;
					ptn = (ptn + a) % MOD;
				}
			}
		} else if (parts[i].charAt(j) == match.charAt(from)){
			ptn = dfs(from+1, to, i, j+1);
		} else {
			ptn = 0;
		}
		
		dp2[from][to][i][j] = ptn;
		return ptn;
	}

	
	public long dfs(int from, int to) {
		if (from >= to) {
			return 1;
		}
		if (dp[from][to] >= 0) {
			return dp[from][to];
		}
		
		long ret = 0;
		for (int i = 0 ; i < len ; i++) {
			ret += dfs(from, to, i, 0);
			ret %= MOD;
		}
		dp[from][to] = ret;
		return ret;
	}
	
	
	public int findDecompositions(String str, String[] resources) {
		dp = new long[101][101];
		dp2 = new long[31][31][51][51];
		for (int i = 0 ; i < 101 ; i++) {
			Arrays.fill(dp[i], -1);
		}
		for (int i = 0 ; i < 31 ; i++) {
			for (int j = 0 ; j < 31 ; j++) {
				for (int k = 0 ; k < 51 ; k++) {
					Arrays.fill(dp2[i][j][k], -1);
				}
			}
		}
		
		match = str;
		parts = resources;
		len = resources.length;
		return (int)dfs(0, str.length());
	}
}

SRM 342 DrivingAround

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

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

  • 既視感のある問題。
  • だが、この問題は辺に重みがついているので違う問題になっている
    • 待てよ、重みが w >= 2 の時はダミーの頂点を w-1 個はさんでやることで重みなしのグラフにできるのでは
    • これで簡易版「いけるかな?」に帰着できた
  • しかし、最大でノードが 10 + 90 * 4 = 370個必要になる。
    • 相当スパースな行列になるが、累乗すると 370^3 のコストが重くのしかかる
    • しかも、「いけるかな」とは違い場合の数を求めなきゃなので、MOD操作のコストがものすごく重い。
      • YES/NO 問題だったらまだ救いはあったが・・・
  • この考え方ではダメのようだ。
    • 一応、書いて出してみるか・・・問題の条件を見落としてるかもしれないし。
      • 案の定TLE。dsyn-

その後

  • ノード数は実は50個用意すれば十分
    • あるノードから他のノードに向かう途中のダミーノードは共通にして使いまわせるため

通ったコード

public class DrivingAround {
	long MOD = 1000003;

	public long[][] e(int size) {
		long[][] e = new long[size][size];
		for (int i = 0; i < size; i++) {
			e[i][i] = 1;
		}
		return e;
	}

	public long[][] pow(long[][] a, long p) {
		long x = 1;
		int len = a.length;
		long[][] ans = e(len);
		while (x <= p) {
			if ((p & x) >= 1) {
				ans = mul(ans, a);
			}
			x *= 2;
			a = mul(a, a);
		}
		return ans;
	}
	
	public long[][] mul(long[][] a, long[][] b) {
		int h = a.length;
		int w = b[0].length;
		int kk = a[0].length;
		long[][] c = new long[h][w];
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				long sum = 0;
				for (int k = 0; k < kk; k++) {
					sum += (a[i][k] * b[k][j]);
					if (sum >= MOD + 1) {
						 sum %= MOD;
					}
				}
				c[i][j] = sum;
			}
		}
		return c;
	}

	public void print(long[][] a) {
		int h = a.length;
		int w = a[0].length;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				System.out.print(a[i][j]);
			}
			System.out.println();
		}
	}

	public int numberOfWays(String[] adj, int start, int finish, int time) {
		int len = adj.length;

		long[][] a = new long[51][51];
		int idx = len;
		for (int i = 0; i < len; i++) {
			for (int x = 0 ; x < 4 ; x++) {
				a[i*5+x][i*5+x+1] = 1;
			}
			for (int j = 0; j < len; j++) {
				if (adj[i].charAt(j) == '.') {
				} else {
					int recur = adj[i].charAt(j) - '1';
					a[i*5+recur][j*5] = 1;
				}
			}
		}

		a = pow(a, time);

		return (int) (a[start*5][finish*5] % MOD);
	}
}

TLEするコード

public class DrivingAround {

	long MOD = 1000003;

	public long[][] e(int size) {
		long[][] e = new long[size][size];
		for (int i = 0; i < size; i++) {
			e[i][i] = 1;
		}
		return e;
	}

	public long[][] pow(long[][] a, long p) {
		long x = 1;
		int len = a.length;
		long[][] ans = e(len);
		while (x <= p) {
			if ((p & x) >= 1) {
				ans = mul(ans, a);
			}
			x *= 2;
			a = mul(a, a);
		}
		return ans;
	}

	public long[][] mul(long[][] a, long[][] b) {
		int h = a.length;
		int w = b[0].length;
		int kk = a[0].length;
		long[][] c = new long[h][w];
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				long sum = 0;
				for (int k = 0; k < kk; k++) {
					sum += (a[i][k] * b[k][j]) % MOD;
				}
				c[i][j] = sum;
			}
		}
		return c;
	}

	public void print(long[][] a) {
		int h = a.length;
		int w = a[0].length;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				System.out.print(a[i][j]);
			}
			System.out.println();
		}
	}

	public int numberOfWays(String[] adj, int start, int finish, int time) {
		int len = adj.length;

		boolean[][] graph = new boolean[500][500];
		int idx = len;
		for (int i = 0; i < len; i++) {
			for (int j = 0; j < len; j++) {
				if (adj[i].charAt(j) == '.') {
				} else {
					int recur = adj[i].charAt(j) - '0';
					int from = i;
					for (int x = 0; x < recur - 1; x++) {
						graph[from][idx] = true;
						from = idx;
						idx++;
					}
					graph[from][j] = true;
				}
			}
		}

		long[][] a = new long[idx][idx];
		for (int i = 0; i < idx; i++) {
			for (int j = 0; j < idx; j++) {
				if (graph[i][j]) {
					a[i][j] = 1;
				}
			}
		}
		a = pow(a, time);

		return (int) (a[start][finish] % MOD);
	}
}