スタックに積まれた文字をすべて空にできるか判定するC++プログラム

2n個の文字があるとします。それぞれの文字には1からnまでの整数が書かれており、同じ数字が書かれた文字は必ず2つずつ存在します。これらの文字はm個のスタックに分けて積まれており、i番目のスタックにはstack[i]の文字が格納されています。

私たちの課題は、以下のルールに従ってすべてのスタックを空にできるかどうかを判定することです。

• 任意の2つのスタックを選び、それぞれの一番上の文字を取り除きます。

• 取り除いた2つの文字には、同じ数字が書かれている必要があります。

この操作を繰り返してm個のスタックすべてを空にできればtrueを出力し、そうでなければfalseを返します。

問題の例

たとえば、入力が n = 3、m = 2、stacks = {{2, 1, 3}, {2, 1, 3}} の場合、出力は true になります。

2つのスタックがあり、それぞれに「2」「1」「3」という数字が書かれた文字が順に積まれています。両方のスタックから「3」同士、「1」同士、「2」同士とペアで取り除いていけば、指定されたルールどおりにすべてのスタックを空にできます。

解法のアプローチ

この問題はトポロジカルソート(カーンのアルゴリズム)を応用して解くことができます。考え方は次のとおりです。

• 各スタック内で隣り合う2つの文字に対して、「一方を取り除く前に、もう一方を先に取り除かなければならない」という依存関係を有向グラフとして記録します。

• 依存関係が残っていない文字(入次数が0の文字)から順にキューを使って処理していきます。

• 最終的にすべての文字の依存カウントが0になっていれば全スタックを空にできるためtrueを返します。依存関係に循環が含まれる場合、その文字は永遠に取り除けないためfalseとなります。

手順(擬似コード)

2次元配列 dp を定義する
配列 tvec を定義する
for i := 0 to m-1 do:
    k := stacks[i] のサイズ
    for j := 0 to k-1 do:
        if j > 0 then:
            p を dp[stacks[i][j]] の末尾に挿入する
            tvec[p] を 1 増やす
        p := stacks[i][j]
配列 tp を定義する
for i := 1 to n do:
    キュー q を定義する
    q に i を挿入する
    while q が空でない do:
        if tp[q の先頭要素] が偽 かつ tvec[q の先頭要素] が 0 と等しい then:
            dp[q の先頭要素] の各要素 next に対して:
                tvec[next] を 1 減らす
                next を q に挿入する
            tp[q の先頭要素] := true
        q から先頭要素を削除する
for i := 1 to n do:
    if tvec[i] が 0 と等しくない then:
        return false
return true

C++による実装例

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

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

bool solve(int n, int m, vector<vector<int>> stacks){
   vector<vector<int>> dp(n + 1);
   vector<int> tvec(n + 1);
   for(int i = 0; i < m; i++){
      int k = stacks[i].size();
      int p;
      for(int j = 0; j < k; j++){
         if(j > 0){
            dp[stacks[i][j]].push_back(p);
            tvec[p]++;
         }
         p = stacks[i][j];
      }
   }
   vector<bool> tp(n + 1);
   for(int i = 1; i <= n; i++){
      queue<int> q;
      q.push(i);
      while(!q.empty()){
         if(!tp[q.front()] && tvec[q.front()] == 0){
            for(auto next: dp[q.front()]){
               tvec[next]--;
               q.push(next);
            }
            tp[q.front()]=true;
         }
         q.pop();
      }
   }
   for(int i = 1; i <= n; i++){
      if(tvec[i] != 0){
         return false;
      }
   }
   return true;
}
int main() {
   int n = 3, m = 2;
   vector<vector<int>> stacks = {{2, 1, 3}, {2, 1, 3}};
   cout<< solve(n, m, stacks);
   return 0;
}

入力

3, 2, {{2, 1, 3}, {2, 1, 3}}

出力

1

コードの解説

まず、各スタックを走査しながら隣接する文字同士の依存関係を配列dpに記録し、依存されている側のカウントをtvecで管理します。次に、番号1からnまでの各文字を起点としてキューに入れ、依存カウントが0かつ未処理の文字を順番に確定させていきます。文字を確定するたびに、それに依存していた文字のカウントを減らし、新たに依存がなくなった文字をキューに追加します。最後にすべての文字のカウントが0になっていれば全スタックを空にできると判定されtrue(出力では1)が返されます。