問題

アリスとボブが格子状のボードでゲームをする。

ボードは $h$ 行 $w$ 列のマスがあり、上から順に $1, \, 2, \, \cdots , \, h$ 行、左から順に $1, \, 2, \, \cdots , \, w$ 列とそれぞれ番号が付けられている。

はじめ、アリスの駒はマス $( {x}_{a}, \, {y}_{a} )$ に、ボブの駒はマス $( {x}_{b}, \, {y}_{b} )$ に位置しており、アリスから交互に駒を動かす。

ここで、アリスの駒がマス $({x}_{a}, \, {y}_{a})$ にあるとき、アリスは駒をマス $({x}_{a} + 1, \, {y}_{a}), \, ({x}_{a} + 1, \, {y}_{a} - 1), \, ({x}_{a} + 1, \, {y}_{a} + 1)$ のいずれかに動かすことができる。また、ボブの駒がマス $({x}_{b}, \, {y}_{b})$ にあるとき、ボブは駒をマス $({x}_{b} - 1, \, {y}_{b}), \, ({x}_{b} - 1 , \, {y}_{b} - 1), \, ({x}_{b} - 1, \, {y}_{b} + 1)$ のいずれかに動かすことができる。

一方のプレイヤーがもう一方のプレイヤーの駒と同じマスに位置したとき、その駒を動かしたプレイヤーが勝者となる。また、いずれかのプレイヤーが駒を動かせなくなったとき（すなわち、アリスが $h$ 行に到達するか、ボブが $1$ 行に到達するとき）、このゲームは引き分けとなる。

どちらのプレイヤーも最適な行動を行うとき、このゲームの結果はどうなるか判定せよ。

入力

まず最初の1行目に、テストケースの個数を表す整数 $t$ が与えられる。

その後、 $t$ 個のテストケースのそれぞれに対して、整数 $h, \, w, \, {x}_{a}, \, {y}_{a}, \, {x}_{b}, \, {y}_{b}$ が1行で順に与えられる。

条件

実行時間制限: 1s
メモリ制限: 256MB
$1 \leq t \leq {10}^{4}$
- すべてのテストケースにおける $h$ の値の合計は ${10}^{6}$ を超えない。
$1 \leq {y}_{a}, \, {y}_{b} \leq w \leq {10}^{9}$
$( {x}_{a}, \, {y}_{a} ) \ne ( {x}_{b}, \, {y}_{b} )$

出力

各テストケースに対し、アリスが勝つ場合は Alice を、ボブが勝つ場合は Bob を、引き分けの場合は Draw を出力すること。

解法

まず、 ${x}_{a} \geq {x}_{b}$ である場合には必ず引き分けとなります。これは、アリスは $x$ 座標が1ターンで必ず $1$ だけ大きくなっていくのに対して、ボブは $x$ 座標が1ターンで必ず $1$ だけ小さくなっていくため、2人の駒が同じ $x$ 座標に位置することはないためです。

従って、 ${x}_{a} \lt {x}_{b}$ の場合についてここから考えます。

まず、アリスとボブの駒が出会う可能性があるターン数について考えます。このゲームでは、1ターンで $x$ 座標の差が $1$ ずつ小さくなっていきます。

従って、初期状態では2人の駒の $x$ 座標の差が ${x}_{b} - {x}_{a}$ だけあるので、2人の駒が出会う可能性があるのは $({x}_{b} - {x}_{a})$ ターン目であるということが言えます。

このゲームではアリスが先攻となっていることから、奇数ターン目ではアリスの出番、偶数ターン目ではボブの出番ということになります。よって、 $({x}_{b} - {x}_{a})$ の値が奇数のときには「アリスが勝つ、もしくは引き分ける」という結果になり、偶数のときには「ボブが勝つ、もしくは引き分ける」という結果になるということが言えます。

ここで、まずは $({x}_{b} - {x}_{a})$ の値が奇数のとき、すなわちアリスが勝つ可能性があるときについて考えます。

まず、 ${y}_{a} = {y}_{b}$ のときについては、必ずアリスが勝ちます。これは2人とも $y$ 座標については $-1, \, 0, \, +1$ の移動しかできないため、

最初の1ターン目でアリスは $y$ 座標の値を変えずに移動する（マス $({x}_{a} + 1, \, {y}_{a})$ に移動する）
次のターン以降は、ボブが移動した方向にアリスも移動する

という手順によって、常に $y$ 座標を一致させたまま $x$ 座標の値の差を縮めることができるためです。

次に、 ${y}_{a} \lt {y}_{b}$ のときについて考えます。このとき、初期状態ではアリスはボブよりも左側にいるため、アリスは右側に移動していくことによって、ボブを追い詰めていくことができます。

一方で、ボブも追いつかれてはならないため、右側に移動し続けることによって、追いつかれるまでのターン数を多く稼ぐことができます。

以上から、互いに $x$ 座標が一致するまで右方向に移動し続け、 $w$ 列目に辿りついたら $y$ 座標を $w$ のままで移動し続ける、ということによって、アリスとボブが一致するか否かを判定することで、アリスが勝つかどうかの判定を行うことができます。

${y}_{a} \gt {y}_{b}$ のときについても同様で、初期状態でアリスはボブよりも右側にいるため、アリスは左側に移動していくことによって、ボブを追い詰めていくことができます。

こちらの場合も、アリスとボブの $x$ 座標が一致するまでそれぞれの $y$ 座標を $1$ ずつ減らしていくことによって、アリスとボブが一致するか否かを判定することができます。

以上のシミュレートは $O({x}_{b} - {x}_{a})$ で行うことができます。

