オーバーフローに苦しめられた問題。
http://arc021.contest.atcoder.jp/tasks/arc021_3
問題
N種類の建物がある。
それぞれ初期の価値はA[i]で、1回改築するたびにD[i]価値が増加する。
なお、改築の際に建物の価値と同じだけのコストがかかる。
K回改築するのに必要な最小コストを求めよ。
解法
当然1回の改築にかかるコストが安い順に選びたい。
コストが安い順に改築を行った場合、K回目の改築1回分のコストがPだとする。
まずはPの値を2分探索で求める。
Pを仮置きすると、各建物はA[i]+(x-1)*D[i]<=P、すなわち最大x=1+(P-A[i])/D[i]回改築できることがO(1)で求められる。
よってO(N)の2分探索を100回ぐらい行えばよい。
次に、コスト(P-1)までで実行できる改築回数及び総コストを求める。
こちらは等差数列の総和なのでそれぞれO(1)、全建物でO(N)で処理できる。
コスト(P-1)までの改築回数でK回に満たない分だけコストPで改築すればよい。
全体の時間はO(N logM) (Mは二分探索の上限)で済む。
なお注意点。
建物が1つで、A[i]=D[i]=1000、K=10^8の最大値に対し、総コストは1000*(10^8)*(10^8+1)/2となる。
この際2で割る前の値は約10^19で2^62を超えるため64bit符号有整数だとオーバーフローする。
((10^8)*(10^8+1)/2)*1000のように先に2で割っておくことでオーバーフローを回避できる。
ll K,N; ll A[100001],D[100001]; ll numnum(ll po) { ll ret=0; int i; FOR(i,N) if(po>=A[i]) ret+=1+(po-A[i])/D[i]; return ret; } void solve() { int f,i,j,k,l,x,y; cin>>K>>N; FOR(i,N) cin>>A[i]>>D[i]; ll LL=1,RR=1LL<<40; FOR(i,100) { ll po=(LL+RR)/2; if(numnum(po)>=K) RR=po; else LL=po; } while(numnum(LL)<K) LL++; while(numnum(LL)>K) LL--; ll tot=(LL+1)*(K-numnum(LL)); FOR(i,N) { if(LL<A[i]) continue; ll nu=1+(LL-A[i])/D[i]; tot+=nu*A[i] + D[i]*(nu*(nu-1)/2); } _P("%lld\n",tot); }
まとめ
オーバーフローさえなければさっくり解けたのに…。