Codeforces Round #286 DIV1 C問題 (1750pt)
Codeforces Round #286 DIV2 E問題 (2750pt)
Problem description
$N$ 本の竹がある．
竹 $i$ は，最初は高さ $H_i$ で，毎日高さが $A_i$ ずつ伸びる．
毎日，合計で $K$ 回以下だけ，竹をマジックハンマーで叩くことができる（同じ日に同じ竹を何回叩いても良い）．
叩くと，高さが $P$ だけ減るが，高さが $0$ 未満になる場合は，その代わりに高さが $0$ になる．
一日の流れは，竹を叩き，その後に全ての竹が伸び，一日が終わるという流れ．
$M$ 日後に最も高い竹の高さを最小化したい．
最小値を求める問題．
答えに対する二分探索をする．
答えを決めつけると，各竹について，逆算して，叩くことによって合計でいくら以上高さを減らさなければいけないというのが求まる．
ある竹 $i$ について，$k = P \alpha + \beta, \;\; 0 \leq \beta < P, \; \alpha \in {\mathbb Z}_{\geq 0}$ 以上の高さを減らさないといけないとする．
更に，今，$\beta \neq 0$ とすると，必ず $\alpha + 1$ 回は叩かなければいけないのは自明．
それぞれの $j = 0,1,\ldots,\alpha$ について，$H_i + x A_i \geq j P + \beta$ を満たす最小の $x$ を求めて，$x$ 日目以降に叩けば $\alpha+1$ 回叩くことで条件をみたすことができる．
これは，最初は高さ $\beta$ 以上になってから叩く，という風になっていて，次からも，減らさなければいけない高さまで育ってから叩くという感じになっている．
（$2$ 回目は，$1$ 回目に $\beta$ しか減らさなかったら $P$ だけ減らせるまで待って，$\beta+1$ 減らしたら，$P-1$ 減らせるまで待って，…という風になっている．）
また，高さ $\beta$ まで育つ前に叩いても，何も得にならない．
つまり，叩く回数は $1$ 増えるし，次回から叩くタイミングが早くても良くなるなんてことはない．
よって，それぞれ叩くときに条件を満たす日にちの中で最も早い日にちを選んで叩けば良い．
また，$\beta = 0$ の時は，合計 $\alpha$ 回だけ叩けば良く，上の式で $j=0$ の時は叩かなくて良い．
まとめると，答えを決めつけた後，それが達成可能かどうかを貪欲に判定できる．
時間計算量は $O( (N+MK) \log (H_i + A_i M))$ ぐらい．
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define READER_BUF_SIZE 1048576
#define WRITER_BUF_SIZE 1048576
int reader_pt=READER_BUF_SIZE,reader_last;char reader_buf[READER_BUF_SIZE];
int writer_pt=0;char writer_buf[WRITER_BUF_SIZE];
#define mygc(c) {if(reader_pt==READER_BUF_SIZE)reader_pt=0,reader_last=fread(reader_buf,sizeof(char),READER_BUF_SIZE,stdin);(c)=reader_buf[reader_pt++];}
#define mypc(c) {if(writer_pt==WRITER_BUF_SIZE)writer_pt=0,fwrite(writer_buf,sizeof(char),WRITER_BUF_SIZE,stdout);writer_buf[writer_pt++]=(c);}
#define myed {fwrite(writer_buf,sizeof(char),writer_pt,stdout);writer_pt=0;}
#define ll long long
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}
template <class T, class S, class U, class V> void reader(T *x, S *y, U *z, V *w){reader(x);reader(y);reader(z);reader(w);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}
template<class T1, class T2> void sort(int N, T1 a[], T2 b[], void *mem){int i;pair<T1,T2> *r=(pair<T1, T2>*)mem;rep(i,N)r[i].first=a[i],r[i].second=b[i];sort(r,r+N);rep(i,N)a[i]=r[i].first,b[i]=r[i].second;}
int N;
ll H[111111], A[111111];
int M, K; ll P;
int rem[5100], nx[5100];
int get_nx(int a){
if(a >= M) return M;
if(rem[a]) return a;
return nx[a] = get_nx(nx[a]);
}
int main(){
int i, j, ng;
ll L, R, C, dec, tm, sm, x;
void *mem = malloc(77000000);
reader(&N, &M, &K, &P);
rep(i,N) reader(H+i, A+i);
sort(N, A, H, mem);
L = 0;
R = 100000000000000LL;
rep(i,N) L = max(L, A[i]);
while(L < R){
C = (L+R) / 2;
rep(i,M) rem[i] = K, nx[i] = i+1;
ng = 0;
rep(i,N){
dec = (H[i] + A[i] * M) - C;
if(dec <= 0) continue;
tm = dec / P;
sm = dec % P;
if(sm){
x = (sm - H[i] + A[i] - 1) / A[i];
x = max(0LL, x);
x = get_nx(x);
if(x >= M){ ng=1; break; }
rem[x]--;
}
rep(j,tm){
x = (sm + (j+1)*P - H[i] + A[i] - 1) / A[i];
x = max(0LL, x);
x = get_nx(x);
if(x >= M){ ng=1; break; }
rem[x]--;
}
if(ng) break;
}
if(ng) L = C+1; else R = C;
}
writerLn(L);
myed;
return 0;
}
Current time: 2024年04月26日08時04分06秒
Last modified: 2015年01月20日08時02分15秒 (by laycrs)
Tags: Competitive_Programming Codeforces CF286 CF_Div1_C CF_Div2_E
トップページに戻る
Logged in as: unknown user (not login)