次に、 $({x}_{b} - {x}_{a})$ が偶数のとき、すなわちボブが勝つ可能性がある場合について考えます。

まず、 ${y}_{a} = {y}_{b}$ のときには必ずボブが勝ちます。これは先程の場合と同様に、アリスが動いた方向にボブが動くことによって、必ず $y$ 座標を一致させながら $x$ 座標の差を縮めることができるためです。

次に、 ${y}_{a} \lt {y}_{b}$ のときについて考えます。このとき、アリスは先攻であり、初期状態ではアリスはボブよりも左側にいるため、アリスは左側に移動していくことによって、ボブから逃げていくことができます。

このようにアリスが逃げる際に、ボブも左側に移動していくことによってアリスを追い詰めることができるので、それぞれの $y$ 座標を $1$ ずつ減らしていくことによって、アリスとボブが一致するか否かを判定することができます。

${y}_{a} \gt {y}_{b}$ のときについても同様で、初期状態でアリスはボブよりも右側にいるため、アリスは右側に移動していくことによって、ボブから逃げていくことができます。

ボブも右側に移動していくことによってアリスを追い詰めることができるので、それぞれの $y$ 座標を $1$ ずつ増やしていくことによって、アリスとボブが一致するか否かを判定することができます。

以上のシミュレートは、アリスが勝つ可能性がある場合と同様に $O({x}_{b} - {x}_{a})$ で行うことができます。

よって、以上の方法によって、このゲームの決着がどのようになるかを判定することができます。

計算量については、 ${x}_{b} - {x}_{a} \lt h$ であることから、 $O(h)$ 程度で判定することができると言えます。ここで、すべてのテストケースに対して $h$ の値の合計は ${10}^{6}$ を超えないことが条件で保証されているため、これは実行時間制限に十分間に合うと言えます。

ソースコード

まず、アリスとボブがともに左側に移動したときに、2つの駒が一致するかどうかを判定する関数 left_same() を以下のように実装しました。

int h, w, xa, ya, xb, yb;

bool left_same(int xa, int ya, int xb, int yb) {
  // 移動は xb - xa 回発生するので、そのそれぞれで ya, yb の値を更新していく
  for (int i = 1; i <= xb - xa; i++) {
   // ya と yb が一致すれば、必ず最終的には駒は一致するので true を返す
    if (ya == yb) {
      return true;
    }

    if (i % 2 == 1) {
      // i が奇数のときはアリスの駒が動く
      ya = max(1, ya - 1); // 1 よりも小さい値にならないことを注意して更新する
    } else {
      // i が偶数のときはボブの駒が動く
      yb = max(1, yb - 1); // 1 よりも小さい値にならないことを注意して更新する
    }
  }

  return ya == yb; // ya と yb が等しいかどうかを返す
}

この left_same() と同様に、アリスとボブがともに右側に移動したときに、2つの駒が一致するかどうかを判定する関数 right_same() を以下のように実装しました。

int h, w, xa, ya, xb, yb;

bool right_same(int xa, int ya, int xb, int yb) {
  // 移動は xb - xa 回発生するので、そのそれぞれで ya, yb の値を更新していく
  for (int i = 1; i <= xb - xa; i++) {
   // ya と yb が一致すれば、必ず最終的には駒は一致するので true を返す
    if (ya == yb) {
      return true;
    }

    if (i % 2 == 1) {
      // i が奇数のときはアリスの駒が動く
      ya = min(w, ya + 1); // w よりも大きい値にならないことを注意して更新する
    } else {
      // i が偶数のときはボブの駒が動く
      yb = min(w, yb + 1); // w よりも大きい値にならないことを注意して更新する
    }
  }

  return ya == yb; // ya と yb が等しいかどうかを返す
}

以上の2つの判定する関数がある状態で、最終的な結果を出力する関数 solve() を以下のように実装しました。

int h, w, xa, ya, xb, yb;

void solve() {
  // 値の入力
  cin >> h >> w >> xa >> ya >> xb >> yb;

  // xa >= xb のときは絶対に一致しないので、Draw を出力して終了する
  if (xa >= xb) {
    cout << "Draw" << endl;
    return;
  }

  if (abs(xa - xb) % 2 != 0) {
    // アリスが勝つ可能性がある場合
    if (ya <= yb && right_same(xa, ya, xb, yb)) {
      // ともに右に動く場合
      cout << "Alice" << endl;
    } else if (yb <= ya && left_same(xa, ya, xb, yb)) {
      // ともに左に動く場合
      cout << "Alice" << endl;
    } else {
      cout << "Draw" << endl;
    }
  } else {
    // ボブが勝つ可能性がある場合
    if (ya <= yb && left_same(xa, ya, xb, yb)) {
      // ともに右に動く場合
      cout << "Bob" << endl;
    } else if (yb <= ya && right_same(xa, ya, xb, yb)) {
      // ともに左に動く場合
      cout << "Bob" << endl;
    } else {
      cout << "Draw" << endl;
    }
  }
  return;
}

提出したコード: https://codeforces.com/contest/1921/submission/244028140
GitHub

感想

$h$ の値の条件がなかったとしても、場合分けを細かく行なうことによって、このゲームの最終結果は求まるはずなので、「 $h$ の値の合計が ${10}^{6}$ を超えない」という条件でこの問題が簡単になったように思います。（ただ解いているだけの身としては、とてもありがたいです…。）

yutasの競技プログラミング勉強帖

競技プログラミングの問題についての解説記事を主に書いています。

E - Eat the Chip / Codeforces Round 920 (Div. 3)

問題

入力

条件

出力

解法

ソースコード

感想