Hatena::Grouptopcoder

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

 | 

2011-03-30

Member Single Round Match 501 23:02 Member Single Round Match 501 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Member Single Round Match 501 - nodchipのTopCoder日記 Member Single Round Match 501 - nodchipのTopCoder日記 のブックマークコメント

Easy 250 FoxPlayingGame

  • Fox・・・
  • japlj回か。
  • japlj回の過去の戦績はまぁまぁぼちぼち
  • とりあえず取り組んでみる
  • rng_58先生か誰かの掛けたり足したりする問題を思い出した
  • けど、ぜんぜん違うっぽい
  • これきっとまとめて足したりまとめて掛けたりするんだよね・・・
  • その線で書いてみる
  • まとめて足す位置、あるいはまとめて掛ける位置を全探索
  • 書けた
  • submit
    • Passed System Test
class FoxPlayingGame {
public:
class FoxPlayingGame {
public:
	double theMax(int nA, int nB, int paramA, int paramB) {
		const double A = paramA / 1000.0;
		const double B = paramB / 1000.0;
		double result = -1e50;
		for (int offset = 0; offset <= nB; ++offset) {
			double score = 0.0;
			for (int i = 0; i < offset; ++i) {
				score *= B;
			}
			for (int i = 0; i < nA; ++i) {
				score += A;
			}
			for (int i = offset; i < nB; ++i) {
				score *= B;
			}

			result = max(result, score);
		}

		for (int offset = 0; offset <= nA; ++offset) {
			double score = 0.0;
			for (int i = 0; i < offset; ++i) {
				score += A;
			}
			for (int i = 0; i < nB; ++i) {
				score *= B;
			}
			for (int i = offset; i < nA; ++i) {
				score += A;
			}

			result = max(result, score);
		}
		return result;
	}
}

Middle 500 FoxAverageSequence

  • 500はきっとDP
  • ほらやっぱりDP
  • さて、DP表の次元を考えてみる
  • [何文字目][最後に使った数字][それまでの和][前回減少したか?]
  • これでいいと思う
  • でもこれO(NM^4)になるよなぁ
  • 40^5って幾つだろう?
    • 1億くらい
      • 怖ぇぇ
  • 枝刈りをしておくことにする
  • ・・・
  • なかなか答えが合わない
  • 変数名間違いまくっている
  • 書けた
  • submit
    • Passed System Test
static const int MOD = 1000000007;
class FoxAverageSequence {
public:
	int theCount(vector <int> seq) {
		// [何番目][最後に使った数字][それまでの和(平均の計算で使用)][前回下がったかどうか]
		static int dp[2][64][2048][2];
		CLEAR(dp);

		int front = 0;
		int back = 1;

		// 枝刈り
		int prevSumMin;
		int prevSumMax;
		if (seq.front() == -1) {
			for (int i = 0; i <= 40; ++i) {
				dp[back][i][i][0] = 1;
			}
			prevSumMin = 0;
			prevSumMax = 40;
		} else {
			dp[back][seq.front()][seq.front()][0] = 1;
			prevSumMin = seq.front();
			prevSumMax = seq.front();
		}

		for (int index = 1; index < seq.size(); ++index) {
			fill_n((int*)dp[front], 64 * 2048 * 2, 0);

			int prevNumberMin;
			int prevNumberMax;
			if (seq[index - 1] == -1) {
				prevNumberMin = 0;
				prevNumberMax = 40;
			} else {
				prevNumberMin = seq[index - 1];
				prevNumberMax = seq[index - 1];
			}

			int nextNumberMin;
			int nextNumberMax;
			int nextSumMin;
			int nextSumMax;
			if (seq[index] == -1) {
				nextNumberMin = 0;
				nextNumberMax = 40;
				nextSumMin = prevSumMin;
				nextSumMax = prevSumMax + 40;
			} else {
				nextNumberMin = seq[index];
				nextNumberMax = seq[index];
				nextSumMin = prevSumMin + seq[index];
				nextSumMax = prevSumMax + seq[index];
			}

			for (int prevNumber = prevNumberMin; prevNumber <= prevNumberMax; ++prevNumber) {
				for (int prevSum = prevSumMin; prevSum <= prevSumMax; ++prevSum) {
					for (int lastWasDown = 0; lastWasDown < 2; ++lastWasDown) {
						for (int nextNumber = nextNumberMin; nextNumber <= nextNumberMax; ++nextNumber) {
							if (prevSum < nextNumber * index) {
								continue;
							}

							if (lastWasDown && prevNumber > nextNumber) {
								continue;
							}

							// [何番目][最後に使った数字][それまでの和(平均の計算で使用)][前回下がったかどうか]
							int& r = dp[front][nextNumber][prevSum + nextNumber][prevNumber > nextNumber ? 1 : 0];
							r += dp[back][prevNumber][prevSum][lastWasDown];
							r %= MOD;
						}
					}
				}
			}

			swap(front, back);
			prevSumMin = nextSumMin;
			prevSumMax = nextSumMax;
		}

		int result = 0;
		for (int number = 0; number <= 40; ++number) {
			for (int sum = 0; sum <= seq.size() * 40; ++sum) {
				for (int down = 0; down < 2; ++down) {
					result += dp[back][number][sum][down];
					result %= MOD;
				}
			}
		}
		return result;
	}
}

Hard 1000 FoxSearchingRuins

  • 余り考えていません

Challenge Phase

  • 500でぎりぎりTLEしそうな人いるかなぁ
  • このひと全部回してる
  • 最大ケース投入!
    • unsuccessfully
  • orz

System Test

Class NameMethod NameDifficultyCoding TimeStatusPoints
FoxPlayingGametheMaxLevel One0:08:03.817Passed System Test231.87
FoxAverageSequencetheCountLevel Two0:36:43.388Passed System Test253.02
FoxSearchingRuinstheMinTimeLevel Three0:25:04.184Opened0.00
トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20110330
 |