kmjp's blog

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

KUPC2015 : B - GUARDIANS

手で解いた人と、プログラム回して解いた人どっちが多いんだろうな。
http://kupc2015.contest.atcoder.jp/tasks/kupc2015_b

問題

10x10のフィールドがある。
プレイヤーは左端のいずれかの行から開始し、右端のいずれかの行に移動したい。
その際、1回で右・右下・右上のいずれかのマスに移動可能である。

ここで、石を投げる敵キャラを最大5体まで置くことができる。
敵キャラは、縦横及び45度斜め方向に対し、射程1~2マスで攻撃できる。

プレイヤーは敵キャラ及び敵キャラの石が届く範囲を通らないように移動したい。
移動経路が1通りに定まるような敵の置き方を求めよ。

解法

ヒントで、敵は4体の解もあると書いてある。
そこで100^4通り全列挙し、その都度DPして到達経路の数を求めよう。

下記のコードを実行すると、以下の例が最初に出力される。

..........
..........
.........C
.CC.......
..........
..........
..........
C.........
..........
..........
int N;
int A[4],X[4],Y[4];
char S[11][11];
ll dp[10][10];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(A[3],100) FOR(A[2],A[3]) FOR(A[1],A[2]) FOR(A[0],A[1]) {
		
		FOR(y,10) FOR(x,10) S[y][x]='.';
		FOR(r,4) {
			FOR(y,10) FOR(x,10) {
				if(abs(A[r]/10-y)==abs(A[r]%10-x) && abs(A[r]/10-y)<=2) S[y][x]='X';
				if(abs(A[r]/10-y)<=2 && abs(A[r]%10-x)==0) S[y][x]='X';
				if(abs(A[r]/10-y)<=0 && abs(A[r]%10-x)<=2) S[y][x]='X';
			}
		}
		ZERO(dp);
		FOR(x,10) {
			FOR(y,10) if(S[y][x]=='.') {
				if(x==0) dp[y][x]=1;
				else {
					if(y) dp[y][x]+=dp[y-1][x-1];
					if(y<9) dp[y][x]+=dp[y+1][x-1];
					dp[y][x]+=dp[y][x-1];
				}
			}
		}
		ll ret=0;
		FOR(y,10) ret+=dp[y][9];
		if(ret==1) {
			FOR(y,10) FOR(x,10) S[y][x]='.';
			FOR(r,4) S[A[r]/10][A[r]%10]='C';
			FOR(y,10) cout<<S[y]<<endl;
			return;
		}
	}
	
}

まとめ

自力で考えても良いし、力技でも良いけど、どちらにしてもちょっと悩む問題。