Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-02-29SRM392 (Practice)

Arena復活したので久々に練習。

安定して強い人はやはり二完している・・・

234/614位

問題結果ポイントその他
250TwoStringMasksWA0.00場合分けミス。ちくしょー!
500RoundAboutCircleAccepted268.19グラフ上でDP
1000EquiDigitNumbersUnopened0.00読んでない

SRM 392 TwoStringMasks

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

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

コーディングフェーズ

  • 方針を検討
    • なんとなく前後に Z を追加しておく
    • 文字列を * で区切ると、
PPPPssss * SSSS
PPPP * pppSSSS
    • という形になるから、
      • *の前後部分(PPPP, SSSS)のそれぞれprefix と suffixが一致していなければ impossible としていいだろう
    • 問題は残った部分をどうするか・・・
      • 単純に PPPPsssspppSSSS としても正しいが、サンプルにもあるように最短でない場合がある
    • 文字列長は50と短いから、合わせる位置を全探索しちゃえばいいか
  • サンプル通った。
    • いくつかの追加ケースで確認
    • ・・・バグはなく、大丈夫そうだ。
    • 提出

システムテスト

  • 落ちる。なんで!?
    • ケースを見る。
PPPPssss * ppppSSSS
PPPP * SSSS
    • みたいなケースで落ちてた。つまり、ssss と ppppが同じ側にあるケース。
    • そのような場合は合わせることができないので、そのままつなげて返す。

public class TwoStringMasks {

	public String shortestCommon(String s1, String s2) {
		s1 = "Z" + s1 + "Z";
		s2 = "Z" + s2 + "Z";
		String[] d1 = s1.split("\\*");
		String[] d2 = s2.split("\\*");
		
		// front
		int mf = Math.min(d1[0].length(), d2[0].length());
		for (int i = 0 ; i < mf ; i++) {
			if (d1[0].charAt(i) != d2[0].charAt(i)) {
				return "impossible";
			}
		}
		String front = d1[0].substring(0, mf);
		boolean sone = true;
		String frontsuffix = "";
		if (d1[0].length() > d2[0].length()) {
			frontsuffix = d1[0].substring(mf);
		} else {
			frontsuffix = d2[0].substring(mf);
			sone = false;
		}
		
		int mmf = Math.min(d1[1].length(), d2[1].length());
		for (int i = 1 ; i <= mmf ; i++) {
			if (d1[1].charAt(d1[1].length()-i) != d2[1].charAt(d2[1].length()-i)) {
				return "impossible";
			}
		}
		String end = d1[1].substring(d1[1].length()-mmf);
		String endprefix = "";
		boolean eone = true;
		if (d1[1].length() > d2[1].length()) {
			endprefix = d1[1].substring(0, d1[1].length()-mmf);
		} else {
			endprefix = d2[1].substring(0, d2[1].length()-mmf);
			eone = false;
		}

		int fsl = frontsuffix.length();
		int epl = endprefix.length();
		int minpresuf = Math.min(fsl, epl);
		
		int maxsize = 0;
		if (sone ^ eone) {
			for (int m = 1 ; m <= minpresuf ; m++) {
				boolean isok = true;
				for (int i = 0 ; i < m ; i++) {
					if (frontsuffix.charAt(fsl-m+i) != endprefix.charAt(i)) {
						isok = false;
						break;
					}
				}
				if (isok) {
					maxsize = Math.max(maxsize, m);
				}
			}
		}
		
		String ans = front + frontsuffix + endprefix.substring(maxsize) + end;
		return ans.substring(1, ans.length()-1);
	}
}

SRM 392 RoundAboutCircle

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

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


コーディングフェーズ

  • 方針を検討
    • ある位置にいる時の行き先は一意だから、まずそれをすべて求めてしまおう
    • 制約が甘い・・・ N <= 200,000
      • おそらく数学ゲーではないんだろう。
    • 訪問済の位置をマークしながらシミュレーションする
      • 訪問済の位置にぶつかるか、ループになったらストップ
      • ループの場合はループのサイズを計算する
    • 方針はこれでよさそう。
    • 実装
  • サンプル通った。
    • N = 200,000 でテスト。 1.2s ・・・
    • ちょっと危ない気もするけど、高速化手法も思いつかないしこれで出しちゃおう。

システムテスト

  • 通った。よかったー
    • 最大ケースは「199997」で、1.95sかかっていた。
    • これは間違いなくお情け解(この解法でも間に合うように微調整してくれたはず)


import java.util.ArrayList;
import java.util.List;

public class RoundAboutCircle {

	public int maxScore(int N) {
		int[] table = new int[N+1];
		for (int i = 1 ; i <= N ; i++) {
			String x = String.valueOf(i);
			int cnt = 0;
			for (int z = 0 ; z < x.length() ; z++) {
				cnt += (x.charAt(z) - '0');
			}
			table[i] = (i + cnt) % N;
			if (table[i] == 0) {
				table[i] = N;
			}
		}
		
		boolean[] visited = new boolean[N+1];
		int[] dp = new int[N+1];
		for (int i = 1 ; i <= N ; i++) {
			if (!visited[i]) {
				boolean[] loop = new boolean[N+1];
				int now = i;
				int count = 1;
				List<Integer> lv = new ArrayList<Integer>();
				while (!visited[now]) {
					loop[now] = true;
					lv.add(now);
					visited[now] = true;
					now = table[now];
					count++;
				}
				if (loop[now]) {
					int cnt = 0;
					for (int z : lv) {
						if (z == now) {
							break;
						}
						cnt++;
					}
					int loopsize = lv.size() - cnt;
					boolean flag = false;
					int nsize = lv.size();
					for (int z : lv) {
						if (z == now) {
							flag = true;
						}
						if (flag) {
							dp[z] = loopsize;
						} else {
							dp[z] = nsize;
							nsize--;
						}
					}
				} else {
					int total = count + dp[now] - 1;
					for (int z : lv) {
						dp[z] = total;
						total--;
					}
				}
			}
		}
		
		
		int ans = 0;
		for (int i = 1 ; i <= N ; i++) {
			ans = Math.max(ans, dp[i]);
		}
		return ans;
	}

}