Hatena::Grouptopcoder

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

 | 

2011-12-29

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

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で保存することも考えるとO(2^N N^2 log(2^N N^2))かな
  • でも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台を回復しました。この調子を保っていきたいです。

ゲスト



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