C++でDota2の勝利陣営を予測する方法（キューを活用したアルゴリズム解説）

Dota2の世界には、Radiant（ラディアント）とDire（ダイア）という2つの勢力が存在するとします。Dota2の上院は、この2つの勢力から選ばれた議員で構成されており、上院はゲーム内の変更について決議を行おうとしています。投票はラウンド制で進行し、各ラウンドで各議員は次の2つの権利のうちいずれか1つを行使できます。

• 他の議員の権利を禁止（Ban）する：ある議員は、別の議員の権利を今回および今後のすべてのラウンドで失わせることができます。

• 勝利を宣言する：まだ投票権を持っている議員がすべて同じ勢力に属している場合、その議員は勝利を宣言し、ゲーム内の変更に関する決定を下すことができます。

各議員の勢力所属を表す文字列が与えられます。文字「R」はRadiant党、「D」はDire党を表します。議員がn人いる場合、与えられる文字列の長さもnになります。

ラウンド制の手続きは、与えられた順序で最初の議員から最後の議員へと進みます。この手続きは投票が終了するまで続き、権利を失った議員は途中でスキップされます。

すべての議員は十分に賢く、自分の党にとって最善の戦略を取ると仮定して、最終的にどちらの党が勝利を宣言しゲーム内の変更を実現するかを予測してください。出力は「Radiant」または「Dire」のいずれかです。

例えば、入力が「RDD」の場合、結果は「Dire」となります。その理由は次のとおりです。1人目の議員はRadiant出身なので、第1ラウンドで2番目の議員の権利を禁止できます。すると2番目の議員は権利を失うため、以降何も行使できません。続いて3番目の議員はDire出身なので、第1ラウンドで1番目の議員の権利を禁止します。こうして第2ラウンドでは、3番目の議員だけが投票可能な議員となるため、彼は勝利を宣言できるのです。

解法のアプローチ

この問題は、2つのキューを使って効率的に解くことができます。手順は以下のとおりです。

• 2つのキューq1とq2を作成し、nを文字列のサイズとします。文字列中の「R」はすべてq1に、「D」はすべてq2にインデックス順で挿入します。
• 両方のキューが空でない間、以下を繰り返します。
  • q1の先頭要素がq2の先頭要素より小さい場合（Radiant側の議員が先に登場する場合）：nをq1に挿入し、q2とq1の先頭要素を削除します。これによりRadiant側の議員が相手を禁止して次ラウンドへ進みます。
  • そうでない場合：nをq2に挿入し、q2とq1の先頭要素を削除します。
  • nを1増やします。
• ループ終了後、q1が空なら「Dire」を返し、空でなければ「Radiant」を返します。

この手法では、各議員の位置を比較することで「誰が先に行動できるか」を判定でき、計算量はO(n)と非常に効率的です。

実装例（C++）

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string predictPartyVictory(string s) {
      queue <int> q1, q2;
      int n = s.size();
      for(int i = 0; i < s.size(); i++){
         if(s[i] == 'R'){
            q1.push(i);
         } else {
            q2.push(i);
         }
      }
      while(q1.size() && q2.size()){
         if(q1.front() < q2.front()){
            q1.push(n);
            q2.pop();
            q1.pop();
         } else {
            q2.push(n);
            q2.pop();
            q1.pop();
         }
         n++;
      }
      return q1.empty()? "Dire" : "Radiant";
   }
};
main(){
   Solution ob;
   cout <<(ob.predictPartyVictory("RDD"));
}

入力

"RDD"

出力

Dire