細胞着色ゲームの勝者を見つけるためのC++プログラム

2つの配列AとBがあり、どちらもそれぞれN個の要素を持っているとします。 AmalとBimalが、セル番号が1からNまでのボードでゲームをプレイしていると考えてください。N-1道路。道路は2つのセルを接続しています。つまり、i番目の道路はA[i]とB[i]を接続しています。隣接するセルに繰り返し移動することにより、他のすべてのセルからすべてのセルに到達できます。最初、セル1は黒色でマークされ、セルNは白色でマークされています。他のセルは着色されていません。アマルが最初にプレイし、代わりにプレイします。 Amalは、黒いセルに隣接し、黒く塗られている色のないセルを選択します。 Bimalは、白いセルに隣接し、白く塗られている色のないセルを選択します。プレイヤーがセルをペイントできないとき、彼は緩みます。勝者を見つける必要があります。

したがって、入力がA =[3、1、3、7、5、1]のような場合; B =[6、2、1、4、7、4]の場合、出力はAmalになります。これは、Amalが最初にセル2を黒く塗った場合、Bimalの動きに関係なく勝つためです。

ステップ

これを解決するには、次の手順に従います-

N := 99999
Define one adjacency list adjList
Define three large arrays p, d, and ssz
Define a function dfs(), this will take nd, par, dep,
   p[nd] := par
   d[nd] := dep
   ssz[nd] := 1
   for each node i in adjList[nd], do
      if i XOR par is non-zero, then:
         dfs(i, nd, dep + 1)
         ssz[nd] := ssz[nd] + ssz[i]
From the main method, do the following:
n := size of A
for initialize i := 1, when i < n, update (increase i by 1), do:
   u := A[i - 1], v := B[i - 1]
   insert v at the end of adjList[u]
   insert u at the end of adjList[v]
dfs(1, 1, 0)
nd := n
for initialize i := 0, when i < (d[n] - 1) / 2, update (increase i by 1), do:
   nd := p[nd]
return if 2 * ssz[nd] >= n, then "Bimal", otherwise "Amal"

例

理解を深めるために、次の実装を見てみましょう-

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

int N = 99999;

vector<vector<int>> adjList(N);
vector<int> p(N), d(N), ssz(N);

void dfs(int nd, int par, int dep){
   p[nd] = par;
   d[nd] = dep;
   ssz[nd] = 1;
   for (int i : adjList[nd]){
      if (i ^ par){
         dfs(i, nd, dep + 1);
         ssz[nd] += ssz[i];
      }
   }
}
string solve(vector<int> A, vector<int> B){
   int n = A.size();
   for (int i = 1; i < n; i++){
      int u = A[i - 1], v = B[i - 1];
      adjList[u].push_back(v);
      adjList[v].push_back(u);
   }
   dfs(1, 1, 0);
   int nd = n;
   for (int i = 0; i < (d[n] - 1) / 2; i++)
      nd = p[nd];
   return (2 * ssz[nd] >= n ? "Bimal" : "Amal");
}
int main(){
   vector<int> A = { 3, 1, 3, 7, 5, 1 };
   vector<int> B = { 6, 2, 1, 4, 7, 4 };
   cout << solve(A, B) << endl;
}

入力

{ 3, 1, 3, 7, 5, 1 }, { 6, 2, 1, 4, 7, 4 }

出力

Amal