Hatena::Grouptopcoder

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

 | 

2010-11-30

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

Easy 300 BallsConverter

  • Hahako キタ━━━━(゚∀゚)━━━━ッ!!
  • ・・・
  • まずは問題を読んでみる
  • ・・・
  • ???
  • 解法がさっぱり思いつかない
  • ・・・
  • サンプルを眺めてみる
  • ・・・
  • ???
  • ・・・
  • なにこれ・・・
  • ・・・
  • 勘ですね
  • 勘で答える問題ですねこれは
  • そうと分かれば韓で解法を思いつく
  • 計算量的にはO(N^4)までおkなのでそれっぽい解法を捏造してみる
  • 例えば3重ループ回して結合しておkだったらおkとか?
  • 書いてみた
  • サンプル通った
  • じゃあこれで
  • 結果: Passed System Test
class BallsConverter {
public:
	string theGood(vector <string> convert) {
		static int c[64][64];
		const int N = convert.size();
		REP(i, N) {
			REP(j, N) {
				int value;
				if (isupper(convert[i][j])) {
					value = convert[i][j] - 'A';
				} else {
					value = convert[i][j] - 'a' + 26;
				}
				c[i][j] = value;
			}
		}

		REP(i, N) {
			REP(j, N) {
				REP(k, N) {
					if (c[c[i][j]][k] != c[i][c[j][k]]) {
						return "Bad";
					}
				}
			}
		}

		return "Good";
	}
};

Middle 500 DiceRotation

  • サイコロキタ━━━━(゚∀゚)━━━━ッ!!
  • ・・・
  • やっぱりあまり嬉しくない気がする
  • でもあれだ、ICPC模擬地区大会で出したばかりだからなんとかなるだろう
  • とりあえず考えてみる
  • サンプルがひどい
  • 小さいケースを試してみようか?
  • 書いてみた
  • ・・・
  • おおおおお!!!!
  • 規則出た!
  • これを実装すればよいだけか!
  • 書けた
  • 結果: Passed System Test
class DiceRotation {
	enum {
		TOP, FRONT, LEFT, RIGHT, BACK, BOTTOM
	};
	struct State {
		int x;
		int y;
		int number[6];
		void right() {
			const int temp = number[TOP];
			number[TOP] = number[LEFT];
			number[LEFT] = number[BOTTOM];
			number[BOTTOM] = number[RIGHT];
			number[RIGHT] = temp;
			++x;
		}
		void up() {
			const int temp = number[TOP];
			number[TOP] = number[FRONT];
			number[FRONT] = number[BOTTOM];
			number[BOTTOM] = number[BACK];
			number[BACK] = temp;
			++y;
		}
		bool operator < (const State& rh) const {
			if (x != rh.x) {
				return x < rh.x;
			} else if (y != rh.y) {
				return y < rh.y;
			} else {
				return lexicographical_compare(number, number + 6, rh.number, rh.number + 6);
			}
		}
	};
public:
	int theCount(int goalx, int goaly) {
		// 上前左右後下
		State init;
		init.x = 0;
		init.y = 0;
		init.number[0] = 0;
		init.number[1] = 1;
		init.number[2] = 1;
		init.number[3] = 1;
		init.number[4] = 1;
		init.number[5] = 1;

		static const int N = 1;

		map<State, int> dp;
		dp[init] = 1;

		set<State> q;
		q.insert(init);
		while (!q.empty()) {
			const State s = *q.begin();
			q.erase(q.begin());

			if (s.number[0] == 0) {
				if (s.x || s.y) {
					continue;
				}
			}

			if (N - 1 <= s.x || N - 1 <= s.y) {
				continue;
			}

			State right = s;
			right.right();
			dp[right] += dp[s];
			q.insert(right);

			State up = s;
			up.up();
			dp[up] += dp[s];
			q.insert(up);
		}

		static int dp2[N][N];
		CLEAR(dp2);

		for (map<State, int>::iterator it = dp.begin(), itEnd = dp.end(); it != itEnd; ++it) {
			if (it->first.number[0] == 0) {
				dp2[it->first.x][it->first.y] += it->second;
			}
		}

		printf("   ");
		REP(x, N) {
			printf("%3d", x);
		}
		printf("\n");
		REP(y, N) {
			printf("%3d", y);
			REP(x, N) {
				printf("%3d", dp2[x][y]);
			}
			printf("\n");
		}

		assert(goalx);
		assert(goaly);
		if (goalx < goaly) {
			swap(goalx, goaly);
		}

		if (goaly == 1) {
			if (goalx == 4) {
				return 2;
			} else {
				return 0;
			}
		} else if (goaly == 2) {
			if (goalx == 4) {
				return 5;
			} else {
				return 2;
			}
		} else if (goaly == 3) {
			if (goalx == 4) {
				return 6;
			} else {
				return 2;
			}
		} else if (goaly == 4) {
			if (goalx == 4) {
				return 12;
			} else {
				return goalx + 3;
			}
		} else {
			return 2;
		}

		assert(false);

		int result = 0;
		return result;
	}
};

Hard 1000 AppleTrees

  • 読んでいません

Challenge Phase

  • 2問が仮に通ったと仮定して、もう少し上の順位を狙いたい
  • 500で条件を間違えている人を狙おう
  • ・・・
  • 開いた瞬間に落とされたorz
  • ・・・
  • 何も出来ないまま終了・・・

System Test

o o x 2003->2033 まずまずの成績でした。

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