kojingharangの日記

Google code jam 2015 Round1A B. Haircut

19:29 |

• B個の1人用床屋があり床屋 i は 1 人切るのに M[i] 分(整数)かかる。行列ができており、同時に複数の店が空いたら i が小さい店にすぐ入る。N人目の人は何番の床屋で切ることになるか？
• (Large) 1≦テストケースの数≦100, 1≦N≦10^9, 1≦B≦1000, 0≦M[i]≦100000

• small はとりあえず LCM(M) を求めて N % その時間までに切り終わった人数までシミュレート。
• ぱっと思いつかなかったので、C small 解いて戻ってきたところ、時刻を決めると切り終わった人数が O(B) で分かることに気づく
• そんな感じで二分探索して Bl.cpp を書く → Bs.cpp で解いた B-small の結果と一致 → large download, 実行
• あ
• Bl.cpp と思っていたビルド＆実行ソースは Bs.cpp だった....。Bl.cpp はただの 1 回も実行されてなくてバグりまくり → 8分デバッグ → 死

• (あとで)
• N 人目が始まる最小の時刻は簡単には求められないんじゃないかと思って累計 N-1 人終わったあたりをぐにぐにしてたが、
• t が終わった時点で始まってる人数は Σ t/M[i]+1 と終了人数 + B で簡単に求まるのだった。終わったらすぐ始まるのだから、そりゃそうだ。
• N 人目が始まった時刻には実際のところ複数の人が始まってる可能性があるので、B を後ろからみてって割り切れるとこをカウントして N になったとこが答え。

• 終わった人数基準でやるなら、N 人目が始まる時刻の下限であるのべ N-B 人が終わった時刻からシミュレートすればよい。(10^8 なのでOK)

• コマンドライン安全標語: 一、自分を信用するべからず

• Accepted in practice

int main() {
	int test_cases;
	cin>>test_cases;
	ll B,Nth;
	string s;
	REP(ttt, test_cases) {
		cin>>B>>Nth;
		VI w(B);
		REP(i, B) cin>>w[i];
		ll lo=-1, hi=1LL<<60; // hi ... began at least N
		while(lo+1<hi) {
			ll mid = (lo+hi)/2;
			ll began = 0;
			REP(i, B) began += mid / w[i] + 1;
			if(began<Nth) lo=mid; else hi=mid;
		}
		ll t = hi;
		ll began = 0;
		REP(i, B) began += t / w[i] + 1;
		ll beganP = 0;
		REP(i, B) beganP += (t-1) / w[i] + 1;
		assert(beganP<Nth);
		assert(Nth<=began);
		int ans = 0;
		for(int i=B-1;i>=0;i--) {
			if(t%w[i]==0) {
				if(began--==Nth) {ans = i+1; break;}
			}
		}
		cout<<"Case #"<<ttt+1<<": "<<ans<<endl;
	}
	return 0;
}

ツイートする