Hatena::Grouptopcoder

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

 | 

2010-02-07

SingleRoundMatch460@TopCoder 16:40 SingleRoundMatch460@TopCoder - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - SingleRoundMatch460@TopCoder - nodchipのTopCoder日記 SingleRoundMatch460@TopCoder - nodchipのTopCoder日記 のブックマークコメント

Easy 250 TheQuestionsAndAnswersDivOne

インタビューでquestions種類の質問をした。Yes/Noの解答answers返ってきた。同じ種類の質問を2回以上した場合もある。同じ種類の質問に対する返答は同じ。questionsとanswersが与えられたときに、これらを満たす質問の順番が何通りあるか求めよ。

  • 全探索?
  • 9^9だと間に合わないよなぁ・・・
  • 数え上げるしか無いかorz
  • YesとNoは独立に計算して、あとから質問の組み合わせの個数を書けることにしよう
  • q種類の質問をa個の解答で答えさせるときの組み合わせの個数をテーブルで持って・・・
  • あれ?答えが合わない・・・。
  • 時間がない
  • もう一度頭の中で整理する。
  • 合った

結果:Passed System Test

class TheQuestionsAndAnswersDivOne {
public:
	int pow(int x, int y) {
		if (x == 0 || y == 0) {
			return 1;
		}
		int value = 1;
		for (int i = 0; i < y; ++i) {
			value *= x;
		}
		return value;
	}
	int find(int questions, vector <string> answers) {
		// [質問の数][解答の数]
		int C[16][16];
		memset(C, 0, sizeof(C));
		C[0][0] = 1;
		for (int n = 0; n < 12; ++n) {
			for (int m = 0; m < 12; ++m) {
				C[n + 1][m] += C[n][m];
				C[n + 1][m + 1] += C[n][m];
			}
		}

		int table[10][10];
		memset(table, 0, sizeof(table));
		table[0][0] = 0;
		for (int q = 0; q <= 9; ++q) {
			for (int a = 0; a <= 9; ++a) {
				table[q][a] = pow(q, a);
			}
		}
		for (int q = 1; q <= 9; ++q) {
			for (int a = 1; a <= 9; ++a) {
				for (int qq = 1; qq < q; ++qq) {
					table[q][a] -= table[qq][a] * C[q][qq];
				}
			}
		}

		const int numberOfYes = count(answers.begin(), answers.end(), "Yes");
		const int numberOfNo = count(answers.begin(), answers.end(), "No");

		int result = 0;
		int yes, no;

		for (yes = 0, no = questions; no >= 0; ++yes, --no) {
			if (numberOfYes == 0 && yes == 0 || numberOfYes >= yes && yes > 0) {
				if (numberOfNo == 0 && no == 0 || numberOfNo >= no && no > 0) {
					result += table[yes][numberOfYes] * table[no][numberOfNo] * C[questions][yes];
				}
			}
		}

		return result;
	}
};

Middle 500 TheFansAndMeetingsDivOne

JohnとBrusがN個の待ちの中からK個ずつ選んで訪れることにした。それぞれの待ちではJohnはminJ[i]~maxJ[i]人、BrusはminB[i]~maxB[i]人のファンに会うことが出来る。二人がファンにあった人数が等しくなる確率を求めよ。

  • 残り20分
  • DP臭です
  • [この街までに][何個の待ちを訪れて][それまでに会った人数]=確率 だろうなぁ
  • 書いてみた
  • 合わないんですけど・・・orz

Hard 1000 TheCitiesAndRoadsDivOne

読んでいません。@tsukuno氏のつぶやきによると与えられた隣接行列に対してMSTが何個作れるかという問題のようです。キルヒホッフの定理で一発で求められるものと思います。

撃墜フェーズ

  • 250で全探索でTLEっぽいのを狙って・・・
  • 失敗orz

System Test

o x x -25 78.23ptx

250が遅すぎます。

2018->1921

一気に100近く落ちてしまいました。自分の適性レートは1900くらいなのでしょうか。

kuusvmeoeskuusvmeoes2013/11/24 13:41fuboaupqdpefs, <a href="http://www.zvhvcsktuh.com/">pmwhobtyny</a>

epuboopjpfepuboopjpf2013/11/25 09:52ewqqxupqdpefs, http://www.xcsrchpkub.com/ xhwnjdwqpn

xbamqhasibxbamqhasib2013/11/26 08:31zugnwupqdpefs, [url=http://www.ueywpeiekr.com/]ubuoqfzjwd[/url]

cjqzflkqoqcjqzflkqoq2013/11/27 03:46wtasaupqdpefs, <a href="http://www.niruyvkvvo.com/">admubmdcbh</a> , [url=http://www.ooawmcjpbn.com/]flyczphnli[/url], http://www.vucyxygarx.com/ admubmdcbh

hosjstusvmhosjstusvm2014/06/03 16:03ldqtoupqdpefs, <a href="http://www.lsnoalqanj.com/">vuxpuhewxi</a> , [url=http://www.ggfyszmply.com/]ghntovugqv[/url], http://www.casmjgdrcp.com/ vuxpuhewxi

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