🔵
【ABC385】AtCoder Beginner Contest 385【C++】
コンテスト名
ユニークビジョンプログラミングコンテスト2024 クリスマス(AtCoder Beginner Contest 385)
コンテストURL
開催日
2024/12/21 21:00-22:40
A: Equally
解法
- グループの分け方をすべて調べる
ABC385A.cpp
#include <iostream>
using namespace std;
int main(){
int a, b, c;
cin >> a >> b >> c;
if(a==b && b==c){
cout << "Yes" << endl;
return 0;
}
if(a+b==c || a+c==b || b+c==a){
cout << "Yes" << endl;
return 0;
}
cout << "No" << endl;
return 0;
}
B: Santa Claus 1
解法
- 問題文通りにシミュレーションする
- 通過または到着した家は
set<pair<int, int>>
に記録する
ABC385B.cpp
#include <iostream>
#include <vector>
#include <string>
#include <set>
using namespace std;
int main(){
int h, w, x, y;
cin >> h >> w >> x >> y;
x--;
y--;
vector<vector<char>> S(h, vector<char>(w));
for(int i=0; i<h; i++){
for(int j=0; j<w; j++){
cin >> S[i][j];
}
}
string t;
cin >> t;
set<pair<int, int>> st;
for(int i=0; i<t.size(); i++){
if(t[i]=='U'){
if(S[x-1][y]=='.'){
x--;
}else if(S[x-1][y]=='@'){
x--;
st.insert({x, y});
}
}else if(t[i]=='D'){
if(S[x+1][y]=='.'){
x++;
}else if(S[x+1][y]=='@'){
x++;
st.insert({x, y});
}
}else if(t[i]=='L'){
if(S[x][y-1]=='.'){
y--;
}else if(S[x][y-1]=='@'){
y--;
st.insert({x, y});
}
}else if(t[i]=='R'){
if(S[x][y+1]=='.'){
y++;
}else if(S[x][y+1]=='@'){
y++;
st.insert({x, y});
}
}
}
cout << x+1 << " " << y+1 << " " << st.size() << endl;
return 0;
}
C: Illuminate Buildings
解法
- 間隔、先頭について全探索する
- 間隔
のときについて、先頭がX のときから1 のときまで調べればよいX - 間隔
のときについての計算量はX \mathcal{O}(\frac{N}{X} \times X)
- 間隔
- 全体の計算量は
\mathcal{O}(N^2)
ABC385C.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
int n;
cin >> n;
vector<int> H(n);
for(int i=0; i<n; i++){
cin >> H[i];
}
int maxv = 1;
for(int i=1; i<=n; i++){
for(int j=0; j<i; j++){
int cnt = 1;
for(int k=j; k+i<n; k+=i){
if(H[k+i]==H[k]){
cnt++;
}else{
maxv = max(maxv, cnt);
cnt = 1;
}
}
maxv = max(maxv, cnt);
}
}
cout << maxv << endl;
return 0;
}
参考
D: Santa Claus 2
解法
- 二分探索
-
map<long long int, set<long long int>>
で家の位置を 軸方向とx 軸方向について管理するy - 通過または到着した家は削除する
ABC385D.cpp
#include <iostream>
#include <set>
#include <map>
using namespace std;
int main(){
long long int n, m, sx, sy;
cin >> n >> m >> sx >> sy;
map<long long int, set<long long int>> MX;
map<long long int, set<long long int>> MY;
int x, y;
for(int i=0; i<n; i++){
cin >> x >> y;
MX[x].insert(y);
MY[y].insert(x);
}
char d;
long long int c;
int cnt = 0;
for(int i=0; i<m; i++){
cin >> d >> c;
if(d=='U'){
auto it = MX[sx].lower_bound(sy);
while(it!=MX[sx].end() && *it<=sy+c){
MY[*it].erase(sx);
MX[sx].erase(it++);
cnt++;
}
sy += c;
}else if(d=='D'){
auto it = MX[sx].lower_bound(sy-c);
while(it!=MX[sx].end() && *it<=sy){
MY[*it].erase(sx);
MX[sx].erase(it++);
cnt++;
}
sy -= c;
}else if(d=='L'){
auto it = MY[sy].lower_bound(sx-c);
while(it!=MY[sy].end() && *it<=sx){
MX[*it].erase(sy);
MY[sy].erase(it++);
cnt++;
}
sx -= c;
}else if(d=='R'){
auto it = MY[sy].lower_bound(sx);
while(it!=MY[sy].end() && *it<=sx+c){
MX[*it].erase(sy);
MY[sy].erase(it++);
cnt++;
}
sx += c;
}
}
cout << sx << " " << sy << " " << cnt << endl;
return 0;
}
Discussion