Hatena::Grouptopcoder

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

 | 

2011-05-21

Yandex.Algorithm 2011 Round 1 10:24 Yandex.Algorithm 2011 Round 1 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Yandex.Algorithm 2011 Round 1 - nodchipのTopCoder日記 Yandex.Algorithm 2011 Round 1 - nodchipのTopCoder日記 のブックマークコメント

A. Domino

  • いつもより難しい
  • 多分簡単な規則を作ってそのとおりに並べれば良いはず
aabbaabbaabb...
bbaabbaabbaa...
fddeeddeedde...
fddeeddeedde...
  • こんな感じでよさそう
  • それにしてもコードが汚い・・・
  • Accepted
int main() {
	std::ios::sync_with_stdio(false);
	
	int N;
	cin >> N;

	if (N == 1) {
		cout << "a\na\nb\nb\n";
		return 0;
	}

	if (N == 2) {
		cout << "aa\nbb\ncc\ndd\n";
		return 0;
	}

	int even = 0;
	int x = 0;
	while (x < N) {
		if (x + 1 == N) {
			cout << "c";
			++x;
		} else {
			cout << (char)('a' + even);
			cout << (char)('a' + even);
			x += 2;
			even ^= 1;
		}
	}
	cout << endl;

	even = 1;
	x = 0;
	while (x < N) {
		if (x + 1 == N) {
			cout << "c";
			++x;
		} else {
			cout << (char)('a' + even);
			cout << (char)('a' + even);
			x += 2;
			even ^= 1;
		}
	}
	cout << endl;

	even = 0;
	cout << "f";
	x = 1;
	while (x < N) {
		if (x + 1 == N) {
			cout << "f";
			++x;
		} else {
			cout << (char)('d' + even);
			cout << (char)('d' + even);
			x += 2;
			even ^= 1;
		}
	}
	cout << endl;

	even = 1;
	cout << "f";
	x = 1;
	while (x < N) {
		if (x + 1 == N) {
			cout << "f";
			++x;
		} else {
			cout << (char)('d' + even);
			cout << (char)('d' + even);
			x += 2;
			even ^= 1;
		}
	}
	cout << endl;
}

B. Embassy Queue

  • シミュレーションゲーきた
    • (実はDPゲー)
  • タイムドリブンで進めるとTLEするのでイベントドリブンで行う
  • 3つの窓口を一つのルーチンで処理したいけど、整理するのが面倒なので愚直に書く
  • それにしてもコードが汚い・・・
  • Accepted
enum {
	WAITING_A,
	FINISHED_A,
	WAITING_B,
	FINISHED_B,
	WAITING_C,
	FINISHED_C
};

struct STATE {
	ll eventTime;
	int state;
	int index;
	STATE(ll eventTime, int state, int index) : eventTime(eventTime), state(state), index(index) {}
	bool operator < (const STATE& rh) const {
		return eventTime > rh.eventTime;
	}
};

