Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2010-06-18SRM473(DIV1)

SRM473 div1 第二問(500点) -6/19追記

| SRM473 div1 第二問(500点)   -6/19追記 - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM473 div1 第二問(500点)   -6/19追記 - hama_DU@TopCoderへの道

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

円周上の点からred pointのみをピックアップして直角三角形を作る。

円の直径をとり、あと一点を選べば直角になる。よって点の数が奇数の場合は却下。

red pointは普通に計算していくだけ。


なぜ解けなかったかというと、最後、直角三角形の数を数えるときに、

(places / 2) " places で二重ループ書いていたからでした。

(red pointの数は必ずpointsとなるので、points - 2 を足していけばよい)

以下は書き直したコード。


public class RightTriangle { 

  public long triangleCount(int places, int points, int a, int b, int c) { 
    if (places % 2 != 0 || places <= 3) return 0; 
    int rad = places / 2; 
    boolean[] is_red = new boolean[places]; 
    long[] count_map = new long[rad]; 

    for (int i = 0 ; i < points ; i++) { 
      long pl = (a * i * 1L * i * 1L + b * i * 1L + c); 
      int place = (int)(pl % places); 
      if (is_red[place]) { 
        int idx = 0; 
        while (idx <= places) { 
          idx++; 
          int p = (place + idx) % places; 
          if (!is_red[p]) { 
            is_red[p] = true; 
            break; 
          } 
        } 
      } else { 
        is_red[place] = true; 
      } 
    } 

    long count = 0; 
    for (int i = 0 ; i < rad ; i++) { 
      if (is_red[i] && is_red[i+rad]) {
        count += (points - 2L);
      } 
    } 
    return count; 
  } 
}

これ後で試したけどSystest通らなかった。多分longへのキャスト周りが失敗している模様。


(6/19追記)

red pointを求めるときに、上記の方法だとTLEするので、やり方を変えてみた。

(各余りの位置に入るred pointの数を数えていく。

red pointが複数あった場合は一つだけのこして次の場所にあげる。

places >= point なのでこれでうまくいく。)


もちろん、longへのキャストミスも修正。

ついでにちょっと手直し。


public class RightTriangle {
	public long triangleCount(int places, int points, int a, int b, int c) {
		if (places % 2 != 0 || places <= 3) return 0;
		int rad = places / 2;
		int[] red_num = new int[places];

		for (int i = 0 ; i < points ; i++) {
			long pl = ((long) a * i * i + (long) b * i + (long) c);
			int place = (int)(pl % places);
			red_num[place]++;
		}

		for (int i = 0 ; i < places * 2 ; i++) {
			int pl = i % places;
			if (red_num[pl] >= 2) {
				red_num[(pl+1)%places] += red_num[pl] - 1;
				red_num[pl] = 1;
			}
		}

		long count = 0;
		for (int i = 0 ; i < rad ; i++) {
			if (red_num[i] >= 1 && red_num[i+rad] >= 1) {
				count += (points - 2L);
			}
		}
		return count;
	}
}

これで通りました。coderさんありがとうございます

codercoder2010/06/19 06:16>>red pointは普通に計算していくだけ。
ここが線形探索だと計算量的に間に合わないですよ(1000000,100000,0,0,0 とか)

hama_DUhama_DU2010/06/19 18:07ほんとですね!longのキャスト直したらTLEしました!