kmjp's blog

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

Codeforces #325 Div1 B. Phillip and Trains

750ptということもあってBの割に簡単。
http://codeforces.com/contest/585/problem/B

問題

縦3行、横W列のグリッドがある。
自分は左端の列のどこかにいる。
グリッド上いくつか電車があるマスがある。

時間1ごとに、自分と電車は交互に以下の順でように動く。

  • 自分が1マス右に移動する。
  • 次に、上下に最大1マス動いても良い。
  • 次に各電車は左に2マス動く。

右からやってくる電車にぶつからずやり過ごしながら、自分が右端に到達できるか判定せよ。

解法

電車が左に2マス動くと考えると面倒なので、自分が右に2マス動くと考えると、後は単純な探索。

int T;
int W,N;
string S[3];

void solve() {
	int i,j,k,l,r,x,y,z; string s;
	
	cin>>T;
	while(T--) {
		cin>>W>>N;
		FOR(i,3) cin>>S[i], S[i]+="................";
		W+=15;
		for(x=0;x+3<W;x+=3) {
			FOR(y,3) if(S[y][x]=='s') {
				if(S[y][x+1]!='.' && S[y][x+1]!='s' ) continue;
				for(z=max(0,y-1);z<=min(2,y+1);z++) if(S[z][x+1]=='.') S[z][x+1]='s';
			}
			FOR(y,3) if(S[y][x+1]=='s' && S[y][x+2]=='.') S[y][x+2]='s';
			FOR(y,3) if(S[y][x+2]=='s' && S[y][x+3]=='.') S[y][x+3]='s';
		}
		if(S[0][W-5]=='s' || S[1][W-5]=='s' || S[2][W-5]=='s') cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
}

まとめ

Div1Bにしては解法にヒネリが無さすぎる気がするが…。

広告を非表示にする