kojingharangの日記

Facebook Hacker Cup Round2 B - RoboElection

23:25 |

• N台のロボットがいて何回か投票することになった。投票率がP%以上になるまで先頭のK台が消されていく。ロボットはlazyなので自分が消される可能性があるときだけ投票する。各ロボットが最適に動いた場合に何回の投票が行われるかを求める問題。
• 0＜K≦N≦10**12, 0＜P≦100

• よくわからんので遅いけど正しい naive 解を作ることにする

• K台ずつ消されてくので、K台ごとに運命共同体グループに分ける。最後のグループから順に、どう行動するか決めてく。
• 自分らが消されるかどうかが問われる投票にて、自分らの投票数と自分より後のグループの（やむを得ない）投票数が条件を満たすなら当該グループは生き残れる。
• 生き残れるグループはそれより前のグループが消されるかどうか問われる投票では投票しない
• サンプル通る

• で、デバッグ出力とか見てると、投票率がP以上になる→後ろのやつらが投票しなくなるので投票率がガクッと下がる→徐々に上がっていく→...を繰り返すようなので
• 徐々に上がっていく部分を二分探索で高速化してみる
• 仕込んでデバッグしてるうちに終了

• やっぱ証明とか数式立てるとかしてもうちょっとスマートにやりたいもんだなぁ

• ↓あとで 正解者の答えと一致した版 (141s)

ll N, K, P;

int main() {
	int T;
	cin>>T;
	REP(ttt, T) {
		cin>>N>>K>>P;
		ll nz = 0;
		ll ans = 1;
		if(P==100) {
			ans = (N+K-1)/K;
		} else {
			for(ll all=N%K==0 ? K : N%K;all<=N;all+=K) {
				ll n = min(K, all);
				ll vote=n + nz;
				if(vote * 100 >= all * P) {
					nz=0;
					ans = 1;
				} else {
					if(n==K && (N-all)/K > 10) {
						ll lo=0,hi=(N-all)/K;
						int hiv;
						{
							ll n_vote = K + nz + K*hi;
							ll n_all = all + K*hi;
							hiv = (n_vote * 100 >= n_all * P);
						}
						if(hiv) {
							while(lo+1<hi) {
								ll mid = (lo+hi)/2;
								ll n_vote = K + nz + K*mid;
								ll n_all = all + K*mid;
								//cout<<"BS "<<mid<<" "<<(float)n_vote/n_all<<" "<<n_vote<<" "<<n_all<<endl;
								if(n_vote * 100 >= n_all * P) hi=mid; else lo=mid;
							}
							//cout<<"BSS hi="<<hi<<" init hi:"<<(N-all)/K<<" hiv:"<<hiv<<endl;
							ans += hi;
							nz += K*hi;
							all += K*hi - K;
						} else {
							ans++;
							nz += n;
						}
					} else {
						ans++;
						nz += n;
					}
				}
				//all += n;
				//cout<<" "<<n<<" "<<all<<" vote "<<vote<<" r "<<(float)vote/all<<" -> "<<(vote * 100 >= all * P)<<endl;
			}
		}
		cout<<"Case #"<<ttt+1<<": "<<ans<<endl;
//		break;
	}
	return 0;
}

ツイートする