保存されている過去のバージョンの一覧

2015年01月20日07時54分25秒

Codeforces Round #286 DIV1 A問題/DIV2 C問題 - Mr. Kitayuta, the Treasure Hunter

Source

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$ 程度の配列を取ったほうが良い．

C++のスパゲッティなコード

#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年04月25日15時42分21秒
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)

ログイン：