mini notes

競技プログラミングの解法メモを残していきます。

AGC033 B - LRUD Game(600)

AtCoderコンテスト ゲーム 後ろから考える

B - LRUD Game

概要

H行W列のマスにコマが1つおいてある。先手と後手はそれぞれ'L', 'R', 'U', 'D'からなる長さNの文字列をもっている。
先手と後手は交互に文字列の先頭から、文字が表す方向にコマを1マス動かすことができる。また動かさなくてもよい。
コマをマスの外に移動させると先手の勝ち、移動させられないと後手の勝ちとする。両者が最適に行動したとき、後手が勝てばYES、先手が勝てばNOと出力せよ。

制約

2 ≦ H, W ≦ 2 * 10^5
2 ≦ N ≦ 2 * 10^5

方針

縦の移動(U, D)と横の移動(L, R)は独立に考えてよい。

横の移動を考える。
文字列の先頭から考えると、先手・後手に出てくるL/Rを実行する/しないのO(2^N)となってしまう。貪欲に考えたいが、先頭からだとうまくいかない。
Twitterで論点となるサンプルを上げてくださった方がいました。
（おそらくジャッジで考慮されていない）

文字列の後ろから考えるのがよい。
考え方としては、
f(i) := 先手・後手ともに後ろからi番目までの文字列を実行した後、後手が勝てるコマの位置　とする。(fの出力は長方形の範囲を表す)
f(0) = [1, H] × [1, W]である。
後手の後ろから1番目の文字は特に影響を与えない。（この時点で後手を動かせても勝てるコマの位置は変わらない）
もし、先手の後ろから1番目の文字（最後の文字）がLであれば、その直前に1列目にコマがあると後手が負けるので、f(1) = [1, H] × [2, W]となる。
もし区間がつぶれた場合は、コマが勝てる位置がなくなったことを意味し、その時点で後手の負けが確定している。
例えばTwitterサンプルのケースだと、先手を後ろからたどりRRLとなるがこのときf = [*, *] ×[2, 1]となり、列を表す区間がつぶれており、この時点で後手負けが確定する。
（実際にコマが1・2・3列目のどこにあっても、先手が文字列LRRに従い、適切に動かす/動かさないを選択することにより、コマを落とすことが可能）

この範囲をf(N)まで算出し、初期配置がf(N)が示す範囲内に入っていれば、後手の勝ち。そうでなければ後手の負けとなる。

解答

Submission #5295705 - AtCoder Grand Contest 033

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int H, W, N;
string S, T;
 
struct bds{int lr, ur, lc, uc;};
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	cin >> H >> W >> N;
 
	int sr, sc;
	cin >> sr >> sc;
 
	cin >> S >> T;
	reverse(S.begin(), S.end());
	reverse(T.begin(), T.end());
 
	int lr = 1, ur = H;
	int lc = 1, uc = W;
 
	for(int i = 0; i < N; i++){
		if(T[i] == 'L'){
			uc = min(W, uc + 1);
		}else if(T[i] == 'R' ){
			lc = max(1, lc - 1);
		}else if(T[i] == 'U'){
			ur = min(H, ur + 1);
		}else{
			lr = max(1, lr - 1);
		}
 
		if(S[i] == 'L'){
			lc += 1;
		}else if(S[i] == 'R' ){
			uc -= 1;
		}else if(S[i] == 'U'){
			lr += 1;
		}else{
			ur -= 1;
		}
 
		if(uc < lc || ur < lr){
			cout << "NO" << endl;
			return 0;
		}
 
	}
 
	if(lr <= sr && sr <= ur && lc <= sc && sc <= uc){
		cout << "YES" << endl;
	}else{
		cout << "NO" << endl;
	}
}