【AtCoder】ABC 355 C - Bingo 2 | 茶コーダーが解くAtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 325

問題概要

縦 $N$ 行、横 $N$ 列のマス目があり、上から $i$ 行目、左から $j$ 列目のマスには整数 $N \times (i-1) + j$ が書かれている。今から $T$ ターンにわたって相異なる整数が宣言され、 $i$ ターン目には整数 $A_i$ が宣言される。宣言された整数が書かれているマス目に印をつけていくとき、初めてビンゴになるのは何ターン目か求めよ。ただし、 $T$ ターンの中でビンゴにならない場合は-1を出力せよ。

制約

入力はすべて整数。
$2 \leq N \leq 2 \times 10^3$
$1 \leq T \leq \min(N^2, 2 \times 10^5)$
$1 \leq A_i \leq N^2$

考察

まず、宣言された数字がマス目の何行何列目にあるのかを簡単に取得するために、マス目に書かれた整数をkey、対応する行数と列数のペアをvalueとしたデータ構造 (pos) を作成する。この部分は別にこんな大げさなことはしなくてもよく、計算によっても求められる。

次に、縦横 $N$ 列、斜め2方向に対して、現在印が何個付けられているかを管理するカウンター配列及び変数を作成する。

あとは各ターンごとに宣言された整数の行数と列数から対応するカウンターを更新していく。そしていずれかのカウンターが $N$ になったらビンゴ成立となる。

ちなみに、掲載しているコードは過去に学校の企画でほぼ同じケースを実装したときのものを流用している (探してくるのに時間がかかった) 。

コード

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

// ======================================== //

int main()
{
    ll N, T;
    cin >> N >> T;
    vector<ll> A(T);
    rep(i, 0, T) cin >> A[i];

    unordered_map<ll, Pair_ll> pos;
    rep(i, 0, N) rep(j, 0, N) pos[N * i + j + 1] = make_pair(i, j);

    vector<int> row_cnt(N), col_cnt(N);
    int diag1_cnt = 0;
    int diag2_cnt = 0;
    rep(t, 0, T)
    {
        int num = A[t];
        if (pos.find(num) != pos.end())
        {
            int i = pos[num].first;
            int j = pos[num].second;
            row_cnt[i]++;
            col_cnt[j]++;

            if (i == j)
                diag1_cnt++;
            if (i + j == N - 1)
                diag2_cnt++;

            if (row_cnt[i] == N || col_cnt[j] == N || diag1_cnt == N || diag2_cnt == N)
            {
                cout << t + 1 << endl;
                return 0;
            }
        }
    }

    cout << -1 << endl;
    return 0;
}

atcoder.jp

実装時間: 20分

Yuulis.log

トンネルを抜けるとそこは参照エラーであった。

【AtCoder】ABC 355 C - Bingo 2 | 茶コーダーが解くAtCoder

問題概要

制約

考察

コード