Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-12SRM376 (Practice)

0完で大敗北。本番じゃなくてよかった・・・ 317/437位

問題結果ポイントその他
250TrainyardWA0.00幅優先探索
500MarbleMachineWA0.00行列累乗
1000UnjumpersUnopened0.00見てない

SRM 376 Trainyard

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

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

  • 方針を検討
    • ふつーにBFSしてカウントすればいいか
  • 実装
    • 意外と手間どう・・・ 連結であるかどうかの判定など
    • げ、もう10分もかかってる。制約小さいしかんたん実装して出しちゃえ!

システムテスト

  • あっさり落ちた。
    • やっぱ適当じゃダメだね・・・
    • 一度たどり着いた場所は枝刈りするように変更
import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

public class Trainyard {

	class State {
		int nx;
		int ny;
		int fuel;
		State(int x, int y, int f) {
			nx = x;
			ny = y;
			fuel = f;
		}
	}
	
	int[] dx = {1, 0, -1, 0};
	int[] dy = {0, -1, 0, 1};
	public int reachableSquares(String[] layout, int fuel) {
		int h = layout.length;
		int w = layout[0].length();
		boolean[][] visited = new boolean[h][w];
		int cnt = 0;
		int[][] mask = new int[1000][4];
		mask['S'] = new int[]{1, 1, 1, 1};
		mask['+'] = new int[]{1, 1, 1, 1};
		mask['-'] = new int[]{1, 0, 1, 0};
		mask['|'] = new int[]{0, 1, 0, 1};
		mask['.'] = new int[]{0, 0, 0, 0};
		
		Queue<State> q = new ArrayBlockingQueue<State>(10000);
		for (int i = 0 ; i < h ; i++) {
			for (int j = 0 ; j < w ; j++) {
				if (layout[i].charAt(j) == 'S') {
					q.add(new State(j, i, fuel));
				}
			}
		}
		
		while (q.size() >= 1) {
			State stat = q.poll();
			if (stat.fuel <= -1) {
				continue;
			}
			if (!visited[stat.ny][stat.nx]) {
				visited[stat.ny][stat.nx] = true;
				cnt++;
			} else {
				continue;
			}

			char now = layout[stat.ny].charAt(stat.nx);
			for (int d = 0 ; d < 4 ; d++) {
				if (mask[now][d] >= 1) {
					int tx = stat.nx + dx[d];
					int ty = stat.ny + dy[d];
					if (tx < 0 || ty < 0 || tx >= w || ty >= h) {
						continue;
					}
					char tow = layout[ty].charAt(tx);
					if (mask[tow][(d+2)%4] >= 1) {
						q.add(new State(tx, ty, stat.fuel - 1));
					}
				}
			}
		}
		return cnt;
	}
}


SRM 376 MarbleMachine

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

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

  • 方針を検討
    • これ一定時間ごとに線形で増えていくんじゃないかな
    • 全体で見ても各machineのactionは30で一巡する
    • とりあえず30ターンごとにやってみて、実験して規則っぽいのを探すか
  • 実装
    • バグりまくってバグの解消に40分消費。
    • できた。
  • 実験
    • 30ターンごとに見ると、サンプルでは見事に線形で増えていってる。
    • 時間がないし、これで出しちゃうか
    • 30 * (t / 30) 実行したことにし、その後 (t % 30) シミュレーションを回す。
  • サンプル通った。
    • 時間ないし提出!

システムテスト

  • 落ちた。やっぱりそう単純じゃないか
  • 行列累乗か?
    • でもmarbleの移動だけじゃなくて、定数を足す操作もあるから行列では書けないような・・・
  • いや
    • 書けるし!定数用の列を足してやればいいんだ!
    • 例えば2x2のフィールドだと
