Yuulis.log

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

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

atcoder.jp

実行時間制限: 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分

【AtCoder】ABC 355 B - Piano 2 | 茶コーダーが解くAtCoder

atcoder.jp

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

問題概要

長さ  N の数列  A と、長さ  M の数列  B が与えられる。  A, B の全ての要素を昇順に並べた長さ  N + M の数列  C において、  A の要素が2つ連続するかどうか判定せよ。ただし、  A, B の要素は全て異なるとする。

制約

  • 入力はすべて整数。
  •  1 \leq N, M \leq 100
  •  1 \leq A_i, B_j \leq 200

考察

 N, M の制約が小さいので、 C の各要素が  A にあるかどうかの判定には  A を全探索してしまって良いだろう。

連続しているかどうかには、フラグ用の変数を用いた。

コード

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

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

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

    vector<int> C;
    rep(i, 0, N) C.push_back(A[i]);
    rep(i, 0, M) C.push_back(B[i]);
    sort(all(C));

    int flag = -1;
    rep(i, 0, N + M)
    {
        if (find(all(A), C[i]) != A.end())
        {
            if (flag == 0)
            {
                cout << "Yes" << endl;
                return 0;
            }
            else
            {
                flag = 0;
            }
        }
        else if (find(all(B), C[i]) != B.end())
        {
            flag = 1;
        }
    }

    cout << "No" << endl;
    return 0;
}

atcoder.jp

実装時間: 5分

【AtCoder】ABC 355 A - Who Ate the Cake? | 茶コーダーが解くAtCoder

atcoder.jp

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

問題概要

あるケーキが食べられてしまい、犯人の候補として人  1, 2, 3 が挙げられている。犯人の目撃者は二人おり、それぞれ「人  A は犯人でない」、「人  B は犯人でない」という証言をしている。二人の証言から犯人を一人に特定できるかどうか判定し、特定できるならばその人の番号を出力せよ。そうでない場合は-1を出力せよ。

制約

  • 入力はすべて整数。
  •  1 \leq A, B \leq 3

考察

様々な実装方法が考えられるが、ここでは一番愚直な方法を書くことにする。

まず、  A = B の場合は犯人は一意に定まらないので-1を出力する。そうでないときは、  1, 2, 3 の中から  A でも  B でもないものを出力すればよい。

コード

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

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

int main()
{
    int A, B;
    cin >> A >> B;

    if (A == B)
        cout << -1 << endl;
    else if (A == 1 && B == 2)
        cout << 3 << endl;
    else if (A == 1 && B == 3)
        cout << 2 << endl;
    else if (A == 2 && B == 1)
        cout << 3 << endl;
    else if (A == 2 && B == 3)
        cout << 1 << endl;
    else if (A == 3 && B == 1)
        cout << 2 << endl;
    else if (A == 3 && B == 2)
        cout << 1 << endl;
}

atcoder.jp

実装時間: 5分以内

【AtCoder】東京海上日動プログラミングコンテスト2024(AtCoder Beginner Contest 355) - 参加記 | 茶コーダーが解くAtCoder

atcoder.jp

コンテスト時間: 2024-05-25(土) 21:00 ~ 2024-05-25(土) 22:40 (100分)

A - Who Ate the Cake?

Difficulty: ???
解答時間: 1:45

  • あるケーキを食べた犯人の候補として]人 [tex: 1, 2, 3 の3人が挙げられている。ここで、次の2つの証言から犯人が一人に特定できるかどうか判定する問題。
  • 証言 : 「人  A は犯人ではない。」「人  B は犯人ではない。」


  •  A = B のとき、犯人は一意に定まらない。それ以外のときは、人  1, 2, 3 の中から  A でも  B でもないものを出力すればよい。if文を使って地道に書いていこう。

B - Piano 2

Difficulty: ???
解答時間: 5:59

  • すべての要素が互いに相異なる長さ  N の数列  A と、長さ  M の数列  B が与えられる。  A, B の全ての要素を昇順に並べた数列  C において、  A の要素が連続して2個現れるか判定せよ。


  • 制約が割と小さいので、数列  C を作った後は各要素が  A に含まれるかどうかを全探索して判定していけばよい。

C - Bingo 2

Difficulty: ???
解答時間: 20:01

  • 縦横  N マスのビンゴ表があり、左上から右下に向かって1から順に数が書かれている。これから  T ターンにわたって相異なる整数が宣言されるので、宣言された数が書かれているマス目に印をつけていく。何ターン目にビンゴが成立するか求めよ。


  • 縦・横・斜め2方向において現在印がつけられているマスがいくつあるかを管理しておき、それらのいずれかが  N になればビンゴが成立したことになる。
  • 実は、私は以前学校の企画でほぼ同じコードを書いたことがあったので、それを流用した。

D - Intersecting Intervals

Difficulty: ???

  •  N 個の実数区間  [l_i, r_i]が与えられる。2つの区間が共通部分を持つような組  (i, j) の個数を求めよ。


  • 実数の範囲がとても大きいのでとりあえず座標圧縮する...ところまでは分かり、あとはいもす法で重なってるところを計算しよう、という方針だったが、なぜか RE が出現して撃沈。
  • 解説を見るに、セグメントツリーでやるとうまいこといけるらしい。

結果

Performance: 717
Rating: 583 → 597 (+14)

atcoder.jp

前回の分を取り返した。一進一退が続いている。

【AtCoder】ABC 335 B - Tetrahedral Number | 茶コーダーが解くAtCoder

atcoder.jp

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

問題概要

整数  N が与えられる。非負整数の組  (x, y, z) であって  x + y + z \leq N を満たすものを辞書順で小さい方から順に全て出力せよ。

制約

  •  0 \leq N \leq 21

考察

 N の制約が非常に小さいので、3重ループを用いて  (x, y, z) の組を全探索し、条件を満たすものを順に出力していこう。

コード

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

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

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

int main()
{
    int N;
    cin >> N;

    rep(x, 0, N + 1) rep(y, 0, N + 1) rep(z, 0, N + 1)
    {
        if (x + y + z <= N)
        {
            cout << x << " " << y << " " << z << endl;
        }
    }

atcoder.jp

実装時間: 5分以内