Hatena::Grouptopcoder

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

 | 

2010-12-05

Codeforces Beta Round #43 (ACM-ICPC Rules) 21:08 Codeforces Beta Round #43 (ACM-ICPC Rules) - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Codeforces Beta Round #43 (ACM-ICPC Rules) - nodchipのTopCoder日記 Codeforces Beta Round #43 (ACM-ICPC Rules) - nodchipのTopCoder日記 のブックマークコメント

Problem A. Ball Game

  • ループを回しておしまい
  • ・・・
  • サンプル合わない!?
  • なんぞこれ!?
  • ・・・
  • 訂正きた!
  • サンプル合った!
  • Submit
  • 結果: Accepted
int main() {
	int N;
	cin >> N;
	int index = 0;
	REP(i, N - 1) {
		index += i + 1;
		index %= N;
		if (i) {
			cout << " ";
		}
		cout << index + 1;
	}
	cout << endl;
}

Problem B. T-shirts from Sponsor

  • やるだけ
  • もうちょっとハードコーディングを綺麗に書きたかった・・・
  • 結果: Accpted
int main() {
	int N[5];
	REP(i, 5) {
		cin >> N[i];
	}

	const int choice[5][5] = {
		{0, 1, 2, 3, 4},
		{1, 2, 0, 3, 4},
		{2, 3, 1, 4, 0},
		{3, 4, 2, 1, 0},
		{4, 3, 2, 1, 0}
	};
	map<string, int> dic;
	dic.insert(MP("S", 0));
	dic.insert(MP("M", 1));
	dic.insert(MP("L", 2));
	dic.insert(MP("XL", 3));
	dic.insert(MP("XXL", 4));
	vector<string> names;
	names.push_back("S");
	names.push_back("M");
	names.push_back("L");
	names.push_back("XL");
	names.push_back("XXL");

	int K;
	cin >> K;
	REP(k, K) {
		string in;
		cin >> in;
		const int best = dic[in];
		REP(i, N) {
			if (N[choice[best][i]]) {
				cout << names[choice[best][i]] << endl;
				--N[choice[best][i]];
				break;
			}
		}
	}
}

Problem C. Hamsters and Tigers

  • 貪欲臭がする
  • なんだろう・・・
  • 始点を固定してハムとトラを並べればいいのかなぁ
  • クイックソートでこんなコード書いたなぁ・・・
  • サンプル合った
  • Submit
  • 結果: Accepted
int f(string s, char a, char b) {
	int left = 0;
	int right = s.size() - 1;
	int counter = 0;
	while (left < right) {
		while (left < right && s[left] == a) {
			++left;
		}
		while (left < right && s[right] == b) {
			--right;
		}
		if (left < right && s[left] != a && s[right] != b) {
			++counter;
			swap(s[left], s[right]);
		}
	}
	return counter;
}

int main() {
	int N;
	cin >> N;
	string in;
	cin >> in;
	int answer = INT_MAX;
	REP(offset, N) {
		string rot = in.substr(offset) + in.substr(0, offset);
		answer = min(answer, f(rot, 'T', 'H'));
		answer = min(answer, f(rot, 'H', 'T'));
	}
	cout << answer << endl;
}

Problem D. Parking Lot

  • シミュレーションやるだけっぽい
  • 最初と最後の条件書くの面倒くさいなぁ
  • 番兵置けば全部一括でできる・・・?
  • できそう
  • 書いた
  • Submit
  • 結果: Accepted
struct Car {
	int back;
	int front;
	int index;
	Car(int b, int f, int i) : back(b), front(f), index(i) { }
};

int main() {
	int L, b, f, N;
	cin >> L >> b >> f >> N;
	vector<Car> cars;
	cars.push_back(Car(-b, -b, -1));
	cars.push_back(Car(L + f, L + f, -1));

	for (int index = 1; index <= N; ++index) {
		int command, arg;
		cin >> command >> arg;
		if (command == 1) {
			int answer = -1;
			for (int i = 0; i < cars.size() - 1; ++i) {
				if (cars[i + 1].back - cars[i].front >= arg + f + b) {
					answer = cars[i].front + b;
					cars.insert(cars.begin() + i + 1, Car(cars[i].front + b, cars[i].front + b + arg, index));
					break;
				}
			}
			cout << answer << endl;
		} else {
			REP(i, cars.size()) {
				if (cars[i].index == arg) {
					cars.erase(cars.begin() + i, cars.begin() + i + 1);
				}
			}
		}
	}
}

Problem E. Comb

  • Combって何だっけ?・・・櫛?
  • とりあえずDP
  • 偶数段目では自分より左上から、奇数弾目では自分より右上から最大のものをとればよいらしい
  • でも最大のものを取るときに線形で取ってくるとオーダーがまずいから・・・
  • 端からやるときに一つ前の最大の値を保持しておけばいいか・・・
  • サンプル合った
  • Submit
  • TLE
  • がーん
  • 計算量O(nm)なのに何で・・・
  • ・・・
  • cin が遅いから・・・?
  • 手元で最悪ケースを走らせてみる
  • ・・・
  • 止まらないorz
  • scanf()に書きなおしてみる
  • ・・・
  • 止まったorz
  • ついでに64bit溢れ直した
  • Submit
  • 結果: Accepted
int main() {
	int H, W;
	scanf("%d%d", &H, &W);
	static ll score[2048][2048];
	REP(h, H) {
		REP(w, W) {
			int value;
			scanf("%d", &value);
			score[h][w] = value;
		}
		for (int w = 1; w < W; ++w) {
			score[h][w] += score[h][w - 1];
		}
	}

	static ll dp[2][2048];
	CLEAR(dp);
	int front = 0;
	int back = 1;

	REP(y, H) {
		if (y % 2 == 0) {
			ll last = INT_MIN;
			dp[front][0] = INT_MIN;
			for (int x = 1; x < W; ++x) {
				last = max(last, dp[back][x - 1]);
				dp[front][x] = score[y][x] + last;
			}
		} else {
			ll last = INT_MIN;
			dp[front][W - 1] = INT_MIN;
			for (int x = W - 2; x >= 0; --x) {
				last = max(last, dp[back][x + 1]);
				dp[front][x] = score[y][x] + last;
			}
		}
		swap(front, back);
	}

	cout << *max_element(dp[back], dp[back] + W) << endl;
}

Problem F. Hercule Poirot Problem

  • 皆目検討がつかない
  • とりあえず鍵を開けられるときは鍵を閉められるよなぁ
  • 鍵を開けまくって木曜日と金曜日を比較して同じ状態になればおkとか?
  • 書いてみた
  • Submit
  • 結果: Wrong Answer
  • 解法が分かりませんでしたorz

Problem G. Emperor's Problem

  • 皆目検討がつかない
  • orz

Results

#Who=PenaltyABCDEFG
42 nodchip5191+ 00:12+ 00:19+ 00:26+ 00:43+1 01:11-1

Rating: 1876->1963 うまく行くと次回赤コーダー・・・。ムリかな?

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