AGC033 B問題：LRUD Game

問題. LRUD Game

縦 行，横 列の長方形上のマス目の に駒が置かれている．高橋君と青木くんはそれぞれ長さ の文字列 を持っている．高橋君から交互に駒を動かさないか，または，文字列にしたがって動かすかを決める．高橋君が ターン目に動かすことのできる方向は に書かれている文字で上下左右のいずれかである．同様に青木君の動かすことのできる方向は である．
ステップ以内で駒が盤外に移動したら高橋君の勝ち， ステップ後に駒が盤内にあれば青木君の勝ちとして，両者が最適な行動を行ったときにどちらが勝つかを判定せよ．

制約：

解法

次の嘘解法で通したので反省（嘘解法についての参考：嘘解法のススメ - てきとーな日記）．

高橋君が勝つことができるならば上下左右いずれかの方向で駒を盤外に移動可能なので，各場合で高橋君はその方向に移動できるなら移動して，青木くんは反対方向に移動できるなら移動するという貪欲戦略によって行動する．これによって の線形時間でどちらが勝つかを判定できる．

反例は のときで，答えは青木君の勝ちなのだが，上の判定方法だと高橋君の勝ちとなる．

解法は動画の解説を参考にした．
AtCoder Grand Contest 033 解説放送 - YouTube

任意の戦略の中から最適戦略を見つけるのは大変なので，任意の戦略を考えた結果どちらが勝つかを判定するということを考える．dp[k][i][j] を ターン目に に駒がある場合に青木君が勝つことができるかどうかという bool 配列を用意して動的計画法を行う．ただし，このまま実装を行うと 時間かかるので高速化が必要である． ターン目では盤内に駒があれば青木君の勝ちなので任意の に対して dp[N + 1][i][j] が true となる．また，マス目の形状は長方形なのでこの true からなる範囲も長方形である．青木君の ターン目を考えると，dp[k + 1][-][-] の true となる領域と， の方向に移動したときに true となる領域が dp[k][-][-] での true となる領域である．これは， ステップ目の長方形の領域を の反対方向に伸ばすことと等しい．反対に，高橋君は true となる長方形の領域を縮めることとなる．したがって，配列を陽に持つのではなく長方形の領域を持つことによって定数時間で更新することができる．

計算時間：

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

bool Solve() {
    int H, W, N;
    cin >> H >> W >> N;

    using P = pair<int, int>; // 行，列
    P s;
    cin >> s.first >> s.second;

    string S, T;
    cin >> S >> T;

    P h(1, W), v(1, H);
    for (int i = N - 1; 0 <= i; --i) {
        if (T[i] == 'U') v.second = min(H, v.second + 1);
        else if (T[i] == 'D') v.first = max(1, v.first - 1);
        else if (T[i] == 'L') h.second = min(W, h.second + 1);
        else if (T[i] == 'R') h.first = max(1, h.first - 1);

        if (S[i] == 'U') ++v.first;
        else if (S[i] == 'D') --v.second;
        else if (S[i] == 'L') ++h.first;
        else if (S[i] == 'R') --h.second;

        if (h.second < h.first || v.second < v.first) return false;
    }

    bool can_stay = (v.first <= s.first && s.first <= v.second)
        && (h.first <= s.second && s.second <= h.second);

    return can_stay;
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    // cout << setprecision(8) << setiosflags(ios::fixed);

    if (Solve()) cout << "YES" << endl;
    else cout << "NO" << endl;

    return 0;
}

反省会だった．二人零和有限確定完全情報ゲームで貪欲戦略が最適戦略となる場合があるので，証明も反例も考えずに脊髄反射的にプログラムを書いて通ってヤッターとなっていた．解説動画を見るとrngさんの「そういうことを考えるんですか・・・直感的に正しそうなものとかなら想定するんですけど・・・」が心に突き刺さって．