Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-05-01SRM336,SRM337,SRM338 (Practice)

SRM 336 Shadow

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

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

  • 問題文をナナメ読みしてそっと閉じた
    • 後でちゃんと解く。

SRM 337 CountPalindromes

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

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

  • 典型的な文字列回文DP
    • 左右どちらかに余る文字列パターンは 15 * 15 * 2 * 50 = 22,500 なので、文字列 -> 数にエンコードして持っておく
    • どの文字列パターンにどの文字列を当てるとどの文字列パターンになるか、という状態遷移関数を前もって作成しておく。
      • これをやらないと多分文字列操作コストが重くてTLEする。
  • 時間はかかったが、一発ACできた。
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class CountPalindromes {
	
	long MOD = 835454957;

	class Go {
		int from;
		int to;
		int change;
		int add;
		Go(int f, int t, int c, int a) {
			from = f;
			to = t;
			change = c;
			add = a;
		}
	}
	
	public int count(String[] words, int alen) {
		int len = words.length;
		Map<String, Integer> strmap = new HashMap<String, Integer>();

		
		String[][] strs = new String[len][2];
		for (int i = 0 ; i < len ; i++) {
			strs[i][0] = words[i];
			strs[i][1] = new StringBuffer(words[i]).reverse().toString();
		}
		
		List<String> strlist = new ArrayList<String>();
		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < 2 ; j++) {
				int strlen = strs[i][j].length();
				for (int k = 0 ; k < strlen ; k++) {
					for (int l = k + 1 ; l <= strlen ; l++) {
						String str = strs[i][j].substring(k, l);
						if (!strmap.containsKey(str)) {
							strmap.put(str, strmap.size());
							strlist.add(str);
						}
					}
				}
			}
		}
		strmap.put("", strmap.size());
		strlist.add("");
		
		
		int wordcnt = strmap.size();
		int emptword = wordcnt - 1;
		
		long[][][] dp = new long[101][wordcnt][2];
		for (int i = 0 ; i < len ; i++) {
			String str = words[i];
			int wid = strmap.get(str);
			dp[str.length()][wid][0] = 1;
		}
		
		List<Go>[][] crspids = new List[wordcnt][2];
		for (int i = 0 ; i < wordcnt ; i++) {
			crspids[i][0] = new ArrayList<Go>();
			crspids[i][1] = new ArrayList<Go>();
			String basestr = strlist.get(i);
			for (int j = 0 ; j < len ; j++) {
				for (int d = 0 ; d <= 1 ; d++) {
					String matchstr = strs[j][d];
					int change = 0;
					String left = "";
					if (matchstr.startsWith(basestr)) {
						change = 1;
						left = matchstr.substring(basestr.length());
					} else if (basestr.startsWith(matchstr)) {
						change = 0;
						left = basestr.substring(matchstr.length());
					} else {
						continue;
					}
					crspids[i][d].add(new Go(i, strmap.get(left), change, matchstr.length() + 1));
				}
			}
		}
		
		
		
		
		for (int i = 0 ; i < alen ; i++) {
			for (int j = 0 ; j < wordcnt ; j++) {
				for (int k = 0 ; k <= 1 ; k++) {
					if (dp[i][j][k] == 0) {
						continue;
					}
					long base = dp[i][j][k];
					int opsk = 1 - k;
					for (Go g : crspids[j][opsk]) {
						int ni = i + g.add;
						int nj = g.to;
						int nk = (g.change == 1) ? 1 - k : k;
						if (ni <= alen) {
							dp[ni][nj][nk] += base;
							dp[ni][nj][nk] %= MOD;
						}
					}
				}
			}
		}
		
		
		boolean[] isp = new boolean[wordcnt];
		for (int i = 0 ; i < wordcnt ; i++) {
			String str = strlist.get(i);
			String rev = new StringBuffer(str).reverse().toString();
			if (str.equals(rev)) {
				isp[i] = true;
			}
		}
		
		
		long ans = 0;
		for (int j = 0 ; j < wordcnt ; j++) {
			if (isp[j]) {
				for (int i = 1 ; i <= alen ; i++) {
					for (int k = 0 ; k <= 1 ; k++) {
						ans += dp[i][j][k];
						ans %= MOD;
					}
				}
			}
		}
		return (int)ans;
	}
}

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

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

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

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
    • 行列累乗すればいい気がする
  • まだ解いてない

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

2012-04-21SRM343, SRM344 (Practice)

SRM 343 RefactorableNumber

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

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

  • これ(難易度的に)250だろ・・・
  • 当時の本番後どんな反応だったかは想像に難くない
public class RefactorableNumber {
	public int count(int low, int high) {
		int[] factors = new int[2000010];
		for (int i = 1 ; i < 2000010 ; i++) {
			for (int j = i ; j < 2000010 ; j += i) {
				factors[j]++;
			}
		}
		int cnt = 0;
		for (int l = low ; l <= high ; l++) {
			if (l % factors[l] == 0) {
				cnt++;
			}
		}
		return cnt;
	}
}

2012-04-20SRM345 (Practice)

SRM 345 ByteLand

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

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

  • 貪欲で行ける気がするが、証明ができない
    • 距離を決めうちしてDPする系なのかな?
  • 後で解く