Hatena::Grouptopcoder

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

 | 

2011-01-13

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

Easy 300 StonesGame

  • 300ってことは数論なんだろうなぁ
  • min-maxをO(1) or O(N)でやりなさい的な何かっぽい
  • 結局数論的な何かか
  • 全然分からないのでmin-maxを書いてみる
  • ・・・
  • なんかバグってる
  • 困った
  • これ2ターンで終わるんじゃね?
  • Romeoのターンで終わればRomeoの勝ち
  • Strangeletのターンで終わればStrangeletの勝ち
  • それ以外はDraw
  • 書いてみた
  • サンプル通った
  • Submit
    • Challenge Succeeded
  • 石に辿りつけるかどうかの判定忘れてた
  • 初手でRomeoが逃げるパターンも入れてないorz

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

class StonesGame {
public:
	void go(int N, int K, int now, int& left, int& right) {
		const int begin = max(1, now - K + 1);
		left = K - (now - begin) - 1 + begin;
		const int end = min(N - K + 1, now);
		right = K - (now - end) - 1 + end;
	}
	string winner(int N, int M, int K, int L) {
		int romeoLeft, romeoRight;
		go(N, K, M, romeoLeft, romeoRight);
		if (romeoLeft <= L && L <= romeoRight && (L & 1) == (romeoLeft & 1)) {
			return "Romeo";
		}

		for (int romeo = romeoLeft; romeo <= romeoRight; romeo += 2) {
			int strangeletLeft;
			int strangeletRight;
			go(N, K, romeo, strangeletLeft, strangeletRight);
			if (!(strangeletLeft <= L && L <= strangeletRight && (L & 1) == (strangeletLeft & 1))) {
				return "Draw";
			}
		}

		return "Strangelet";
	}
}

Middle 450 AmoebaCode

  • 簡単なDPか何かなんだろうなぁ
  • 見た感じでDP
  • これ過去7個分覚えておけばいいだけじゃね?(<-間違い)
  • でもそれって7+α次元DP
  • いやいや、ビットに収めればおkだろう
  • 書いてみた
  • サンプル通った
  • Coding Phase終了後22秒経過してたorz
  • Practice Roomでシステムテストをしてみる
  • TLE
  • なんですと!?
  • ・・・
  • まず7個じゃなくて6個で十分だ
  • 次、dequeにデコード/からエンコードは遅いので配列に変更
  • さらに配列も遅いのでビットフラグを直接いじる
  • 通ったorz
  • プロファイラー持ち出さないと通せないなんてorz

以下はPractice Roomで通ったコードです

class AmoebaCode {
public:
	int K;
	int find(string code, int K) {
		this->K = K;

		static int dp[2][1 << 18];
		fill_n((int*)dp, sizeof(dp) / sizeof(int), K);
		int front = 0;
		int back = 1;

		REP(index, code.size()) {
			memset((int*)dp[front], 0, sizeof(dp) / 2);

			const char c = code[index];
			for (int digit = 1; digit <= K; ++digit) {
				if (c != '0' && c - '0' != digit) {
					continue;
				}

				REP(src, 1 << ((K - 1) * 3)) {
					int cost = dp[back][src];
					int buffer[16];
					if (cost != 1) {
						REP(prev, cost) {
							if (digit == ((src >> (prev * 3)) & 7)) {
								cost = min(cost, prev + 1);
							}
						}
					}
					buffer[0] = digit;
					const int dst = (digit | (src << 3)) & ((1 << ((K - 1) * 3)) - 1);
					dp[front][dst] = max(dp[front][dst], cost);
				}
			}

			swap(front, back);
		}

		int answer = INT_MIN;
		REP(flag, 1 << ((K - 1) * 3)) {
			answer = max(answer, dp[back][flag]);
		}
		return answer;
	}
}

Hard

  • 読んでません

Challenge Phase

  • 今回ってどこが落とし所なんだろう?
  • 分からない
  • 他の人のコードを読んでみる
  • !!!
  • 偶奇判定入れてない!
  • そうか、なら偶奇判定が入っていないコードを落とせば良いのか
  • ・・・
  • 殆どの人に入っている
  • 何もできませんでした

System Test

x x x 0ptx 今回の問題セットは自分には無理でしたorz

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