AGC034 A - Kenken Race (400)

A - Kenken Race

概要

横一列に並んだNマスがあり、マスAとマスBにはコマが置いてある。マスAのコマをマスCに、マスBのコマをマスDに移動できるかどうかを判定せよ。ただし、以下の条件がある。

• コマは右に1マスもしくは2マス移動できる
• 移動先のマスが壁'#'である場合、または移動先のマスにコマがある場合、そのマスには移動できない

制約

4 ≦ N ≦ 200 000
A < B, A < C, B < D

方針

2マス続いて壁もしくは壁とコマがある場合はそれより右のマスに移動することができない。
CとDの大小関係が制約にないため、Aが先にCに移動するパターンとBが先にDに移動するパターンを考えてあげるとよい。

Bが先にDに移動するパターンは、先にBをDに移動させた後、Bを壁と考えてAをCに移動させる。
Aが先にCに移動するパターンは、AがBを飛び越える必要があるため、AがBを飛び越えられるかどうかを確認した後、AをCに移動させ、BをDに移動させる。AがBを飛び越えられるかどうかは、BとCとの間に（Bが今いる場所を含め）3マス以上壁がないマスがあるかどうかで判断できる。

解答

Submission #5782482 - AtCoder Grand Contest 034

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int N, A, B, C, D;
string S;
vector<bool> iwa;
 
bool chk1(){
	for(int i = B; i < D; i++){
		if(iwa[i] && iwa[i+1]) {
			// cout << "chk1,B," << i << endl;
			return false;
		}
	}
 
	iwa[D] = true;
 
	for(int i = A; i < C; i++){
		if(iwa[i] && iwa[i+1]) {
			// cout << "chk1,A," << i << endl;
			iwa[D] = false;
			return false;
		}
	}
 
	return true;
}
 
bool chk2(){
	bool ok = false;
	int pos = -1;
	// for(int i = B; i <= min(C-2, D-1); i++){
	for(int i = B-1; i <= min(C-2, D-1); i++){
		if(!iwa[i] && !iwa[i+1] && !iwa[i+2]){
			// cout << "chk2,B," << i << endl;
			pos = i+1;
			iwa[pos] = true;
			ok = true;
		}
	}
 
	if(!ok) return false;
 
	for(int i = A; i < C; i++){
		if(iwa[i] && iwa[i+1]) {
			// cout << "chk2,A," << i << endl;
			iwa[pos] = false;
			return false;
		}
	}
 
	return true;
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	cin >> N >> A >> B >> C >> D;
	A--, B--, C--, D--;
 
	cin >> S;
 
	iwa.resize(N);
	rep(i, N) {
		if(S[i] == '#'){
			iwa[i] = true;
		} else{
			iwa[i] = false;
		}
	}
 
	// B -> A
	if(chk1()){
		cout << "Yes" << endl;
		return 0;
	}
 
	// A -> B
	if(chk2()){
		cout << "Yes" << endl;
		return 0;
	}
 
	cout << "No" << endl;
}