嘘貪欲は一瞬脳裏によぎり、それを振り払って問題を解いてた。発想はこれの「後ろから解く」のに似ている。

問題概要

$H$ × $W$ のグリッドのあるマスにロボットが置かれている。先手と後手はそれぞれ長さ $N$ の自分の文字列 $S, T$ を持っていて、交互に

$i$ 回目のターンでは自分の文字列の $i$ 文字目で指定された方向に一マス進む
その位置に待機する

を選ぶことができる。先手はロボットをグリッド外に落としたい。後手はロボットをグリッド内に残したい。双方最善を尽くしたとき、ロボットがグリッド内に残るなら Yes、残らないなら No を出力せよ。

制約

$1 \le H, W \le 2 × 10^{5}$

考えたこと

まず真っ先に思ったのが「縦方向と横方向は完全に独立に考えてよい」ということ。これはもう何万回も見た思考。なので、一直線上の問題として左右に動かし合う問題と考えて OK。

さて、そうすると

各プレイヤーは毎ターン「左に動かせる」「右に動かせる」「動かせない」のいずれか
左右のいずれかに動かせる場合でも、動かすかどうかを選べる

というゲームになる。

ゴールから逆算する

後手目線で考えることにする。ラストターンにおいて、先手が「L (左に動かせる)」だった場合には、 $N-1$ ターン目の後手終了時点で

区間 $\lbrack 1, W -1 \rbrack$

にロボットを存在させることが、勝てるための必要十分条件となる。ロボットがマス $0$ にいたら次に先手によって落とされてしまうけど、 $\lbrack 1, W -1 \rbrack$ にいたら先手が左に動かしたりしても大丈夫。

より一般に、

ターン目の先手が手を打った直後ににロボットが存在するようにするためには、その前段階で以下のことが条件となる
- S[i] == 'L' なら $\lbrack l+1, r \rbrack$ にロボットが存在すること
- S[i] == 'R' なら $\lbrack l, r-1 \rbrack$ にロボットが存在すること

ということが言える。さらに、

ターン目の後手が手を打った直後ににロボットが存在するようにするためには、その前段階で以下のことが条件となる
- T[i] == 'L' なら $\lbrack l, \min(r+1, W-1) \rbrack$ にロボットが存在すること
- T[i] == 'R' なら $\lbrack \max(0, l-1), r \rbrack$ にロボットが存在すること

ということも言える。これを利用すると、

スタート時点でロボットがどこに存在しなければならないか

を完全に逆算することができる。逆算の過程で

区間が潰れてしまう (その時点でロボットがどこにいても将来的に必ず先手に落とされる)
スタートの生存条件が、ロボットの初期位置を含まない

となったら No を出力する。

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int H, W, N;
int ix, iy;
string S, T;

bool solve() {
    // left, right
    int left = 0, right = W;
    if (S[N-1] == 'L') ++left;
    if (S[N-1] == 'R') --right;
    for (int i = N-2; i >= 0; --i) {
        if (T[i] == 'L') right = min(right+1, W);
        else if (T[i] == 'R') left = max(0, left-1);
        if (S[i] == 'L') left = left + 1;
        else if (S[i] == 'R') right = right - 1;
        if (left >= right) return false;
    }
    if (iy < left || iy >= right) return false; 

    // up, down
    left = 0, right = H;
    if (S[N-1] == 'U') ++left;
    if (S[N-1] == 'D') --right;
    for (int i = N-2; i >= 0; --i) {
        if (T[i] == 'U') right = min(right+1, H);
        else if (T[i] == 'D') left = max(0, left-1);
        if (S[i] == 'U') left = left + 1;
        else if (S[i] == 'D') right = right - 1; 
        if (left >= right) return false;
    }
    if (ix < left || ix >= right) return false;

    return true;
}

int main() {
    while (cin >> H >> W >> N >> ix >> iy >> S >> T) {
        --ix, --iy;
        if (solve()) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder AGC 033 B - LRUD Game (水色, 600 点)

問題概要

制約

考えたこと

ゴールから逆算する