kojingharangの日記

Facebook Hacker Cup Round2

19:15 |

起きれたけど o-- (rank 353/407) で Round3 進出ならず。

Round3 勢がんばってください

ツイートする

Facebook Hacker Cup Round2 A - Cake Cutting

19:15 |

• 長さ N の数列 A が与えられる。まるいケーキがあって、A の各要素について A[i] 回折れ曲がる線でカットする。ただし折れ曲がる点はケーキ内に限定する。ケーキは最大何個の部分に分けられるか求める問題。
• 1≦N≦100, 1≦A[i]≦400 for i in [0, N)
• 図 https://www.facebook.com/hackercup/problems.php?pid=500995316613418&round=499927843385312

• 直ちに影響がある眠さ（朝６時）

• 円卓に座ったビジネスマンが握手するやつに似てるので何らかのDPかな
• ...
• １時間くらい

• 各カットについて、
• (1) そのカット自身だけで生じる部分 ... ((A[i]-1)*A[i]/2)
• (2) すでにカットした線分の数に依存する部分 ... すでにカットした線分の数 * (A[i]+1) +1
• の領域が新たに発生することにしたらサンプルが通った。証明できないしもしもっと複雑な事情であっても分からないだろうからこれでサブミット

• Accepted (おー)

int main() {
	int T;
	cin>>T;
	REP(ttt, T) {
		ll N;
		cin>>N;
		VI A(N);
		REP(i, N) cin>>A[i];
		
		ll lines=0;
		ll ans=1;
		
		REP(i, N) {
			ans += lines*(A[i]+1) + ((A[i]-1)*A[i]/2) +1;
			lines += A[i]+1;
		}
		cout<<"Case #"<<ttt+1<<": "<<ans<<endl;
//		break;
	}
	return 0;
}

ツイートする

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;
}

ツイートする