C++で実装するランダムフリップ行列：効率的なアルゴリズムとコード解説

n_rows（行数）と n_cols（列数）からなる2値行列を考えてみましょう。すべての要素は初期状態で0になっています。ここで、0の値を一様にランダムに選択し、その値を1に変更して、該当する位置 [row.id, col.id] を返す関数 flip() を定義する必要があります。さらに、すべての値を0に戻す関数 reset() も実装しなければなりません。その際、システムの乱数生成関数（Math.random）の呼び出し回数を最小限に抑え、時間計算量と空間計算量を最適化することが求められます。

例えば、2×3の行列に対して flip() を4回呼び出した場合、結果は [0,1]、[1,2]、[1,0]、[1,1] のようになります。

解決のためのアプローチ

この問題は、フィッシャー–イェーツシャッフル（Fisher-Yates shuffle）の考え方を仮想的な1次元配列に適用することで、追加の行列データ構造なしに効率的に解けます。具体的には、以下の手順に従います。

• holes という名前のハッシュマップを作成します。
• コンストラクタでは以下を行います。
  • 乱数生成器を初期化し、n := 行数、m := 列数 を設定します。
  • size := n * m とします。
• flip メソッドでは以下を行います。
  • id := 乱数 mod size を求め、size を1減らします。また rid := id としておきます。
  • id が holes に存在する場合、id := holes[id] と置き換えます。
  • size が holes に存在すれば holes[rid] := holes[size]、存在しなければ holes[rid] := size とします。
  • (id / m, id % m) のペア（行番号と列番号）を返します。
• reset メソッドでは以下を行います。
  • size := n × m に戻し、holes マップをクリアします。

この方法なら、実際に行列全体を保持する必要がなく、flip ごとの処理は O(1) で完了するため、大規模な行列でも高速に動作します。

C++ 実装例

以下のコードで、実際の動作をより深く理解できます。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
    public:
    unordered_map <int, int> holes;
    int n;
    int m;
    int size;
    Solution(int n_rows, int n_cols) {
        srand(time(NULL));
        n = n_rows;
        m = n_cols;
        size = n * m;
    }
    vector<int> flip() {
        int id = rand() % size;
        size--;
        int rid = id;
        if(holes.count(id)){
            id = holes[id];
        }
        holes[rid] = holes.count(size) ? holes[size] : size;
        return {id / m, id % m};
    }
    void reset() {
        size = n * m;
        holes.clear();
    }
};
main(){
    Solution ob(2,2);
    print_vector(ob.flip());
    print_vector(ob.flip());
    print_vector(ob.flip());
    print_vector(ob.flip());
}

入力

コンストラクタを 2,2 で初期化し、flip() を4回呼び出す

出力

[1, 1]
[0, 0]
[1, 0]
[0, 1]

出力例のように、同じ位置が重複して選ばれることなく、すべてのセルがちょうど1回ずつ選択されることが確認できます。乱数の出力結果は実行ごとに異なるため、返される座標の順序は毎回変わりますが、重複のない一様な選択という性質は保証されます。