kmjp's blog

競技プログラミング参加記です

TopCoderOpen 2018 Wildcard Round Medium Gangsters

これは手間取ったけど解けて良かった。
http://community.topcoder.com/stat?c=problem_statement&pm=15008

問題

N人の人が円形に並んでいる。
i番の人は自身の銃を(i+1)%N番に向けている。

N人の人が順に銃を撃つことを考える。
銃を向けた先の人が生きていればその人は死亡する。
ただし撃つ順番の人が先に死んでいた場合、その人が銃を撃てない。

銃の撃ち方はN!通りあるが、そのうち最終的にA人生き残る順番は何通りか。

解法

初手、1番の人が撃ったとする。
すると2番の人は死亡し、3番の人は死ぬことはない。

下記DPを考える。解はN*(N-1)*dp(N-2,A)となる。最初のNは誰が最初に撃つか、2番目の(N-1)は、(実質何も起きないが)2番目の人が撃つ順番は残り(N-1)人のうちどこに来るかを示している。
dp(N,A) := N人の人が並んでいて、その後に順番完了済みの人が1人いる場合、A人残っている撃ち方の組み合わせ

dp(N,A)は次にN人中誰が撃つかを考えていけばよく、全体でO(N^3)で済む。

ll mo=1000000007;
ll memo[160][160];

const int CN=401;
ll C[CN][CN];


class Gangsters {
	public:
	ll dfs(int P,int A) {
		if(A<1) return 0;
		if(A>P+1) return 0;
		if(P<=1) return A==1;
		if(memo[P][A]>=0) return memo[P][A];
		ll ret=0;
		
		for(int i=1;i<=P;i++) {
			if(i==1) {
				ret+=(P-1)*dfs(P-2,A-1)%mo;
			}
			else if(i==P) {
				ret+=dfs(P-1,A);
			}
			else {
				int x,y;
				ll tmp=0;
				for(x=0;x<=A;x++) {
					y=A-x;
					tmp+=dfs(i-1,x)*dfs(P-(i+1),y)%mo;
				}
				ret+=(P-1)*(tmp%mo)%mo*C[P-2][i-1]%mo;
			}
		}
		
		return memo[P][A]=ret%mo;
	}
	
	int countOrderings(int people, int alive) {
		MINUS(memo);
		int i,j;
		FOR(i,CN) for(j=0;j<=i;j++) C[i][j]=(j==0||j==i)?1:(C[i-1][j-1]+C[i-1][j])%mo;
		
		return people*(people-1)*dfs(people-2,alive)%mo;
	}
}

まとめ

方針はすぐ立ったけど、実装を詰めるのにだいぶ手間取った。