【c++】ABC355 A-D問題解説【ACコード付き】

# AtCoder Beginner Contest 355
D問題まで4完。

B問題で1回、C問題で2回、D問題で1回WAを出してしまい、D問題まで解けた割にパフォーマンスもレートも爆上がりはしなかった。

それでもレートは442→506の64アップとなり、過去最高の上がり幅であった。1000パフォくらいを安定して取れるようにABC埋めこれからも精進します。

https://atcoder.jp/contests/abc355

## A - Who Ate the Cake?
1,2,3の番号がついた人がいる。
A,Bのそれぞれが犯人でない時に、犯人は誰か。特定できない時には`-1`を出力せよ、という問題。

もっといい方法がありそうだったが、条件分岐でごり押した。笑

```cpp
int main()
{
	int A, B;
	cin >> A >> B;
	if (A == B) cout << -1 << endl;
	else
	{
		if (A == 1 || B == 1)
		{
			if (A == 2 || B == 2) cout << 3 << endl;
			else cout << 2 << endl;
		}
		else cout << 1 << endl;
	}
	return 0;
}
```

## B - Piano 2
長さ$N$の数列$A$と長さ$M$の数列$B$が与えられる。それぞれの要素を全て昇順に並び替えた長さ$N+M$の数列$C$において、数列$A$の要素が連続して出現することはあるか。

`vector<pair<int, int>>`で配列$C$を定義し、どちらの配列から加えられた数なのかをsecondの要素として保持させた。そしてソートし、数列$A$の要素が連続するかどうかをひたすらチェックしていく。

```cpp
int N,M;
int A[109];
int B[109];
vector<pair<int, int>> c;

int main()
{
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
		c.push_back(make_pair(A[i], 1));
	}
	for (int i = 0; i < M; i++)
	{
		cin >> B[i];
		c.push_back(make_pair(B[i], 2));
	}
	
	sort(c.begin(), c.end());
	for (int i = 1; i < c.size(); i++)
	{
		if (c[i].second == 1 &&  c[i-1].second == 1)
		{
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
	return 0;
}
```

## C - Bingo 2
$N*N$のビンゴがある。$T$ターンに渡って異なる整数が宣言されるので、ビンゴを達成するのは何ターン目かを出力せよ。ビンゴが達成できない場合は`-1`を出力せよ、という問題。

最初は `bool board[2009][2009]`と二次元配列でビンゴの盤面の状態を管理し、毎回手が進むごとに盤面でビンゴが発生するかどうかを調べる、という途方もないアルゴリズムにしていた。

しかも全部の列、行、斜めに対して1マスずつ調べていくというトンデモ計算量。

間に合うはずもなく、行と列、斜めをそれぞれ別の配列で管理するというアルゴリズムに修正するとACとなった。

今回の問題では同じ数が出ないというのがミソである。（もしかしたら現実もそう？）

マスが重複することはないので、列、行それぞれで何マス穴が開けられたか？を記録しておくだけでOKだったのだ。

```cpp
int N, T;
int A[200009];
int row_count[2009], col_count[2009];
int diag1_count = 0, diag2_count = 0;

bool BINGO() {
    for (int i = 0; i < N; i++) {
        if (row_count[i] == N || col_count[i] == N) {
            return true;
        }
    }
    if (diag1_count == N || diag2_count == N) {
        return true;
    }
    return false;
}

int main() {
    cin >> N >> T;
    for (int i = 0; i < N; i++) {
        row_count[i] = 0;
        col_count[i] = 0;
    }

    for (int i = 0; i < T; i++) {
        cin >> A[i];
        int row = (A[i] - 1) / N;
        int col = (A[i] - 1) % N;

        row_count[row]++;
        col_count[col]++;
        if (row == col) {
            diag1_count++;
        }
        if (row + col == N - 1) {
            diag2_count++;
        }

        if (i >= N - 1) {
            if (BINGO()) {
                cout << i + 1 << endl;
                return 0;
            }
        }
    }

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

少し長いがTLEとなった最初のコードも載せておく。成仏してくれ。

```cpp
// 下のコードだとTLEになって間に合わなかった
int N, T;
int A[200009];
bool board[2009][2009];

bool BINGO()
{
    // 行のチェック
    for (int i = 0; i < N; i++)
    {
        bool row_bingo = true;
        for (int j = 0; j < N; j++)
        {
            if (!board[i][j])
            {
                row_bingo = false;
                break;
            }
        }
        if (row_bingo)
            return true;
    }

    // 列のチェック
    for (int j = 0; j < N; j++)
    {
        bool col_bingo = true;
        for (int i = 0; i < N; i++)
        {
            if (!board[i][j])
            {
                col_bingo = false;
                break;
            }
        }
        if (col_bingo)
            return true;
    }

    // 対角線のチェック（左上から右下）
    bool diag1_bingo = true;
    for (int i = 0; i < N; i++)
    {
        if (!board[i][i])
        {
            diag1_bingo = false;
            break;
        }
    }
    if (diag1_bingo)
        return true;

    // 対角線のチェック（右上から左下）
    bool diag2_bingo = true;
    for (int i = 0; i < N; i++)
    {
        if (!board[i][N - i - 1])
        {
            diag2_bingo = false;
            break;
        }
    }
    if (diag2_bingo)
        return true;

    return false;
}

int main()
{
    cin >> N >> T;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            board[i][j] = false;
        }
    }
    for (int i = 0; i < T; i++)
    {
        cin >> A[i];
        int row = (A[i] - 1) / N;
        int col = (A[i] - 1) % N;
        board[row][col] = true;

        if (i >= N - 1)
        {
            if (BINGO())
            {
                cout << i + 1 << endl;
                return 0;
            }
        }
    }
    cout << -1 << endl;
    return 0;
}
```

## D - Intersecting Intervals

$N$個の実数の区間$[l_{i},r_{i}]$が与えられる。共通区間を少しでも持つ、つまり被っている区間の組はいくつあるか。

今回の問題のミソは、区間の左端である$l_{i}$と右端である$r_{i}$は分離して考えて問題ないということだ。セットで情報が渡されるので直感的にはイメージしずらいと思うが、それぞれの区間の右端が入れ替わっても、最終的に求めたい共有区間を持つ区間の組みの数に変化はない。

そこで左端と右端をそれぞれ昇順に並びかえて、数字が小さい順に以下の処理を行っていく。

### 一番小さな数が左端(c)だった場合

左端ということはここから区間が加わるということだ。

今重なっている区間の数(tmp)分だけ、新しく加える区間との重複が生まれるので、tmpの数だけ答え(ans)に加えて、重なっている区間の数(tmp)を1足して、次の左端へ移動($c_{i}→c_{i+1}$)する。

### 一番小さな数が右端(c)だった場合

右端ということはここで区間が終わるということだ。

今重なっている区間の数(tmp)を1減らして、次の右端へ移動($d_{i}→d_{i+1}$)する。

```cpp
int N, l, r;
vector<int> c;
vector<int> d;

int main()
{
    cin >> N;
    c.reserve(N);
    d.reserve(N);
    for (int i = 0; i < N; i++)
    {
        cin >> l >> r;
        c.push_back(l);
        d.push_back(r);
    }
    sort(c.begin(), c.end());
    sort(d.begin(), d.end());

    long long ans = 0;
    int tmp = 0;
    int i = 0, j = 0;

    while (i < N && j < N)
    {
        if (c[i] > d[j])
        {
            tmp--;
            j++;
        }
        else
        {
            ans += tmp;
            tmp++;
            i++;
        }
    }

    cout << ans << endl;
    return 0;
}
```