2014年05月03日17時23分23秒に更新されたバージョンを表示しています.
最新のページはこちらをご覧ください.
Codeforces Round #243 DIV1 A問題 (1500pt)
Codeforces Round #243 DIV2 C問題 (2500pt)
Problem description
$N$ 要素の正整数列 $\{A_k\}_{k=1}^N$ と,$M$ 要素の正整数列 $\{B_k\}_{k=1}^M$ が与えられる.
最初エネルギーが $S$ だけある.
次の操作を好きなだけ繰り返す:
最後に,今まで削除した要素の数だけエネルギーを使わなければいけない.
最終的にエネルギーは $0$ を下回ってはいけない.
最高で,何円もらえるかを求める問題.
まず,$E$ の最小値が $10^3$ であることから,答えは高々 $300$ である.
これを念頭にDPを行う.
状態として(今何円もらったか,$\{A_k\}$ で最後に使った要素の番号)を用い,$\{B_k\}$ の最後に使った要素の番号の最小値を計算する.
これがわかれば,あるお金をもらうのに必要な最小エネルギーを計算することができるようになる.
何円もらったかを小さい方から見ていき,それが同じものは,要素の番号が小さい方から計算していく.
$A_k$ を最後に使う場合は,$A_j, \; j < k$ のうち,最後に使った要素が最も早い要素の次の $B_x = A_k$ なる要素を見つけて,$x$ をDPテーブルに保存すれば良い.
ここで,$B_x$ を見つけるには,各 $z$ に対して $B_y = z$ なる $y$ の配列を作っておいて二分探索すれば良い.
時間計算量は $O(S/E \times N \log M),\; S/E \leq 300$ 程度.
#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<string>
#include<utility>
#include<iostream>
#include<cmath>
#include<ctime>
#include<cassert>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define INF 1000000000
#define mygc(c) (c)=_getchar_nolock()
#define mypc(c) _putchar_nolock(c)
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 writer(int x, char c){int i,sz=0,m=0;char buf[10];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}
int N, M, S, E, A[110000], B[110000];
vector<int> place[110000];
int pt[110000], nx[110000];
int main(){
int i, j, k, mn, ok;
int res;
reader(&N);
reader(&M);
reader(&S);
reader(&E);
rep(i,N) reader(A+i);
rep(i,M) reader(B+i);
rep(i,M) place[B[i]].push_back(i);
rep(i,N) pt[i] = -1;
for(res=0;;res++){
mn = INF; if(res==0) mn = -1;
ok = 0;
rep(i,N){
k = lower_bound(place[A[i]].begin(), place[A[i]].end(), mn+1) - place[A[i]].begin();
mn = min(mn, pt[i]);
if(k == place[A[i]].size()){ nx[i]=INF; continue; }
nx[i] = place[A[i]][k];
if(S - E*(res+1) - (i+1) - (nx[i]+1) >= 0) ok = 1;
}
if(!ok) break;
rep(i,N) pt[i] = nx[i];
}
writer(res, '\n');
return 0;
}
Current time: 2024年05月03日06時47分54秒
Last modified: 2014年05月03日17時23分23秒 (by laycrs)
Tags: Competitive_Programming Codeforces CF243 CF_Div1_C CF_Div2_E
トップページに戻る
Logged in as: unknown user (not login)