Hatena::Grouptopcoder

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

 | 

2010-04-04

SingleRoundMatch466@TopCoder 13:47 SingleRoundMatch466@TopCoder - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - SingleRoundMatch466@TopCoder - nodchipのTopCoder日記 SingleRoundMatch466@TopCoder - nodchipのTopCoder日記 のブックマークコメント

Easy 250 LotteryCheating

  • 数字を0か、約数の数が奇数になるまで数字を書き換えるらしい
  • iterative searchで行けるかなぁ
  • きっと書き換える数字ってそんなに多くないよなぁ
  • 数字の判定は愚直に因数分解するしか無いかなぁ
  • とりあえず書いた
  • 最大ケースを入れたらTLE
  • 何か色々と間違っているらしい
  • 分からない

結果:Compiled

  • 約数の数が奇数=平方数らしい
  • 平方数全部試しても間に合うっぽい
  • printfの書式で桁数を引数で指定するやつがあったような・・・

以下はPracticeで通したソースコードです

class LotteryCheating {
public:
	int minimalChange(string ID) {
		int best = INT_MAX;
		for (ll i = 0; i <= 100000; ++i) {
			char s[16];
			sprintf(s, "%0*lld", ID.size(), i * i);
			const int length = strlen(s);
			if (ID.size() != length) {
				continue;
			}

			int diff = 0;
			for (int j = 0; j < ID.size(); ++j) {
				if (s[j] != ID[j]) {
					++diff;
				}
			}
			best = min(best, diff);
		}

		return best;
	}
}

Middle 500 LotteryPyaterochka

  • 出た・・・確率の問題
  • とりあえず取り組んでみる
  • 特定のパターン数/全パターン数を計算する
  • 全パターン数は{}_{N*5}\mathrm{C}_5パターン
  • 次に特定のパターン数を求める
  • {5}{4,1}{3,2}{3,1,1}が選ばれるパターン数を求めれば良いはず
  • ・・・
  • 答えが合わない
  • 仕方ないので{2,2,1}{2,1,1,1}{1,1,1,1,1}のパターン数を求めて初めの数から引くことにする
  • 答えが合った

結果:Passed System Test

  • それにしても時間がかかりすぎだ
class LotteryPyaterochka {
public:
	double chanceToWin(int N) {
		double low = 1;
		for (int i = 0; i < 5; ++i) {
			low *= N * 5 - i;
			low /= i + 1;
		}

		const double n = N;
		double result = 1.0;
		if (N >= 3) {
			double r = 1;
			r *= n * (n - 1) / 2;
			r *= (n - 2);
			r *= 10.0 * 10.0 * 5;
			result -= r / low;
		}

		if (N >= 4) {
			double r = 1;
			r *= N;
			r *= 10;
			r *= (N - 1);
			r *= (N - 2);
			r *= (N - 3);
			r /= 6;
			r *= 5;
			r *= 5;
			r *= 5;
			result -= r / low;
		}

		if (N >= 5) {
			double r = 1;
			r *= 5;
			r *= 5;
			r *= 5;
			r *= 5;
			r *= 5;
			r *= (N);
			r *= (N - 1);
			r *= (N - 2);
			r *= (N - 3);
			r *= (N - 4);
			r /= 2;
			r /= 3;
			r /= 4;
			r /= 5;
			result -= r / low;
		}

		return result;
	}
}

Hard 1000 DrawingBlackCrosses

  • 読んでいる時間がありませんでした
  • 動的計画法だそうです

Challenge Phase

  • 狙いどころが分からない
  • 以上終了

System Test

x o x 263.79 1726->1718 もう少し早く解きたかった

総評

250で平方数に気づけなかったのが痛かった。気付けたとしても文字数を合わせる部分に気づかなかった可能性が高い。レーティング1900台まで回復させたい。

ゲスト



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