Hatena::Grouptopcoder

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

 | 

2011-01-28

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

Class NameMethod NameDifficultyCoding TimeStatusPoints
ColorfulCardstheCardsLevel One0:22:29.827Passed System Test183.83
CarrotBoxestheProbabilityLevel Two0:52:20.480Opened0.00
StrangeElevatortheCountLevel Three0:46:59.396Opened0.00

Easy 275 ColorfulCards

  • 全く予期していなかったRabbit Hanakoきた
  • rng回ですね
  • 見た感じで前と後ろから当てはめられる数字を当てはめて、両方当てはまる数字を調べていけばいい感じ
  • でもこれ書くのちょっと面倒かも
  • さすがは275
  • なんかいつもより時間がかかっている・・・
  • 書けた
#define MAX (256*1024)
class ColorfulCards {
public:
	vector <int> theCards(int N, string colors) {
		static bool flag[MAX];
		memset(flag, -1, sizeof(flag));
		flag[0] = flag[1] = false;
		for (int i = 2; i * i < MAX; ++i){
			if (!flag[i]){
				continue;
			}
			for (int j = i * i; j < MAX; j += i){
				flag[j] = false;
			}
		}

		static bool dp0[64][1024];
		static bool dp1[64][1024];
		CLEAR(dp0);
		CLEAR(dp1);

		REP(n, 1024) {
			dp0[0][n] = true;
		}
		REP(i, colors.size()) {
			const int prev = distance(dp0[i], find(dp0[i], dp0[i] + 1024, true));
			for (int n = prev + 1; n < 1024; ++n) {
				if ((colors[i] == 'R' && flag[n]) || (colors[i] == 'B' && !flag[n])) {
					dp0[i + 1][n] = true;
				}
			}
		}

		REP(n, 1024) {
			dp1[colors.size()][n] = true;
		}

		for (int i = colors.size() - 1; i >= 0; --i) {
			int prev;
			for (prev = N + 1; prev >= 0; --prev) {
				if (dp1[i + 1][prev]) {
					break;
				}
			}

			REP(n, prev) {
				if ((colors[i] == 'R' && flag[n]) || (colors[i] == 'B' && !flag[n])) {
					dp1[i][n] = true;
				}
			}
		}

		vector <int> result(colors.size(), -1);
		REP(i, colors.size()) {
			int counter = 0;
			int answer = -1;
			for (int n = 1; n <= N; ++n) {
				if (dp0[i + 1][n] && dp1[i][n]) {
					++counter;
					answer = n;
				}
			}

			if (counter == 1) {
				result[i] = answer;
			}
		}

		return result;
	}
}

Middle 500 CarrotBoxes

  • そもそも最適な戦略が思いつかないorz
  • 頭悪くて死にそうorz

Hard 975 StrangeElevator

  • 多分約数だけ考えればよくて・・・
  • NとHでメモ付きdfsすれば良さそうなのだけれど・・・
  • 肝心の式が立たないorz

Challenge Phase

  • 眺めているだけでした

System Test

o x x 1892->1901

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