Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-02-29SRM392 (Practice)

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

}