Zepto Code Rush 2014 : B. Om Nom and Spiders

Aよりこちらの方が楽だった。
http://codeforces.com/contest/436/problem/B

問題

2次元のグリッドがある。
プレイヤーは最上段のいずれかのセルから、時間ごとに1マスずつジャンプして下のマスに移動する。
ここで、グリッド上には何体かの蜘蛛がおり、それぞれの移動方向が与えられている。
蜘蛛は各自の方向に時間ごとに1マス移動する。

プレイヤーが各列からスタートして最下段に移動する際、それぞれ何体の蜘蛛と遭遇するか。

解法

各蜘蛛が、プレイヤーが何列目からスタートした場合に遭遇するかカウントしていく。
(x,y)にいる蜘蛛の方向が：

• 下向きなら、プレイヤーは蜘蛛と遭遇しない。
• 上向きで、かつyが最上段から偶数段の位置にいるなら、x列目からスタートしたプレイヤーと遭遇する。奇数段なら遭遇しない。プレイヤーはジャンプで移動するので、すれ違いは遭遇とみなされない点に注意。
• 左または右向きなら、時間y後に(y-x)列または(y+x)列目でプレイヤーと遭遇する。

int N,M,K;
string S[2001];
int num[2001];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M>>K;
	FOR(y,N) cin>>S[y];
	for(y=1;y<N;y++) FOR(x,M) {
		if(S[y][x]=='U') if(y%2==0) num[x]++;
		if(S[y][x]=='R') {
			f=x+y;
			if(f<M) num[f]++;
		}
		if(S[y][x]=='L') {
			f=x-y;
			if(f>=0) num[f]++;
		}
	}
	
	FOR(x,M) _P("%d ",num[x]);
	_P("\n");
}

まとめ

上向きの蜘蛛の扱い以外は難しい点はないね。