AtCoder ARC #021 : C - 増築王高橋君

オーバーフローに苦しめられた問題。
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は二分探索の上限)で済む。

なお注意点。
建物が１つで、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);
}

まとめ

オーバーフローさえなければさっくり解けたのに…。