nodchipのTopCoder日記

■ Single Round Match 528 13:14

Easy 250 Cut

• うなぎとかCielだからwriterは日本人・・・っと
• 貪欲かな？
• とりあえずそれっぽいのを書いてみる
• ・・・
• サンプル合わなかったΣ(ﾟДﾟ；ｴｰｯ!
• 問題をよく読み直してみる
• 20のときは1回で10×2に分けられるのか
• ふむふむ
• ならば10の倍数の時を先に処理して、残りは後から処理すべきだな
• あれ・・・
• 小さい方から処理していったほうが良い？
• そんな気がする。
• とりあえずsort()も入れておく
• 書けた
• サンプル通った
• Passed System Test

class Cut {
public:
	int getMaximum(vector <int> eelLengths, int maxCuts) {
		sort(ALL(eelLengths));

		int result = 0;
		REP(i, eelLengths.size()) {
			int l = eelLengths[i];
			if (l % 10 != 0) {
				continue;
			}

			int cut = l / 10 - 1;
			if (cut <= maxCuts) {
				result += l / 10;
				maxCuts -= cut;
			} else {
				result += maxCuts;
				maxCuts = 0;
			}
		}

		REP(i, eelLengths.size()) {
			int l = eelLengths[i];
			if (l % 10 == 0) {
				continue;
			}

			int cut = l / 10;
			result += min(cut, maxCuts);
			maxCuts -= min(cut, maxCuts);
		}

		return result;
	}
};

Midlle 500 SPartition

• 溢れんばかりのDP臭(´д⊂)‥ﾊｩ
• とりあえず基本通りに全探索を考えてみる
• 前探索するなら、XとYの配列前通り作るBFSになるはず
• これをメモ化するとすると
• XとYの配列と何文字目かを状態として持たせてDPか
• ううむ
• これだけだとMLEかTLEしそう
• もうちょっとメモリを節約してみよう
• XとYのprefixは等しくなるのだから・・・
• XとYの配列のうち長い方、何文字目、Xの長さだけ分かっていれば状態を保存できそう(゜゜)
  • Yは上記の状態から復元できるので
• あとXはビット列として保存できそう(゜_゜)
• ならばdp[何文字目][XとYの長い方の配列のビット表現][Xの長さ]のDPだ
• 上限40ってのは最大20文字で打ち切れという意味だと思う(゜-゜)
• ということで計算量はmapで保存することも考えるとかな
• でもdp表がスカスカになる気がするからもっと速いはず(^_^)
• 書いてみる
• ビット演算が面倒くさい・・・(ToT)
• 書けた
• なんか落ちるorz
• ちょこっと修正
• サンプル通った
• 最大ケース通った
• Passed System Test

class SPartition {
public:
	long long getCount(string s) {
		// ビット, Xの長さ
		map<pair<int, int>, ll> current;
		current.insert(MP(MP(0, 0), 1));

		int N = s.size();
		REP(i, N) {
			char ch = s[i];
			int num = (ch == 'o' ? 0 : 1);
			map<pair<int, int>, ll> next;
			for (map<pair<int, int>, ll>::const_iterator it = current.begin(), itEnd = current.end(); it != itEnd; ++it) {
				int bit = it->first.first;
				int xLen = it->first.second;
				int yLen = i - xLen;
				ll ans = it->second;

				if (i == xLen * 2) {
					assert(i == yLen * 2);
					next[MP(bit | (num << xLen), xLen + 1)] += ans;
					next[MP(bit | (num << xLen), xLen)] += ans;

				} else if (i < xLen * 2) {
					// Xの方が長い
					if (xLen * 2 < N) {
						// Xに加える
						next[MP(bit | (num << xLen), xLen + 1)] += ans;
					}

					// チェック後Yに加える
					if (((bit & (1 << yLen)) != 0) == (num != 0)) {
						next[MP(bit, xLen)] += ans;
					}
				} else {
					// Yの方が長い
					if (yLen * 2 < N) {
						// Yに加える
						next[MP(bit | (num << yLen), xLen)] += ans;
					}

					// チェック後Xに加える
					if (((bit & (1 << xLen)) != 0) == (num != 0)) {
						next[MP(bit, xLen + 1)] += ans;
					}
				}
			}

			swap(current, next);

			//for (map<pair<int, int>, ll>::iterator it = current.begin(), itEnd = current.end(); it != itEnd; ++it) {
			//	printf("bit:%d xLen:%d yLen:%d -> %d\n", it->first, it->first.second, i + 1 - it->first.second, (int)it->second);
			//}

			//printf("\n");
		}

		long long result = 0;
		for (map<pair<int, int>, ll>::iterator it = current.begin(), itEnd = current.end(); it != itEnd; ++it) {
			result += it->second;
		}
		return result;
	}
}

Hard 1000 ColorfulCookie

• さっぱりわからん
• とりあえず焼きなまし解法投げておくか
• Challenge Succeeded

Challenge Phase

• 250でソート忘れで{30,20}で落ちる人を探す
• いないなぁ・・・
• あ、これいけるかな？
• う？
• なんかループ回して最小値見つけてる
• ううむ
• 終了

System Test

oox 491.87 97位 1716->1816 久々の1800台を回復しました。この調子を保っていきたいです。

ツイートする