Hatena::Grouptopcoder

hama_DU@TopCoderへの道

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

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);
	}
}