ビンゴを題材とした問題。行・列・斜めを合わせて $2N+2$ 個のラインがあるので、各ラインの空きマス数を管理しよう。

問題へのリンク

問題概要

$N \times N$ のグリッドがあり、上から $i$ 行目、左から $j$ 列目のマスには整数 $N \times (i−1)+j$ が書かれている。

今から $T$ ターンの穴あけをする。 $t$ ターン目には整数 $A_{t}$ が宣言される。その整数の穴を開ける。

ビンゴが成立する瞬間のターン数を答えよ。最後までビンゴしない場合は -1 を出力せよ。

制約

$2 \le N \le 2000$

考えたこと

ターンが終了するごとに、ビンゴが成立するかどうかを調べたい。次の $2N+2$ 個の集合を管理しておくと楽だと思われる。

各行について、すでに宣言された整数の集合
各列について、すでに宣言された整数の集合
左上から右下の対角線について、すでに宣言された整数の集合
右上から左下の対角線について、すでに宣言された整数の集合

整数 $A$ が宣言されたとき、その整数のあるマス $(x, y)$ を求めてあげて、

行 $x$ についての上記集合に整数値 $A$ を挿入する
列 $y$ についての上記集合に整数値 $A$ を挿入する
$x = y$ のとき、左上から右下の対角線についての上記集合に整数値 $A$ を挿入する
$x + y = N - 1$ のとき、右上から左下の対角線についての上記集合に整数値 $A$ を挿入する

としよう。そして、もしその挿入操作によって、集合のサイズが $N$ になったならば、そのときのターン数を答えればよい。

コード

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int,int>;

int main() {
    int N, T;
    cin >> N >> T;
    
    // 各行・各列・斜め方向の、穴の空いた集合を管理する
    vector<set<int>> lines(N * 2 + 2);
    
    // 値 val の穴を開ける
    // さらに、値 val を含むライン id について、ビンゴが達成したかどうかを返す
    auto play = [&](int id, int val, int turn) {
        lines[id].insert(val);
        if (lines[id].size() >= N) {
            cout << turn << endl;
            exit(0);
        }
    };
    
    // T ターン
    for (int turn = 1; turn <= T; ++turn) {
        int A; cin >> A; --A;
        int x = A / N, y = A % N;
        
        // 行 x を見る
        play(x, A, turn);
        
        // 列 y を見る
        play(y + N, A, turn);
        
        // 左上から右下への対角線を見る
        if (x == y) play(N * 2, A, turn);
        
        // 左上から右下への対角線を見る
        if (x + y == N - 1) play(N * 2 + 1, A, turn);
    }
    cout << -1 << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 355 C - Bingo 2 (3Q, 灰色, 300 点)

問題概要

制約

考えたこと

コード