Kenken Race [AtCoder Grand Contest 034 A]

https://atcoder.jp/contests/agc034/tasks/agc034_a

解説

https://atcoder.jp/contests/agc034/submissions/5779249

自明な場合分けをまずはしておこう。
C＜Dであれば、追い越しが必要ない。
C＞Dであれば、追い越す必要がある。
追い越すためには、...のように何も置かれていない部分が3連続している必要がある。
そこで追い越すことができれば、あとは、1,2マス分のジャンプで到達できるかを見ればいい。
　
前提として、AからC, BからDが独立に到達可能であるかを判定する。
到達不可能なら不可能。
　
あとは、追い越しが必要であれば、追い越しできるか判定する。
自明なパターンを見る。
Bより後で...というところがあればここで追い越す。
あとは、Bの真後ろまでAがこれて、Bの次が空いているなら、追い越せる。
他にもB..でも追い越せる。
これらを丁寧に見ていくと判定できる。
　
isOk(a, b) := aからbに到達可能か
を作れば比較的わかりやすく判定可能。

int N, A, B, C, D;
string S;
//---------------------------------------------------------------------------------------------------
bool dp[201010];
bool isOk(int s, int t) {
	rep(i, s, t + 1) dp[i] = false;
	dp[s] = true;
	rep(i, s, t + 1) if (dp[i]) rep(d, 1, 3) if (S[i] == '.') dp[i + d] = true;
	return dp[t];
}
//---------------------------------------------------------------------------------------------------
#define yes "Yes"
#define no "No"
string solve() {
	if (!isOk(A, C)) return no;
	if (!isOk(B, D)) return no;

	if (C < D) return yes;


	rep(i, B - 1, D) if (S[i] == '.' and S[i + 1] == '.' and S[i + 2] == '.') return yes;
	return no;
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> A >> B >> C >> D >> S;
	A--; B--; C--; D--;
	cout << solve() << endl;
}