HackerrankでのC++によるVertical Rooksの解法

問題の解法には様々なアプローチがありますが、以下にいくつかのシンプルで簡単な方法とコード例を示します。

1. グリーディ法の使用:

   • 各プレイヤーは1手ずつ交互にルークを選び、相手のルークを移動できなくなる位置に配置します。
   • 相手のルークが移動できなくなる位置は、縦方向の最小・最大値の組み合わせとなります。
   • このアプローチでは、各プレイヤーが最適な手を選ぶことが求められます。

   // C++コード例
   #include <iostream>
   using namespace std;
   int main() {
      int n;
      cin >> n;
      int maxVal = 0, minVal = 0;
      for (int i = 0; i < n; i++) {
          int a, b;
          cin >> a >> b;
          maxVal ^= max(a, b);
          minVal ^= min(a, b);
      }
      if (maxVal > minVal) {
          cout << "player-2" << endl;
      } else {
          cout << "player-1" << endl;
      }
      return 0;
   }

2. ダイナミックプログラミングの使用:

   • 2次元配列を使用して、各マスにおける相手のルークの状態を保持します。
   • 各プレイヤーは、自分の手番において相手のルークを動かすことで、相手のルークの状態を更新します。
   • 最終的に相手のルークが移動できなくなるかどうかを判定します。

   // C++コード例
   #include <iostream>
   using namespace std;
   int main() {
      int n;
      cin >> n;
      int grid[n][n];
      for (int i = 0; i < n; i++) {
          for (int j = 0; j < n; j++) {
              cin >> grid[i][j];
          }
      }
      bool dp[n][n];
      dp[0][0] = false;
      for (int i = 0; i < n; i++) {
          for (int j = 0; j < n; j++) {
              if (i == 0 && j == 0) continue;
              dp[i][j] = false;
              for (int k = 0; k < i; k++) {
                  dp[i][j] |= !dp[k][j];
              }
              for (int k = 0; k < j; k++) {
                  dp[i][j] |= !dp[i][k];
              }
          }
      }
      if (dp[n-1][n-1]) {
          cout << "player-1" << endl;
      } else {
          cout << "player-2" << endl;
      }
      return 0;
   }