Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-10SRM380,SRM381,SRM382 (Practice)

SRM 382 PointsOnACircle

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

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

  • 方針を検討
    • とりあえず、1度から359度回してみて一番いいのを選べばいいだろう
    • グラフにしてみるとフローで解けるかな?
      • 0〜359までのノードを考え、赤と青のノードに分割して考える
  • サンプル合わない・・・
    • 同じノードを2回使ってしまっていることに気づく。
    • フローじゃ解けない
    • いやそもそもフローなんて高等なもの使わなくていい気がする。
      • 一つの点からは高々一つの点にしかいかないんだし・・・
  • しばらく唸って時間切れ。

その後

  • 単純に、連結してるノードを数えてやればいいだけだった
    • ノードは単純に分割せず考える
    • ループが発生する場合に注意する
import java.util.Arrays;

public class PointsOnACircle {
	public int color(String[] points) {
		String line = "";
		for (String s : points) {
			line += s;
		}
		String[] data = line.split(" ");
		int len = data.length;
		int[] a = new int[len];
		int[] idmap = new int[361];
		Arrays.fill(idmap, -1);
		for (int i = 0 ; i < len ; i++) {
			a[i] = Integer.valueOf(data[i]);
		}
		Arrays.sort(a);
		for (int i = 0 ; i < len ; i++) {
			idmap[a[i]] = i;
		}
		if (len <= 1) {
			return 0;
		}
		
		int maxpair = 0;
		for (int r = 1 ; r <= 359 ; r++) {
			int[] next = new int[len];
			Arrays.fill(next, -1);
			boolean[] ishead = new boolean[len];
			Arrays.fill(ishead, true);
			for (int i = 0 ; i < len ; i++) {
				int go = (a[i] + r + 360) % 360;
				if (idmap[go] != -1) {
					next[i] = idmap[go];
					ishead[idmap[go]] = false;
				}
			}
			int pairs = 0;
			for (int i = 0 ; i < len ; i++) {
				if (ishead[i]) {
					int cnt = 1;
					int cur = i;
					while (next[cur] != -1) {
						cnt++;
						cur = next[cur];
					}
					pairs += cnt / 2;
				}
			}

			boolean[] visited = new boolean[len];
			for (int i = 0 ; i < len ; i++) {
				if (!ishead[i] && next[i] != -1 && !visited[i]) {
					int cnt = 0;
					int cur = i;
					do {
						visited[cur] = true;
						cnt++;
						cur = next[cur];
					} while (cur != -1 && cur != i);
					if (cur == i) {
						pairs += cnt / 2;
					}
				}
			}
			maxpair = Math.max(maxpair, pairs);
		}
		return maxpair*2;
	}
}