Hatena::Grouptopcoder

nodchipのTopCoder日記 このページをアンテナに追加 RSSフィード

 | 

2010-04-16

SingleRoundMatch467@TopCoder 21:59 SingleRoundMatch467@TopCoder - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - SingleRoundMatch467@TopCoder - nodchipのTopCoder日記 SingleRoundMatch467@TopCoder - nodchipのTopCoder日記 のブックマークコメント

今回の目標はGoogle先生を有効に使うことでした

Easy 250 LateProfessor

  • 時間が10000000までしか内から全部試せばいいんじゃね?
  • 書き始める
  • 答えが合わない
  • 遅刻の意味を取り違えていたらしい
  • 直してみた
  • 最後のexampleでNanが出た
  • なん・・・だと・・・
  • beginとlastが同じ場合は別処理が必要らしい
  • 条件がかなり不安
  • とくにwaitが終わった瞬間に教授が来た場合
  • inclusiveと書いてあるのでこれで良いはず・・・
  • submit

結果 : Passed System Test

class LateProfessor {
public:
	double getProbability(int waitTime, int walkTime, int lateTime, int bestArrival, int worstArrival) {
		if (bestArrival == worstArrival) {
			const int tt = bestArrival % (waitTime + walkTime);
			if (waitTime < tt && tt <= (waitTime + walkTime) - lateTime) {
				return 1.0;
			} else {
				return 0.0;
			}
		}

		int sum = 0;
		for (int t = bestArrival; t < worstArrival; ++t) {
			const int tt = t % (waitTime + walkTime);
			if (waitTime <= tt && tt < (waitTime + walkTime) - lateTime) {
				++sum;
			}
		}


		double result = sum / (double)(worstArrival - bestArrival);
		return result;
	}
}

Middle 500 SuperSum

  • わけが・・・分からない・・・
  • 取り敢えず落ち着いて考えよう
  • きっと何らかの変形ができるはず
  • 紙に表を書いてみる
  • これS(k,n)=\sum_{i=1}^{n}S(k-1,i)=S(k-1,n)+\sum_{i=1}^{n-1}S(k-1,i)=S(k-1,n)+S(k,n-1)じゃね・・・?
  • この形どこかで見たことある・・・
  • パスカルの三角形?
  • 一番上に1,1,1,...,1を追加すると正しくパスカルの三角形!
  • 変数を調整してみる
  • {}_{n+k}C_{k+1}
  • mod面倒だなぁ・・・逆元求める方法があるのは知っているけど・・・
  • BigIntegerでやっちゃえ!
  • submit

結果 : Passed System Test

import java.math.BigInteger;

public class SuperSum {
	public int calculate(int k, int n) {
		BigInteger nk = BigInteger.valueOf(k + n);
		BigInteger answer = BigInteger.ONE;
		for (int i = 0; i <= k; ++i) {
			answer = answer.multiply(nk.subtract(BigInteger.valueOf(i)));
			answer = answer.divide(BigInteger.valueOf(i + 1));
		}
		answer = answer.mod(BigInteger.valueOf(1000000007));
		return answer.intValue();
	}
}

Hard 1000 NextHomogeneousStrings

  • 考えていません

Challenge Phase

  • 250でbegin=lastでwaitが終わった瞬間に教授が来るやつを狙ってみよう
  • この人落ちそう
  • だけどコードがぐちゃぐちゃで何やっているか分からないのでパス
  • この人も落ちそう
  • だけどやっぱりぐちゃぐちゃで読めない
  • この人は落とせそう
  • と思ったら先に落とされたorz

System Test

o o x 436.86 久々に良い成績が取れました

トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20100416
 |