kojingharangの日記

Google code jam 2015 Round1B C. Hiking Deer (Update: largeもやった)

18:27 |

• シカとヒトN人が単位円上を1方向に歩く。シカのスタート時のヒトの初期位置と周期（定速で周る）が与えられる。
• シカは任意の正の速度で移動できるとき、シカが1周するまでにすれ違うヒトの最少人数を求めよ。
• 周期≦10^9 +α
• Small1: N≦2 Small2: N≦10 Large: N≦500000

• Small1 だけ。
• 各ヒトに対して、シカがすれ違わずにゴールできる時刻の範囲が決まる。
• 具体的には、シカのスタート後、そのヒトがシカのスタート地点を1回通過する時刻〜2回通過する時刻まで。
• ヒト2人に対するその範囲の共通部分があれば 0 人にできる。共通部分がなければ最低 1 人とすれ違う必要がある。
• Small2 以降は謎。時刻を決め打ちして云々的な？

• Small1: Accepted

int main() {
	int test_cases;
	cin>>test_cases;
	ll N, D, H, M;
	string s;
	REP(ttt, test_cases) {
		cin>>N;
		vector<PII> w;
		REP(i, N) {
			cin>>D>>H>>M;
			REP(j, H) w.PB(MP(M+j, D));
		}
		sort(ALL(w));
		ll ft = w[0].first * (360 + 360-w[0].second);
		ll st = w[1].first * (360-w[1].second);
		ll ans = st>=ft ? 1 : 0;
		cout<<"Case #"<<ttt+1<<": "<<ans<<endl;
	}
	return 0;
}

(追記)

• Large も基本的にヒト毎にすれ違い回数は独立に足せることを利用する。
• 各ヒトについてすれ違い回数が 0, 1, 2, ... になるような時刻の区間が定まるので、それらをソートしておいて、すれ違い回数が変化するとこで変化させていく。

• ...書いたが WA がとれないので SnapDragon さんのを動かしたりするぢっと見たりする
• そうだ -1, +1 おわり ではなく -1, +1, +1, ... とどんどん増えていくのだ

• まとめると

• すれ違い回数の初期値は t=0 でゴールするときなので全員分
• まだ考慮していない変化データとその時刻を priority_queue で管理して、変化分を足し込んでいく。
• 見たら次周のために +1 なデータを push
• すれ違い回数はいずれ単調増加になるので、人数を超えたあたりで適当に終了。念のため人数*2にしとく

• はまりどころ
• push の前で top を見てた
• -1 が人数分出るまでループを回すと -1 が長い周期になっててループが10^9回くらいになる可能性があるのですれ違い回数で打ち切る必要がある

• Small1, Small2, Large: Accepted in practice

int main() {
	int test_cases;
	cin>>test_cases;
	ll N, D, H, M;
	string s;
	REP(ttt, test_cases) {
		cin>>N;
		priority_queue<pair<ll, pair<ll, ll>>> q;
		ll all = 0;
		REP(i, N) {
			cin>>D>>H>>M;
			REP(j, H) q.push(MP(-(M+j)*(360-D), MP(-1, (M+j)*360)));
			all+=H;
		}

		ll ans = 1LL<<60;
		ll cur=all;
		while(q.size() && cur < all*2) {
			ll t = -q.top().first;
			ll dn = q.top().second.first;
			ll dur = q.top().second.second;
			q.pop();
			cur+=dn;
			q.push(MP(-(t+dur), MP(1, dur)));
			if(t != -q.top().first) {
				ans = min(ans, cur);
			}
		}
		ans = min(ans, cur);
		cout<<"Case #"<<ttt+1<<": "<<ans<<endl;
	}
	return 0;
}

ツイートする