2015年01月20日07時54分25秒に更新されたバージョンを表示しています.
最新のページはこちらをご覧ください.
Codeforces Round #286 DIV1 A問題 (500pt)
Codeforces Round #286 DIV2 C問題 (1500pt)
Problem description
$0$ 番から $30000$ 番までの $30001$ 個の島が一列に並んでいる.
最初,島 $0$ から島 $D$ に移動した.
島の移動は,島の番号は増えるようにしか移動できす,前回移動した時に,島の番号が $x$ だけ増えたなら,今回は,島の番号が $x-1$, $x$, $x+1$ のどれかだけ増えるように移動しなければいけない.
また,移動ができなくなったらそれ以上移動しない.
$N$ 個の石があり,それぞれの石がある島の番号 $P_i$ が与えられる.
最高で何個の石を回収できるかを求める問題.
島の数を $k = 30001$ としよう.
今いる島の番号,前回のジャンプ幅(島の番号がいくら増えたか)を状態にして,今まで手に入れた石の数の最大値を計算するDPをすれば良い.
ジャンプの幅を増やし続けたり,減らし続けても,最初のジャンプ幅 $D$ からどれだけ変化できるかというと,高々 $O(\sqrt{k})$ 程度.
実際,$1 + 2 + \cdots + 250 > 30000$ なので,取りうるジャンプ幅は $[D-250, D+250]$ より狭い.
よって,時間計算量,空間計算量ともに $O(k^{1.5})$.
状態を表すのにハッシュを使ってしまったが,定数倍遅く,時間制限 $1$ 秒のところ,$0.8$ 秒程度かかった.
素直に,$30000 \times 500$ 程度の配列を取ったほうが良い.
#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
#define ull unsigned ll
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);}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}
void writer(int x, char c){int s=0,m=0;char f[10];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 T>
struct ullHash{
ull *key; T *val; unsigned memory, size, mask;
void clear(){memset(val,0,size*sizeof(T));}
void clear(int sz){size=1;while(size<sz)size*=2;mask=size-1;clear();}
void init(int mem, int sz){memory=mem;size=1;while(size<sz)size*=2;mask=size-1;if(memory<size)memory=size;key=(ull*)malloc(memory*sizeof(ull));val=(T*)malloc(memory*sizeof(T));if(size)clear();}
int function(ull a){return (a*97531)&mask;}
T get(ull a){int i=function(a);for(;key[i]!=a&&val[i]!=0;)i=(i+1)&mask;if(key[i]!=a) return 0;return val[i];}
void set(ull a, T v){int i=function(a);for(;key[i]!=a&&val[i]!=0;)i=(i+1)&mask;key[i]=a;val[i]=v;}
T increase(ull a, T v = 1){int i=function(a);for(;key[i]!=a&&val[i]!=0;)i=(i+1)&mask;key[i]=a;return val[i]+=v;}
};
int N = 30001, D, M;
int gain[30001];
ullHash<int> hash;
int solve(int now, int d){
int i, j, k, hs = d + now * N;
int res = 0, tmp;
k = hash.get(hs) - 1;
if(k >= 0) return k;
if(d-1 >= 1 && now + (d-1) < N){
tmp = solve(now + d-1, d-1);
res = max(res, tmp);
}
if(now + d < N){
tmp = solve(now + d, d);
res = max(res, tmp);
}
if(now + d+1 < N){
tmp = solve(now + d + 1, d + 1);
res = max(res, tmp);
}
res += gain[now];
hash.set(hs, res+1);
return res;
}
int main(){
int i, j, k;
int res;
hash.init(8000000, 8000000);
reader(&M,&D);
while(M--){
reader(&k);
gain[k]++;
}
res = solve(D, D);
writerLn(res);
myed;
return 0;
}
Current time: 2024年05月05日01時09分47秒
Last modified: 2015年01月20日07時54分25秒 (by laycrs)
Tags: Competitive_Programming Codeforces CF286 CF_Div1_A CF_Div2_C
トップページに戻る
Logged in as: unknown user (not login)