Mr. Kitayuta vs. Bamboos (CF286 C)

CF Programming

Problem - C - Codeforces

クッソ良問.CFのCに置かれて虐殺が起こった.

問題:竹がN本あり,はじめ高さはそれぞれh[i]である. 1日で起こることは,「 (竹を選んで"ハンマーで叩く")をK回以下 → それぞれの竹がa[i]伸びる」 ここで,高さhの竹をハンマーで叩くと,高さはmax(h-p,0)になる(竹が消えるわけではなく、高さが0になる).K回の操作で同じ竹を複数回選んでも良い. M日後の竹の高さのうち最大のもの を最小化せよ.(N,M,K,p,h,aがgiven) N<=10^5 M<=5000 K<=10 他<=10^9

以下解法なので自分で考えたい人は見ないでください.


ヒント:逆










とりあえずにぶたんしたい形なので最後全てt以下になれるかどうか を判定する.
竹の高さをx,その竹の伸びをaとすると,M日に起こることは次のようになる.initをx=h,incをx+=a,decをx=max(x-p,0)とすると,
init dec* inc dec* inc ... dec* inc (dec* incの繰り返しがM回.(dec*はdecの自然数回繰り返し))
この操作列を逆に見る.
すると,incはx-=a,decは,x=0ならx=0~p (一意には定まらない) x>0ならx+=p となる.
逆で見た時に考えやすいように,h→t以下 というのを言い換えると,h以上→tと同値になることがわかる(ある操作列を決めた時に、という意味)
なのでtから考えていってh以上にできればいいことがわかる.最終的にできるだけデカい値になればいいので、decのx=0の時のx:=0~p というのをx:=pだとしてよい.こうするとx-=aができなくなったところ(つまりx<aになったところ)でx+=pをする を繰り返し、最後にh以上になるようにx+=pを繰り返す ができるだけギリギリな成功方法だとわかる.これを各竹に対して足しあわせて, ギリギリ度を緩和(早めにやる分にはOKなので(i日目まででi*K回以下ならOK)して大丈夫なら出来る. x-=aができなくなるところは割り算すればわかるのでO(1)で次のヤバイところがわかって、全体でMK回しかハンマーは使えないのでMKより大きくなったら打ち切ってNOを返せば各判定はO(MK+N)でできる.

最初の逆に考える っていうのが難関すぎる・・・
一見逆に見ても同じように思えるけど、冷静に考えると x-=aは確実に実行されないといけない(0未満になってはいけない) というのが大きい(もちろんx+=0~pは全部x+=pだと思っていい という方も重要だけど).そのままの向きだと+bが途中で0になりうるため最終的にどのくらい嬉しいかがわからないんだけど、こっち向きで考えるとそもそも0未満になろうとすることが許されないのでわかる.すごい.

最近のARCのバイナリハック って言う問題の線形解で問題に上がってたので解いてみたけど,めっちゃ面白かった.

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
typedef long long ll;
const int MX=100000;
int N,M,K;
ll a,h[MX],b[MX];
int cnt[5001];
bool can(ll tar){
	int sum=0;
	rep(i,M+1) cnt[i]=0;
	rep(i,N){
		ll x=tar;
		ll t=0;
		while(true){
			ll q=x/b[i];
			if(t+q>=M){
				x-=b[i]*(M-t);
				t=M;
				if(x<h[i]){
					int tmp=(h[i]-x +a-1)/a;
					cnt[t]+=tmp;
					sum+=tmp;
					if(sum>M*K) return 0;
				}
				break;
			}else{
				x%=b[i];
				x+=a;
				t+=q;
				cnt[t]++;
				sum++;
				if(sum>M*K) return 0;
			}
		}
	}
	sum=0;
	rep(i,M+1){
		sum+=cnt[i];
		if(sum>i*K) return 0;
	}
	return 1;
}
int main(){
	cin>>N>>M>>K>>a;
	rep(i,N) cin>>h[i]>>b[i];
	ll ub=1e13,lb=-1;
	while(ub-lb>1){
		ll m=(ub+lb)/2;
		if(can(m)) ub=m;
		else lb=m;
	}
	cout<<ub<<endl;
}