Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-02-18SRM396 (Practice)

SRM 396 DNAString

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

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

コーディングフェーズ

  • 最大で周期pにするとき、最小で何文字変える必要があるか
  • 方針を検討
    • 周期pで作る時、最初のp文字が決まれば生成すべき文字列は決まる
      • これだと最大で 4^p (p <= 2500)の検証が必要になり、間に合わない
    • 周期pにするとき、{a, a+p, a+2p , ...} (0 <= a <= p-1) で文字の登場回数を数え、一番多いものを採用する
      • 必要な変更回数は ∑(count({a, a+p, a+2p, ...}) - max(登場回数))
    • すべての周期を確かめ、一番小さいものを採用する。
    • 計算量はO(n^4+α) (n <= 50)
  • テスト
    • 通った。念のためランダム文字列2500, p=2500で確かめる
    • 間に合った(1.2s)。ちょっと不安だけどこれで提出

システムテスト

  • 最大ケースで1.9sかかる。あぶない!

public class DNAString {
	public int minChanges(int mp, String[] dna) {
		String line = "";
		for (String x : dna) {
			line += x;
		}
		
		int len = line.length();
		int min = Integer.MAX_VALUE;
		for (int p = 1 ; p <= mp ; p++) {
			int cnt = 0;
			for (int md = 0 ; md < p ; md++) {
				char[] clist = new char[512];
				int idx = md;
				int max = 0;
				int total = 0;
				while (idx < len) {
					char c = line.charAt(idx);
					clist[c]++;
					max = Math.max(max, clist[c]);
					idx += p;
					total++;
				}
				cnt += (total - max);
			}
			min = Math.min(min, cnt);
		}
		return min;
	}
}