Codeforces #286 Div1 A. Mr. Kitayuta, the Treasure Hunter

CF286は不参加でした。ABDは自力で解けたので、出てたらレート微増だったかな。
http://codeforces.com/contest/506/problem/A

問題

0～30000(=M)まで30001個の格子点を含む１次元の数直線がある。
初回、原点からDまでジャンプする。
以降、前回のジャンプ距離をLとすると、次は(L-1),L,(L+1)のいずれかの距離数直線の正の方向にジャンプする。

数直線上、N箇所の格子点にお宝がある。
ジャンプして経由した格子点にあるお宝は入手することができる。
最適にジャンプするとき、得られるお宝の最大数を求めよ。

解法

愚直に解くと[座標][前回のジャンプ距離]でDPすればよいが、これだとO(M^2)かかりTLEする。
そこで何らかの計算量削減が必要である。

直前にxジャンプしてきた場合、次は(x-1),x,(x+1)ジャンプでき、もう１回ジャンプすると合計(2x-3)～(2x+3)のいずれかの距離に到達できる。
よって１発で(2x-3)～(2x+3)の距離にジャンプするケースを考える必要がない。

同様の手順で不要なジャンプの処理を省略することで何とか間に合う。

int N,D;
int P[30300];
int ma;
map<int,int> M[30300];
int sk[60300];
int mama[60300];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>D;
	FOR(i,N) cin>>x, P[x]++;
	
	M[D][D]=P[D];
	for(i=D;i<=30000;i++) {
		ITR(it,M[i]) {
			ma=max(ma,it->second);
			x=it->first;
			if(sk[x+10]==i && it->second<=mama[x+10]) continue;
			for(j=-2;j<=2;j++) {
				sk[x*2+j+10]=i;
				mama[x*2+j+10]=it->second;
			}
			
			if(x>1 && i+x-1<=30000) M[i+x-1][x-1]=max(M[i+x-1][x-1], P[i+x-1]+it->second);
			if(i+x<=30000)          M[i+x][x]    =max(M[i+x][x],     P[i+x]+it->second);
			if(i+x+1<=30000)        M[i+x+1][x+1]=max(M[i+x+1][x+1], P[i+x+1]+it->second);
		}
	}
	
	cout<<ma<<endl;
}

まとめ

Aにしては若干きつい。