【ABC355】AtCoder Beginner Contest 355【C++】

コンテスト名

東京海上日動プログラミングコンテスト2024（AtCoder Beginner Contest 355）

コンテストURL

https://atcoder.jp/contests/abc355

開催日

2024/05/25 21:00-22:40

---

A: Who Ate the Cake?

解法

• 人 $A$ と人 $B$ が同じ場合は犯人を特定できない
• $1 + 2 + 3 = 6$ から $A$ と $B$ を引くことで求められる

ABC355A.cpp

#include <iostream>
using namespace std;

int main(){
    int a, b;
    cin >> a >> b;

    if(a==b){
        cout << -1 << endl;
    }else{
        cout << 6 - a - b << endl;
    }

    return 0;
}

B: Piano 2

解法

• vector<pair<int, int>> で数列の要素とどちらの数列の要素かを記録する
• 昇順にソートして数列 $A$ の要素が連続しているかを判定する

ABC355B.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n, m;
    cin >> n >> m;

    vector<pair<int, int>> C;
    int a;
    for(int i=0; i<n; i++){
        cin >> a;
        C.emplace_back(a, 0);
    }
    int b;
    for(int i=0; i<m; i++){
        cin >> b;
        C.emplace_back(b, 1);
    }

    sort(C.begin(), C.end());
    for(int i=0; i<C.size()-1; i++){
        if(C[i].second==0 && C[i+1].second==0){
            cout << "Yes" << endl;
            return 0;
        }
    }

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

C: Bingo 2

解法

• 横、縦、対角線の各列について何マス印がついているかを記録する
• $i$ ターン目にビンゴになる可能性があるのは、 $A_i$ に関連する列だけ
  • $O(1)$ で更新・判定できる
• 計算量は長さ $N$ の配列の作成とターン数 $T$ で $O(N + T)$

ABC355C.cpp

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n, t;
    cin >> n >> t;

    vector<int> A(t);
    for(int i=0; i<t; i++){
        cin >> A[i];
        A[i]--;
    }

    vector<int> H(n), W(n);
    int naname1 = 0, naname2 = 0;
    for(int i=0; i<t; i++){
        int x = A[i] / n;
        int y = A[i] % n;

        H[x]++;
        W[y]++;
        if(x==y){
            naname1++;
        }
        if(x+y==n-1){
            naname2++;
        }

        if(H[x]==n || W[y]==n || naname1==n || naname2==n){
            cout << i+1 << endl;
            return 0;
        }
    }

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

D: Intersecting Intervals

解法

• 区間 vector<pair<int, int>> を昇順にソートして、 $l_j$ が $l_i$ より大きい区間のうち、 $l_j$ が $r_i$ より小さい区間 $j$ の個数をそれぞれ加算する
  • $i$ 番目の区間と共通部分をもつのは、左端が $l_i$ より大きくて $r_i$ より小さい区間である
• $l_j$ が $r_i$ より小さい区間 $j$ の個数は二分探索 upper_bound() で求める
  • 左端 $l$ を昇順にソートしたとき、 $r_i$ が何番目になるかを求める

ABC355D.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    int l, r;
    vector<pair<int, int>> V;
    vector<int> L;
    for(int i=0; i<n; i++){
        cin >> l >> r;
        V.emplace_back(l, r);
        L.push_back(l);
    }

    sort(V.begin(), V.end());
    sort(L.begin(), L.end());
    long long int sum = 0;
    for(int i=0; i<n; i++){
        auto [l, r] = V[i];
        sum += (upper_bound(L.begin(), L.end(), r) - L.begin()) - i - 1;
    }

    cout << sum << endl;
    return 0;
}