TopCoder SRM 329 Div1 Medium LogCutter
問題
長さLの丸太がある。
整数A,Kが与えられて、
この丸太を、 ( (A * i) mod (L - 1) ) + 1 (1≦i≦K)の位置で切ることができる。
丸太を最大でC回まで切ることができ、
丸太の最長の部分の長さを最小にするように切りたい。
最長の部分の長さの最小値および、その切断における一番左端の切断位置を求めよ。
左端の切断位置が複数ありえる場合は、最小のものを選ぶものとする。
制約条件
L≦1000000000
A≦1000000000
K,C≦10000
方針
切れ目を入れられる位置は、左側のほうでは密集していて、右側のほうでは疎になっている。
なので、右側から切れるだけ貪欲に切っていって、切れなければ切れないと判定するような二分法をしてみたら通ってしまった。
最初の切れ目の位置は、左から全通り試して、最初に解があった位置で切るようにすればいい。
ソースコード
vi pos; bool can(int cut,int len,int s){ int p=pos.back(); rep(i,cut){ p=*lower_bound(all(pos),p-len); } return p<=pos[s]; } class LogCutter { public: string bestCut(int L, int A, int K, int C) { pos.clear(); rep(i,K)pos.pb(A*(i+1ll)%(L-1)+1); pos.pb(0); pos.pb(L); sort(all(pos)); pos.erase(unique(all(pos)),pos.end()); int lo=0, hi=L, mid; while(lo+1<hi){ mid=(lo+hi)/2; if(can(C+1,mid,0))hi=mid; else lo=mid; } for(int i=1;i<pos.size()-1;i++)if(can(C,hi,i)){ stringstream ss; ss<<hi<<" "<<pos[i]; return ss.str(); } } };