Codeforces #593 Div2 E. Alice and the Unfair Game

微妙にとっつきにくい問題。
http://codeforces.com/contest/1236/problem/E

問題

N個の並んだ箱を使ったゲームを行う。
先手は最初いずれかの箱に人形を入れる。
その後、後手がM回箱の番号を指定するので、人形の入った箱を当てられないようにしたい。
後手の初回の手番の前と、毎回の手番のあとの計(M+1)回、先手は人形を隣接する箱に移すことができず。

先手が人形の位置を当てられずに済むような初期位置と最後の位置の対は何通りか。

解法

N=1の時は自明。
N=2以上の場合、初期位置に対し最後の位置は区間になる。
そこで、各マスに対し初期位置からどこまで右に行けるかを考えよう(その後、同様に左に行くケースを考える)。

先手の手番ではそれぞれ人形は右に動かすが、動かすと後手に当てられてしまう場合、動かせない。
これを(初期位置毎に応じて)各段階で各箱の位置にいる人形の数を考えるようにすると、ほとんどのケースでは要素を1つシフトする必要がある。
そこで、実際のシフトを行わずindexの初期位置を1ずらすことで対応しよう。
これで各人形がどこまで右に動かせるか高速に求められる。

int N,M;
int A[101010];
int dp[301010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>A[i];
		A[i]--;
	}
	
	if(N==1) return _P("0\n");
	
	ll ret=N;
	FOR(i,2) {
		ZERO(dp);
		FOR(j,N) dp[j]=1;
		FOR(j,M) {
			dp[j+1]+=dp[j];
			dp[j]=0;
			dp[j+A[j]+2]+=dp[j+A[j]+1];
			dp[j+A[j]+1]=0;
		}
		dp[M+1]+=dp[M];
		int st=0;
		FOR(j,N) FOR(x,dp[M+1+j]) {
			assert(st>=j);
			ret+=(st++)-j;
		}
		FOR(j,M) A[j]=N-1-A[j];
	}
	cout<<ret<<endl;
}

まとめ

なんか今回こういうシミュレーション系多いな。