Hatena::Grouptopcoder

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

 | 

2010-04-20

SingleRoundMatch468@TopCoder 22:58 SingleRoundMatch468@TopCoder - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - SingleRoundMatch468@TopCoder - nodchipのTopCoder日記 SingleRoundMatch468@TopCoder - nodchipのTopCoder日記 のブックマークコメント

Easy 250 T9

  • うげ・・・重そう・・・
  • 取り敢えずとりかかってみる
  • まずはキーと文字の対応表を作っておく
  • 次に単語と数字の列との対応表を作っておく
  • "0", "[1-9]", "[#*]"に分けてから先頭から処理
  • 重かった

結果: Passed System Test

class T9 {
public:
	string message(vector <string> part, vector <string> dict, vector <string> keystr) {
		string key;
		for (vector<string>::iterator it = keystr.begin(), itEnd = keystr.end(); it != itEnd; ++it) {
			key += *it;
		}

		map<char, int> keyToNumber;
		for (vector<string>::iterator it = part.begin(), itEnd = part.end(); it != itEnd; ++it) {
			for (string::iterator jt = it->begin(), jtEnd = it->end(); jt != jtEnd; ++jt) {
				keyToNumber[*jt] = distance(part.begin(), it) + 1;
			}
		}

		map<string, vector<string> > keysToWord;
		for (vector<string>::iterator it = dict.begin(), itEnd = dict.end(); it != itEnd; ++it) {
			string keys;
			for (string::iterator jt = it->begin(), jtEnd = it->end(); jt != jtEnd; ++jt) {
				keys += keyToNumber[*jt] + '0';
			}
			keysToWord[keys].push_back(*it);
		}

		for (map<string, vector<string> >::iterator it = keysToWord.begin(), itEnd = keysToWord.end(); it != itEnd; ++it) {
			sort(it->second.begin(), it->second.end());
		}

		char keyTypes[256];
		keyTypes['0'] = 1;
		keyTypes['1'] = 2;
		keyTypes['2'] = 2;
		keyTypes['3'] = 2;
		keyTypes['4'] = 2;
		keyTypes['5'] = 2;
		keyTypes['6'] = 2;
		keyTypes['7'] = 2;
		keyTypes['8'] = 2;
		keyTypes['9'] = 2;
		keyTypes['#'] = 3;
		keyTypes['*'] = 3;
		vector<pair<string, int> > commands;
		string command;
		for (string::iterator it = key.begin(), itEnd = key.end(); it != itEnd; ++it) {
			if (command.empty()) {
				command += *it;
				continue;
			}

			if (keyTypes[command[command.size() - 1]] != keyTypes[*it]) {
				if (command != "") {
					commands.push_back(make_pair(command, keyTypes[command[0]]));
				}
				command = "";
			}

			command += *it;
		}
		if (command != "") {
			commands.push_back(make_pair(command, keyTypes[command[0]]));
		}

		string result;
		vector<pair<string, int> >::iterator it = commands.begin(), itEnd = commands.end();
		while (it != itEnd) {
			switch (it->second) {
			case 1:
				{
					result += string(it->first.size(), ' ');
					++it;
				}
				break;
			case 2:
				{
					if (it + 1 == itEnd || (it + 1)->second != 3) {
						result += keysToWord[it->first][0];
						++it;
					} else {
						int counter = 0;
						for (string::iterator jt = (it + 1)->first.begin(), jtEnd = (it + 1)->first.end(); jt != jtEnd; ++jt) {
							if (*jt == '#') {
								++counter;
							} else if (*jt == '*') {
								counter += 5;
							} else {
								while (1);
							}
						}
						result += keysToWord[it->first][counter];
						++it;
						++it;
					}
				}
				break;
			case 3:
				{
					while (1);
				}
				break;
			}
		}

		return result;
	}
};

Middle 500 RoadOrFlightHard

  • 姉さん、DPです。(誰?
  • 確率じゃないから怖くないもん
  • O(NK)DPを書かなければならないらしい
  • 横をN、縦をKとしてみよう
  • これだけだと歩いているのか飛んでいるのか分からない・・・
  • もう一次元追加して歩いている状態と飛んでいる状態を分けてみよう
  • できた
  • メモリ足りなくね・・・?
  • スワップを入れてみる
  • こんどこそできた
  • submit

結果: Passed System Test

static int roadTime[4000010];
static int flightTime[4000010];

class RoadOrFlightHard {
public:
	long long minTime(int N, int roadFirst, int roadProd, int roadAdd, int roadMod, int flightFirst, int flightProd, int flightAdd, int flightMod, int K) {
		roadTime[0] = roadFirst % roadMod;
		for (int i = 1; i < N; ++i) {
			roadTime[i] = ((ll)roadTime[i - 1] * (ll)roadProd + (ll)roadAdd) % roadMod;
		}

		flightTime[0] = flightFirst % flightMod;
		for (int i = 1; i < N; ++i) {
			flightTime[i] = ((ll)flightTime[i - 1] * (ll)flightProd + (ll)flightAdd) % flightMod;
		}

		ll memo[2][64][2];
		fill_n((ll*)memo, sizeof(memo) / sizeof(ll), 0x1000000000000000LL);
		memo[0][0][0] = 0;

		int front = 1;
		int back = 0;
		for (int n = 1; n <= N; ++n) {
			fill_n((ll*)memo[front], sizeof(memo) / sizeof(ll) / 2, 0x1000000000000000LL);
			for (int k = 0; k <= K; ++k) {
				// 歩く場合
				memo[front][k][0] = min(memo[front][k][0], min(memo[back][k][0], memo[back][k][1]) + roadTime[n - 1]);
				if (k) {
					// 飛ぶ場合
					memo[front][k][1] = min(memo[front][k][1], min(memo[back][k - 1][0], memo[back][k][1]) + flightTime[n - 1]);
				}
			}

			swap(front, back);
		}

		long long result = 0x1000000000000000LL;
		for (int k = 0; k <= K; ++k) {
			for (int flight = 0; flight < 2; ++flight) {
				result = min(result, memo[back][k][flight]);
			}
		}
		return result;
	}
};

Hard 1000 MallSecurity

  • 姉さん、二部マッチングです。(誰?
  • なんとなく天の声が聞こえた
  • 「頂点数-マッチングの数」と言っているように聞こえる
  • でも綺麗な二部マッチングに落ちなくね・・・?
  • 一般グラフの最大マッチングの方にしてみる?
  • 一応ライブラリはある
  • 書けた
  • submit

結果: Failed System Test

  • 上記の式は二部マッチングの時だけだったようです
  • 一部を全探索すると解けるそうです・・・

Challenge Phase

  • どこを狙えば良いのか分からない・・・
  • もうだめだorz

System Test

o o x 478.81 結構良かったようです。次回も魔法の言葉はつぶやかずにするめしたいと思います。

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