| # # # # * | | a |
| # # # # * | | b |
| # # # # * | | c |
| # # # # * | | d |
| 0 0 0 0 1 | | 1 |
(#={0,1},*={0,1,2,3,4,5,6,7,8,9} そのターンのコマンドによる)
    • こんな感じになるはず。
  • 線形変換(元の数から何かをかけたり何かを足したりする操作)は行列で表現できる。
    • 行列を30ターン分作ってそれぞれを掛けあわし、あとはいつもどおり行列累乗すればいいのか。
      • 行列を作るのがちょい面倒か。やるべきことが多いので強実装に分類できると思う
    • そこに気づかぬとは・・・やはり以下略。あとで書く。

その後

  • 1〜6の最小公倍数は30じゃなく60だアホ
  • 後で通したコード。
public class MarbleMachine {

	int[] dx = {1, -1, 0, 0};
	int[] dy = {0, 0, 1, -1};
	int w, h;
	int[] cmap;
	
	long MOD = Long.MAX_VALUE;
	
	public long[][] pow(long[][] a, long n, long mod) {
		long i = 1;
		long[][] res = E(a.length);
		long[][] ap = mul(E(a.length), a, mod);
		while (i <= n) {
			if ((n & i) >= 1) {
				res = mul(res, ap, mod);
			}
			i *= 2;
			ap = mul(ap, ap, mod);
		}
		return res;
	}
	
	public long[][] E(int n) {
		long[][] a = new long[n][n];
		for (int i = 0 ; i < n ; i++) {
			a[i][i] = 1;
		}
		return a;
	}
	
	public long[][] mul(long[][] a, long[][] b, long mod) {
		long[][] c = new long[a.length][b[0].length];
		if (a[0].length != b.length) {
			System.err.print("err");
		}
		for (int i = 0 ; i < a.length ; i++) {
			for (int j = 0 ; j < b[0].length ; j++) {
				long sum = 0;
				for (int k = 0 ; k < a[0].length ; k++) {
					sum = (sum + a[i][k] * b[k][j]);
				}
				c[i][j] = sum;
			}
		}
		return c;
	}

	public long maxMarbles(String[] layout, String[] actions, int t) {
		h = layout.length;
		w = layout[0].length();
		int dlen = actions.length;
		String[] action60 = new String[dlen];
		for (int i = 0 ; i < dlen ; i++) {
			action60[i] = "";
			for (int c = 0 ; c < 60 ; c++) {
				action60[i] += actions[i].charAt(c % actions[i].length());
			}
		}
		cmap = new int[512];
		cmap['D'] = -10;
		cmap['E'] = -1;
		cmap['W'] = -2;
		cmap['S'] = -3;
		cmap['N'] = -4;
		for (int c = '0' ; c <= '9' ; c++) {
			cmap[c] = c - '0';
		}
		
		long[][][] table = new long[60][h*w+1][h*w+1];
		for (int a = 0 ; a < 60 ; a++) {
			table[a][h*w][h*w] = 1;
			for (int i = 0 ; i < h ; i++) {
				for (int j = 0 ; j < w ; j++) {
					int idx = i*w+j;
					int type = layout[i].charAt(j) - '0';
					int act = cmap[action60[type].charAt(a)];
					if (act == -10) {
					} else if (act <= -1) {
						int dir = Math.abs(act) - 1;
						int tx = j + dx[dir];
						int ty = i + dy[dir];
						if (tx < 0 || ty < 0 || tx >= w || ty >= h) {
							continue;
						}
						int tidx = (ty*w)+tx;
						table[a][tidx][idx] = 1;
					} else {
						table[a][idx][idx] = 1;
						table[a][idx][h*w] = act;
					}
				}
			}
		}
		
		long[][] table60 = E(h*w+1);
		for (int a = 0 ; a < 60 ; a++) {
			table60 = mul(table[a], table60, MOD);
		}
		long left = t % 60;
		long cur = t / 60;
		long[][] res = pow(table60, cur, MOD);
		for (int a = 0 ; a < left ; a++) {
			res = mul(table[a], res, MOD);
		}

		long ans = 0;
		for (int i = 0 ; i < h ; i++) {
			for (int j = 0 ; j < w ; j++) {
				ans = Math.max(ans, res[i*w+j][w*h]);
			}
		}		
		return ans;
	}
}
  • おまけ。サンプルだけは通るコード。
    • ちなみに30を60に直しても通りませんでした。
public class MarbleMachine {
	int[] dx = {1, -1, 0, 0};
	int[] dy = {0, 0, 1, -1};
	
	int w, h;
	int[] cmap;
	String[] layout;
	String[] action30;
	
	public long[][] simulation(long[][] mb, long turn) {
		long[][] res = new long[h][w];
		long[][] nmb = new long[h][w];
		for (int a = 0 ; a < turn ; a++) {
			for (int i = 0 ; i < h ; i++) {
				for (int j = 0 ; j < w ; j++) {
					int type = layout[i].charAt(j) - '0';
					int act = cmap[action30[type].charAt(a % 30)];
					if (act == -10) {
					} else if (act <= -1) {
						int dir = Math.abs(act) - 1;
						int tx = j + dx[dir];
						int ty = i + dy[dir];
						if (tx < 0 || ty < 0 || tx >= w || ty >= h) {
							continue;
						}
						nmb[ty][tx] += mb[i][j];
					} else {
						nmb[i][j] += mb[i][j] + act;
					}
				}
			}
			for (int i = 0 ; i < h ; i++) {
				for (int j = 0 ; j < w ; j++) {
					mb[i][j] = nmb[i][j];
					nmb[i][j] = 0;
				}
			}
		}
		
		for (int i = 0 ; i < h ; i++) {
			for (int j = 0 ; j < w ; j++) {
				res[i][j] = mb[i][j];
			}
		}
		return res;
	}
	
	public long maxMarbles(String[] lo, String[] actions, int t) {
		layout = lo;
		int dlen = actions.length;
		action30 = new String[dlen];
		for (int i = 0 ; i < dlen ; i++) {
			action30[i] = "";
			for (int c = 0 ; c < 30 ; c++) {
				action30[i] += actions[i].charAt(c % actions[i].length());
			}
		}
		cmap = new int[512];
		cmap['D'] = -10;
		cmap['E'] = -1;
		cmap['W'] = -2;
		cmap['S'] = -3;
		cmap['N'] = -4;
		for (int c = '0' ; c <= '9' ; c++) {
			cmap[c] = c - '0';
		}
		
		h = layout.length;
		w = layout[0].length();
		long[][] mb = new long[h][w];
		mb = simulation(mb, 30);
		
		long left = t % 30;
		long cur = t / 30;
		long[][] res = new long[h][w];
		for (int i = 0 ; i < h ; i++) {
			for (int j = 0 ; j < w ; j++) {
				res[i][j] += cur * mb[i][j];
			}
		}
		
		res = simulation(res, left);
		long ans = 0;
		for (int i = 0 ; i < h ; i++) {
			for (int j = 0 ; j < w ; j++) {
				ans = Math.max(ans, res[i][j]);
			}
		}	
		return ans;
	}
}

agwagw2012/03/15 15:36はじめまして、いつも楽しみに拝見させていただいております。id:agwと申します。

初学的な質問で大変申し訳ないです。Practice Roomでの過去問に対してシステムテストを行っているとのことですが、どのようにやっていらっしゃるのでしょう?

hama_DUhama_DU2012/03/15 16:02上部メニュー -> practice options -> run system test からできます

agwagw2012/03/15 16:18試してみました。どうもありがとうございます!

本番では一つでも失敗したらシステムテストを落とす、という解釈でよいのでしょうか?

hama_DUhama_DU2012/03/15 16:56もちろんそうです!
一つでも失敗したらポイントの部分が赤く表示されるので、そうなると本番ではfailed system testということになります。

agwagw2012/03/16 03:34なるほど、理解しました。どうもありがとうございます!