Codeforces #216 Div2. D. Valera and Fools

DとEは正答者少ないけど、Dは自力で解けた。
http://codeforces.com/contest/369/problem/D

問題

1～N番の人が並んでいる。
各人の持つ銃の命中率P[i]が与えられる。

ここで、数Kが与えられ、以下の処理を最大K回行う。

• もし残り人数が1人以下なら終了。
• 各人他の相手を銃で撃つ。各人が狙う相手は生き残っている人のうち、番号の一番若い人を同時に狙う。ただし一番若い番号の人は、自分の代わりに2番目の人を狙う。

上記処理を行ううち、残る人のパターンの組み合わせ数を答えよ。

解法

一番番号の若い人は2番目を狙い、それ以外は一番若い人を狙う。
よって、ありうるパターンはパターンはあるi番目の人と、j～N番目(j>i)の人が残るということになる。
そのため残された人のパターンは(i,j)と2要素の値で表現できる。

また、命中率P[x]の細かい値の違いはあまり関係なく、結局以下の3つに分けられる。

• P[x]==0、すなわち絶対に当たらない
• P[x]==100、すなわち絶対に当たる
• 1<=P[x]<=99、すなわち当たる場合と当たらない場合が両方ありうる

各(i,j)について、1回処理を行うと以下のような状態遷移がありうる。
このうち、P[i]やmax(P[j]～P[N])の値によって、行わない遷移もある。

• i番目とj番目が撃たれて、(j+1,j+2)に遷移
• i番目だけが撃たれて、(j,j+1)に遷移
• j番目だけが撃たれて、(i,j+1)に遷移
• どちらも撃たれず(i,j)のまま

上記遷移をK回行ってありうる遷移のパターンを列挙すればよい。

int N,K;
int P[3002],MP[3002];
int mat[3001][3001];
int nu;


void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>K;
	FOR(i,N) cin>>P[i];
	for(i=N-1;i>=0;i--) MP[i]=max(MP[i+1],P[i]);
	
	nu=1;
	mat[0][1]=1;
	set<pair<int,int> > S,S2;
	S.insert(make_pair(0,1));
	FOR(i,K) {
		S2.clear();
		ITR(it,S) {
			int cur=it->first;
			int ne=it->second;
			
			if(cur>=N-1) continue;
			if(ne>=N) continue;
			if(P[cur]!=0 && MP[ne]!=0 ) {
				if(ne+1<N && mat[ne+1][ne+2]==0) {
					nu++;
					mat[ne+1][ne+2]=1;
					S2.insert(make_pair(ne+1,ne+2));
				}
				if(ne==N-1 && mat[0][0]==0) {
					nu++;
					mat[0][0]=1;
				}
			}
			if(P[cur]!=0 && MP[ne]!=100 ) {
				if(mat[cur][ne+1]==0) {
					nu++;
					mat[cur][ne+1]=1;
					S2.insert(make_pair(cur,ne+1));
				}
			}
			if(P[cur]!=100 && MP[ne]!=0 ) {
				if(mat[ne][ne+1]==0) {
					nu++;
					mat[ne][ne+1]=1;
					S2.insert(make_pair(ne,ne+1));
				}
			}
		}
		swap(S,S2);
	}
	
	_P("%d\n",nu);
}

まとめ

ちょっと変わった問題。
問題としては面白いけど、ストーリーは若干不自然。