Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-23SRM365 (Practice)

問題結果ポイントその他
300PointsOnCircleAccepted230.66数論
500ArithmeticProgressionsWA0.00???
1000RelabelingOfGraphUnopened0.00グラフ

SRM 365 PointsOnCircle

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

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

  • 好きなパターンの問題(数論ゲー)きた
  • 公式が提示されてるので、それを使うんだろう
    • 最大で 4*10^18 の数の約数を数えなければならない
    • 普通にやるとTLEするので、対策を考える
  • 実験。
    • ある約数と、その二乗の約数を書きだしてみる。
      • 12 = 1, 2, 3, 4, 6, 12
      • 144 = 1, 2, 3, 4, 6, 9, 12, 16, 24, 36, 48, 72, 144
    • 二乗の約数は元の約数の何かと何かをかけ合わせた数になってるんじゃないか?
      • 36 = 6 * 6, 72 = 6 * 12, 144 = 12 * 12
    • きっとそうだ!直感的にも正しいように思える
  • 実装。
    • Setを使って重複しないように気をつけながら数え上げる
  • サンプル通った。
    • 小さめのケースでテストしようとしたがサンプルで網羅されてた
    • 大丈夫っぽい。
  • 提出
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class PointsOnCircle {

	public long count(int r) {
		long rr = 1L * r;
		long cnt1 = 0;
		long cnt3 = 0;
		List<Long> divisors = new ArrayList<Long>();
		for (long i = 1 ; i * i <= rr ; i++) {
			if (rr % i == 0) {
				divisors.add(i);
				long x = rr / i;
				if (x != i) {
					divisors.add(x);
				}
			}
		}
		
		Set<Long> dblDivisors = new HashSet<Long>();
		int dlen = divisors.size();
		for (int i = 0 ; i < dlen ; i++) {
			for (int j = 0 ; j < dlen ; j++) {
				dblDivisors.add(divisors.get(i) * divisors.get(j));
			}
		}
		
		for (long x : dblDivisors) {
			if (x % 4 == 1) {
				cnt1++;
			} else if (x % 4 == 3) {
				cnt3++;
			}
		}
		return 4L * (cnt1 - cnt3);
	}
}

SRM 365 ArithmeticProgressions

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

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

  • 方針検討
    • 数列のうち3つを使って等差数列を作る場合を全探索でよさそう
      • 50 ^ 3 = 125,000通り
  • 実装中・・・
    • 数列の個数を求めるのに苦労する
      • Mを超えないdで割ってmod余る数
      • m以上のdで割ってmod余る数
    • ↑の数を求める実装に苦労する。
  • できた。
    • なんかバグっててサンプル合わない・・・
    • そもそも方針合ってるのかな・・・
  • 時間がない(<3分)ので無理やり帳尻をあわせて提出

SRM 365 RelabelingOfGraph

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

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

  • 練習では解く時間なかったけど、1000もやってみよう
  • あんまり難しくはなかった。
    • こっちが500でいいような気がする
  • やりかた。
    • WFして各ノード同士がつながってるか調べる。
    • 先頭から順番に見ていき、
      • まだラベルを付けてない&自身に繋がってるノードがあれば
      • そっちを先にラベリングする
  • これで通ってしまった。
import java.util.Arrays;

public class RelabelingOfGraph {

	boolean[][] graph;
	int[] flag;
	int count = 0;
	
	public void dfs(int now) {
		int len = graph.length;
		for (int i = 0 ; i < len ; i++) {
			if (graph[i][now] && flag[i] <= -1) {
				// そっち先お願い
				dfs(i);
			}
		}
		flag[now] = count;
		count++;
	}
	
	
	public int[] renumberVertices(String[] m) {
		int len = m.length;
		graph = new boolean[len][len];
		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < len ; j++) {
				graph[i][j] = (m[i].charAt(j) == '1');
			}
		}
		
		for (int k = 0 ; k < len ; k++) {
			for (int i = 0 ; i < len ; i++) {
				for (int j = 0 ; j < len ; j++) {
					if (graph[i][k] && graph[k][j]) {
						graph[i][j] = true;
					}
				}
			}
		}
		for (int i = 0 ; i < len ; i++) {
			if (graph[i][i]) {
				return new int[]{};
			}
		}
		flag = new int[len];
		Arrays.fill(flag, -1);
		
		for (int i = 0 ; i < len ; i++) {
			if (flag[i] <= -1) {
				dfs(i);
			}
		}	
		return flag;
	}
}