Bingo

以下のように、ビンゴの状態を愚直にシミュレーションを行うと、計算量が $O(QN^2)$ となり、この問題において正解することはできません。

愚直な実装 $O(QN^2)$

具体的には、ビンゴのカードの各マスが既に開いているかを $N \times N$ の二次元配列で表現し、読み上げの毎に更新、ビンゴしているかの判定を行うことを考えます。 ビンゴカードの初期化に $O(N^2)$ 、読み上げ毎に、ビンゴカードの更新に $O(N^2)$ 、ビンゴしているかの判定に $O(N^2)$ かかるため、問題全体の計算量は $O(QN^2)$ となります。

以下は Python の実装例です。

正解できる解法 1 $O(N^2 + QN)$

実装を工夫することで、計算量を $O(N^2 + QN)$ まで落とすことができ、正解することができます。 具体的には、以下のような処理を行うことで正解できます。

1. マスに書かれた数を key、そのマスの座標を value としての連想配列を作ります。計算量は $O(N^2)$ です。
2. ビンゴのカードの各マスが既に開いているかを $N \times N$ の二次元配列で表現し、読み上げの毎に更新します。計算量は $O(1)$ です。
3. ビンゴの達成の有無の判定を行う際には、直前に読み上げられた数字が書かれたマスを含む列のみをチェックします。計算量は $O(N)$ です。

上の愚直な実装では、読み上げられた数字が書かれたマスを求めること、ビンゴ達成の有無の判定それぞれに $O(N^2)$ 、かかっていましたが、今回の実装では、それぞれ $O(1)$ 、 $O(N)$ まで落とすことができています。 これにより、問題全体の計算量は $O(N^2 + QN)$ となり十分に高速です。

以下は Python の実装例です。

正解できる解法 2 $O(N^2 + Q)$

以下のような処理を行うことで、上の解法よりも更に高速に解くこともできます。

1. マスに書かれた数を key、そのマスの座標を value としての連想配列を作ります。計算量は $O(N^2)$ です。
2. 各行、各列、左上から右下の斜め、左下から右上の斜めそれぞれにおいて、開いたマスの数を管理し、読み上げのたびに逐次更新します。計算量は $O(1)$ です。
3. 各行、各列、左上から右下の斜め、左下から右上の斜めいずれかの開いたマスの数が $N$ になることは、ビンゴを達成することと等しいです。よって、それらの値が $N$ になったかを確認することで、ビンゴの達成の有無を確認します。計算量は $O(1)$ です。

問題全体の計算量は $O(N^2 + Q)$ になります。

以下は Python の実装例です。

※ 連想配列に、C++の std:unordered_map 、Pythonの dict のようなデータ構造を用いた場合の計算量を記載しています。