int main() {
	std::ios::sync_with_stdio(false);

	int k1, k2, k3;
	ll t1, t2, t3;
	cin >> k1 >> k2 >> k3 >> t1 >> t2 >> t3;
	priority_queue<STATE> q;

	vector<ll> cs;
	int N;
	cin >> N;
	REP(n, N) {
		ll c;
		cin >> c;
		q.push(STATE(c, WAITING_A, n));
		cs.push_back(c);
	}

	ll answer = -1;
	int rest1 = k1;
	int rest2 = k2;
	int rest3 = k3;
	queue<int> waiting1;
	queue<int> waiting2;
	queue<int> waiting3;

	while (!q.empty()) {
		const STATE state = q.top();
		q.pop();

		switch (state.state) {
		case WAITING_A:
			{
				if (rest1 == 0) {
					waiting1.push(state.index);
				} else {
					--rest1;
					q.push(STATE(state.eventTime + t1, FINISHED_A, state.index));
				}
				break;
			}
		case FINISHED_A:
			{
				q.push(STATE(state.eventTime, WAITING_B, state.index));
				++rest1;
				if (!waiting1.empty()) {
					const int index = waiting1.front();
					waiting1.pop();
					--rest1;
					q.push(STATE(state.eventTime + t1, FINISHED_A, index));
				}
				break;
			}
		case WAITING_B:
			{
				if (rest2 == 0) {
					waiting2.push(state.index);
				} else {
					--rest2;
					q.push(STATE(state.eventTime + t2, FINISHED_B, state.index));
				}
				break;
			}
		case FINISHED_B:
			{
				q.push(STATE(state.eventTime, WAITING_C, state.index));
				++rest2;
				if (!waiting2.empty()) {
					const int index = waiting2.front();
					waiting2.pop();
					--rest2;
					q.push(STATE(state.eventTime + t2, FINISHED_B, index));
				}
				break;
			}
		case WAITING_C:
			{
				if (rest3 == 0) {
					waiting3.push(state.index);
				} else {
					--rest3;
					q.push(STATE(state.eventTime + t3, FINISHED_C, state.index));
				}
				break;
			}
		case FINISHED_C:
			{
				answer = MAX(answer, state.eventTime - cs[state.index]);

				++rest3;
				if (!waiting3.empty()) {
					const int index = waiting3.front();
					waiting3.pop();
					--rest3;
					q.push(STATE(state.eventTime + t3, FINISHED_C, index));
				}
				break;
			}
		}
	}

	cout << answer << endl;
}

C. Petya and Tree

  • これは自分より下の最小値と最大値を覚えていおけば良い気がする
  • でもそれだと左右のどちらかに偏ったときに結局全部探索しなければならなくなる
  • ううむ・・・

D. Sum of Medians

  • データ構造系かな
  • 無理ゲーっぽい

E. Guard Towers

  • 読んでいません

Hack

  • このAのコード1で落ちる気がする
  • Hack
  • Unsuccessful hacking attempt
  • 手元に書き写したらちゃんと処理できてたorz
  • ・・・
  • この赤コーダーさんが時間ぎりぎり出だしてきたBのコード、一番最後の人の待ち時間を決め打ちで出力してる
  • これ間違ってるよね・・・?
  • 今度は慎重に手元に書き写してWAすることを確認する
1 1 1
100000 100000 100000
3
1 1 1000000000
  • このデータで落ちることを確認した
  • Hack
  • Successful hacking attempt
  • ・・・
  • 予選は突破できそうにないけどもうちょっと点数がほしい
  • Dで青い人がだしているコードを読みたい
  • TLEするコードを書いてDに投入
  • 青い人のコードを読んでみる
  • ・・・
  • これTLEコードに見えるんだけど・・・
  • 最大ケースを投入
  • Unsuccessful hacking attempt
  • ・・・
  • オワタorz

結果

|#|Who|=| *|A|B|C|D|E|

233nodchip1306+1 / -2478 00:11828 00:43 -1

CarleyCarley2011/07/09 20:24Haha, shouldn't you be charging for that kind of konwelgde?!

sexdlxkdwsexdlxkdw2011/07/10 00:55lkiUo5 <a href="http://rhlbmjtdxilb.com/">rhlbmjtdxilb</a>

ziuspqnziuspqn2011/07/10 20:35jNaMKe , [url=http://jsmvmigwzcph.com/]jsmvmigwzcph[/url], [link=http://kqoenzxqgvht.com/]kqoenzxqgvht[/link], http://ajparvhxvutj.com/

suhxengsuhxeng2011/07/11 20:04OtooAN <a href="http://ihufhsoyawgk.com/">ihufhsoyawgk</a>

qiabauaqiabaua2011/07/12 22:28regDJF , [url=http://aejwtwybkqyf.com/]aejwtwybkqyf[/url], [link=http://zxuratibfkgo.com/]zxuratibfkgo[/link], http://txatzrgfzozq.com/

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