LRUD Game #C++

LRUD Game

コンテスト中の考察（ACしたけど嘘解法）

縦と横は独立に考えられる。
一番最初に思いつくのは、高橋くんがある方向にできるだけ進んで番外に駒を出そうとするという方針。それを上下左右について調べれば良さげ。貪欲法の嘘を見つけるには反例を挙げるといいんだけど、パッと思いつくものがない。なのでこの方針で実装してみる。
実装したが、サンプルと合わない（原因は[0, H], [0, W]の区間で座標を扱っていたことだった。いつも区間は[0, H)で扱うが今回は[1, H]で扱ったため、混乱してしまった）
とりあえず貪欲がサンプルと合わないので全探索を書いてみる（全探索のコード）。コードはミニマックス法みたいに書ける。全探索は明らかにTLEになる。制約が大きすぎてメモ化もできない(MLEとTLEで死ぬ）。うーん、どうしようか。
やはり最初に考えた貪欲しかなくね？ってなる。実装したら、次はバグらせずに実装できた。提出したらACした（ACしたコード(嘘解法)）。でもこれは嘘解法。嘘ついちゃった…えーん...

貪欲法の反例

貪欲法は以下のケースで落ちる。

2 2 3
1 1
RDU
DRR

本当の答えはNOだが、貪欲法だとYESとなってしまう。
反例、自分で思いつけない…（この反例も僕が思いついたやつじゃない…）
常に証明を考えたり、相手のコードをhackする気持ちになると反例が思いつくらしいんだが、僕はできない。多分慣れの問題だと思う。

反省

どうすればよかったか？

逆操作を考えると良かった。逆操作を考えると、ある時点で駒がどこにあれば青木くんが勝てるのかがわかる。
例えばN=3で横の場合のみを考えてみる。考えるべき情報は、その手番で駒があれば青木くんが勝てる範囲である。全ての操作が終わった状態では、駒が[1, W]の範囲にあれば勝てる。3手目では、3手目を打った時に駒が[1, W]からはみ出さない範囲[left1, right1]であれば勝てる。2手目では、2手目を打った時に駒が[left1, right1]からはみ出さない範囲[left2, right2]であれば勝てる。1手目では、1手目を打った時に駒が[left2, right2]からはみ出さない範囲[left3, right3]であれば勝てる。なので、初期位置が[left3, right3]の中に入っていれば青木くんの勝ちとなる。
言葉で説明するの難しすぎるな。説明がぐちゃぐちゃになってしまった。
とにかく青木くんが勝てる範囲は最終盤面で確定している。なので、そこから逆算して初期位置がどこにあれば青木くんが勝てるのかを求めることができる。
全体的な雰囲気の考察はだいたいこんな感じ。
もうちょっと詰めないとこの問題は解けない。まず、高橋くんと青木くんの操作を合わせて1回とカウントすると頭が壊れる。高橋くんの青木くんの操作は別々に考えるべき。
あとは、それぞれがどの操作をしたらどうなるかを考える。パターンは「高橋がR」「高橋がL」「青木がR」「青木がL」の4パターンある。サンプル１で試すとかでもいいかもだけど、僕は頭が壊れて無理だった。RRRRとかLLLLみたいな極端なケースを考えて、それぞれがそうするとどうなるかを見ると良かった。それをすると、「高橋がR→右--」「高橋がL→左++」「青木がR→左--」「青木がL→右++」だとわかる。ただし、青木くんははみ出さないように注意する必要がある
おしまい！

コード

#include <bits/stdc++.h>
using namespace std;

int H, W, N;
int sy, sx;
string s, t;

// solve(+へ向かう座標の文字, -へ向かう座標の文字, 座標の最大値, スタート座標)
bool solve(char cRight, char cLeft, int Max, int start) {
  int left = 1, right = Max;
  // 高橋の一番最後の手（青木の最後の手は無視して良い）
  if (s[N-1] == cRight) right--;
  if (s[N-1] == cLeft) left++;

  for (int i = N-2; i >= 0; i--) {
    // 青木
    if (t[i] == cRight) {
      left = max(1, left - 1);
    }
    if (t[i] == cLeft) {
      right = min(Max, right + 1);
    }

    // 高橋
    if (s[i] == cRight) {
      right--;
    }
    if (s[i] == cLeft) {
      left++;
    }

    // 青木が移動できる範囲がなくなったら終了
    if (left > right) return false;
  }

  // スタートが[left, right]の範囲内にあれば青木の勝ち
  return left <= start and start <= right;
}

int main() {
  cin >> H >> W >> N;
  cin >> sy >> sx;
  cin >> s >> t;

  bool a1 = solve('R', 'L', W, sx); // 横方向
  bool a2 = solve('D', 'U', H, sy); // 縦方向
  bool ans = a1 and a2;

  puts(ans ? "YES" : "NO");

  return 0;
}

要点

順番に操作するのを考えるは難しい。なぜなら、操作方法は無数にあるためその時点ではどの行動が最善かがわかりづらいから。
でも、逆操作は違う。最終盤面がどうなっていれば嬉しいかは確定しているため、そこから1つずつ逆操作していけば初期盤面がどうなっていれば嬉しいかがわかる。
逆操作を考えるときは、最終盤面で確定している情報を考えると良さそう。確定している状態を逆操作によって前の状態に持ち越せるから。
- 今回の場合、最終盤面で確定している情報は「青木くんが盤面のどこかにいれば青木くんが勝ち」という情報。他にもありそうだけど思いつかん。
本質じゃないけど、2操作1ターンで考えるのは無理だった。これだと、一気に2操作を考えないといけないから頭が爆発する。ターンを気にせず1操作ずつ考えるべきだった。
ある操作で何が起こるかを知りたいとき、極端なケースを作るとわかりやすかった。
- 今回の場合、高橋がR操作する時にはRRRRみたいなケースを作れば何が起こるかがわかりやすかった。

メモ

アルメリアさんの記事。図が良い。
drkenさんの記事。類題、考えたことが書いてある。
Harlequin。最終盤面から考えるって部分が類題。Alice&Brownも同様。
Snuke the Wizard。けんちょんさんが類題って言ってたやつ。まだ解いてないのでどの辺が類題かは知らん。
逆操作の発想、Nimでも使うらしいがNimを知らない（いつも先延ばしにしてる）