Hatena::Grouptopcoder

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

 | 

2011-09-11

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

Easy 250 CompositeSmash

  • トーストウーマンということはrng_58さんかな?
  • しょっぱなから面倒そうな数論・・・
  • 全探索無理かな?
  • N<=100,000だからメモ探のメモリは足りそう
  • 再帰の回数は高々log(N)だから時間も足りそう
  • 書いてみる
  • 書けた
  • submit
  • Passed System Test
int dp[128 * 1024];

class CompositeSmash {
public:
	int target;
	bool dfs(int current) {
		int& r = dp[current];
		if (r) {
			return r == YES;
		}

		if (current == target) {
			r = YES;
			return true;
		}

		if (current % target != 0) {
			r = NO;
			return false;
		}

		bool atLeastOne = false;
		bool bothFailed = false;
		for (int i = 2; i * i <= current; ++i) {
			if (current % i != 0) {
				continue;
			}

			atLeastOne = true;
			const bool lh = dfs(i);
			const bool rh = dfs(current / i);
			if (!(lh || rh)) {
				bothFailed = true;
			}
		}

		r = atLeastOne && !bothFailed;
		return r == YES;
	}
	string thePossible(int N, int target) {
		CLEAR(dp);
		this->target = target;

		string result = dfs(N) ? "Yes" : "No";
		return result;
	}
}

Middle 600 AdjacentSwaps

  • 読んでいません

Hard 900 ColorfulBoard

  • どうせ600は数論DPの難しいやつのはずなので900に逃げる
  • とりあえず考えてみる
  • ・・・
  • これ探索で行けたりしないかな?
  • 盤面の状態を引数にして再帰探索
  • ハッシュを使ってメモ化
  • 全部塗ってから一分だけ書き換えたほうが早い場合があるので、そこだけ特殊処理
  • とりあえず書いてみる
  • 書けた
  • 動いた
  • とりあえずsubmit
  • でも最大ケース試してない
  • 手元でいくつか作ってみる
  • ・・・
  • TLEした
  • 盤面の探索の際にsortして正規化してみる
  • 通った
  • resubmit
  • ・・・
  • それでも怪しい
  • もうちょっとやばいケースを考えてみる
  • ・・・
  • TLEした
  • ループをいじって貪欲法に近い形に書きなおしてみる
  • なんか答えが合わなくなった
  • ・・・
  • 時間切れ
  • ・・・
  • return文周辺の処理の順番がおかしいっぽい
  • 直した
  • Practice通った
  • ・・・
  • これは惜しい・・・
class ColorfulBoard {
public:
	void trans(const vector<string>& board, vector<string>& out) {
		const int Y = board.size();
		const int X = board[0].size();
		out.clear();
		out.resize(X, string(Y, ' '));
		REP(i, X) {
			REP(j, Y) {
				out[i][j] = board[j][i];
			}
		}
	}
	void normalize(const vector<string>& board, vector<string>& out) {
		trans(board, out);
		if (board < out) {
			out = board;
		}
	}
	ll hash(const vector<string>& board) {
		const int Y = board.size();
		const int X = board[0].size();
		ll h = -1;
		REP(y, Y) {
			REP(x, X) {
				const ll ch = board[y][x];
				h ^= ch + (h << 6) + (h >> 2);
			}
			h ^= (h << 6) + (h >> 2);
		}
		return h;
	}
	void print(const vector<string>& board) {
		REP(r, board.size()) {
			cout << board[r] << endl;
		}
		cout << endl;
	}
	map<ll, int> dp;
	int dfs(const vector<string>& board) {
		//print(board);

		if (board.empty()) {
			return 0;
		}

		vector<string> normalized;
		normalize(board, normalized);

		const ll h = hash(normalized);
		if (dp.find(h) != dp.end()) {
			return dp[h];
		}

		int best = INT_MAX;
		vector<string> target = board;
		REP(rev, 2) {
			sort(ALL(target));
			const int R = target.size();
			const int C = target[0].size();
			REP(r, R) {
				if (search_n(ALL(target[r]), C, target[r][0]) == target[r].begin()) {
					//cout << target[r] << endl;
					vector<string> next = target;
					next.erase(next.begin() + r);
					const int nextScore = dfs(next);
					if (nextScore == -1) {
						return dp[h] = -1;
					}
					MIN_UPDATE(best, nextScore + 1);
					break;
				}
			}

			// 特殊処理
			if (search_n(ALL(target), R, target[0]) == target.begin()) {
				const string& row = target[0];
				map<char, int> m;
				REP(i, row.size()) {
					++m[row[i]];
				}

				int bestCount = INT_MIN;
				for (map<char, int>::iterator it = m.begin(), itEnd = m.end(); it != itEnd; ++it) {
					MAX_UPDATE(bestCount, it->second);
				}

				const int res = MIN(R, C) + C - bestCount;
				MIN_UPDATE(best, res);
			}

			trans(board, target);
		}

		if (best == INT_MAX || best == -1) {
			return dp[h] = -1;
		}

		return dp[h] = best;
	}
	int theMin(vector <string> board) {
		int result = dfs(board);
		return result;
	}
}

Challange Phase

  • 900に狙いを定める
  • 自分の考えた特殊ケースを投げてみる
  • 全部失敗したorz

System Test

Class NameMethod NameDifficultyCoding TimeStatusPoints
CompositeSmashthePossibleLevel One0:14:15.875Passed System Test203.51
AdjacentSwapstheCountLevel Two0:48:34.012Opened0.00
ColorfulBoardtheMinLevel Three0:46:30.284Challenge Succeeded310.04

oxx 1942->1798 順調に右肩下がり中・・・

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