Hatena::Grouptopcoder

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

 | 

2010-11-14

Single Round Match 487 11:57 Single Round Match 487 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Single Round Match 487 - nodchipのTopCoder日記 Single Round Match 487 - nodchipのTopCoder日記 のブックマークコメント

Easy 250 BunnyComputer

  • うさぎたん・・・?
  • hos回キタ!
  • ・・・
  • hos回の自分の成績って良くな方気がするorz
  • とりあえず考える
  • ・・・
  • これ本当に250?
  • 取っ掛かりがつかめない
  • k+1個のグループを独立に考えればいいのかなぁ?
  • 各グループについて、i番目までのスコアの合計を考えるDP
  • 250でDPを求めて来るっておかしい気がする
  • でも合ってそうだしなぁ
  • いいや、書いちゃえ!
  • Passed System Test
class BunnyComputer {
public:
	int solve(const vector<int>& preference) {
		const int N = preference.size();
		if (N < 2) {
			return 0;
		}

		vector<int> dp(N);
		dp[1] = preference[0] + preference[1];
		for (int n = 2; n < N; ++n) {
			dp[n] = max(dp[n - 1], dp[n - 2] + preference[n - 1] + preference[n]);
		}
		return dp[N - 1];
	}
	int getMaximum(vector <int> preference, int k) {
		const int N = preference.size();
		int result = 0;
		REP(offset, k + 1) {
			vector<int> ps;
			for (int i = 0; i * (k + 1) + offset < N; ++i) {
				ps.push_back(preference[i * (k + 1) + offset]);
			}
			result += solve(ps);
		}

		return result;
	}
}

Middle 550 BunnyExam

  • ええっと、グラフが与えられて
  • んでk色で塗れるかどうかを判定して・・・
  • そんで、ランダムに色を塗ったときにある配色とどれくらい合っているかの期待値・・・
  • 分からないorz
  • Opened

Hard 950 BunnySequence

  • げ・・・数論・・・
  • とりあえず取り組んでみる
  • ええっと、掛けたり引いたりするのね
  • ・・・
  • これって連続でm回引いちゃダメってこと?(<-微妙に違う)
  • となると、別の問題に置き換えることができる
    • oとxを一直線にn-1個並べる
    • oはm個以上連続してはならない
    • 並べ方はなん通りあるか?
  • これサイズが小さかったら1次元DPだよね?
  • でもそれだとO(nm)になっちゃう
  • ・・・
  • 総和を足せばいいんだから、総和を別の変数でもってリングバッファと組み合わせればO(n)で行けそう
  • 書いてみた
  • 予想していた通り答えが合わない・・・
  • どこがまちがっているんだろう?
  • {3, 4}のケースを手で書きだしてみる
  • あ・・・、一番始めの部分はm-1回以上連続しちゃいけないっぽい
    • そうじゃないと1に戻ってしまう
  • ・・・で?
  • 最初だけm-2回まで総和を取って、それ以降はm-1まで総和を取ればいいのかな?
  • サンプル通った
  • Passed System Test
class BunnySequence {
public:
	int getNumber(int m, int n) {
		if (n < 2) {
			return 1;
		}

		deque<ll> dp;
		dp.push_back(1);
		ll sum = 1;

		int M = m - 1;

		for (int i = 0; i < n - 1; ++i) {
			dp.push_front(sum);
			if (dp.size() > M) {
				sum -= dp.back();
				dp.pop_back();

				if (M != m) {
					M = m;
				}
			}
			sum += dp.front();
			sum %= 1000000009;
			if (sum < 0) {
				sum += 1000000009;
			}
		}

		return (int)sum;
	}
}

Challenge Phase

  • 250で探索をしている人を探してみる
  • 使用済みウサギをビットで持たせてメモ探している人を発見!
  • ・・・
  • これ最大ケースで落ちるのかなぁ?
  • 状態数どれくらいだろう?
  • 1次元DPのやり方から考えると、1グループにN匹いる場合、1グループあたりfib(N)状態くらいだよなぁ・・・
  • k=1とか入れるとfib(25)^2状態か・・・。
  • fib(25)ってどれくらいだろう・・・?
  • オンライン数列辞典によると四万ちょっとらしい
  • これなら落ちそう
  • 撃墜成功!
    • じつは引数の意味を勘違いしてk=2を入れていた
    • それでもfib(16)^3=1000^3位なのでTLE
    • 危なかった・・・
  • あとはよく分からないので終了

System Test

o x o +50 1934->2052 数論がたまたま解けたおかげでいい感じに上がりました。目指せレッドコーダー。

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