コンテスト名
東京海上日動プログラミングコンテスト2024(AtCoder Beginner Contest 355)
コンテストURL
開催日
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;
}