Hatena::Grouptopcoder

hama_DU@TopCoderへの道

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

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