撒いたエラーすら読んじゃいない男の備忘録です
コンテスト概要
AtCoder Beginner Contest 391
開催日:2025年2月1日 21:00-22:40
A-Lucky Direction
考察
方角の反対側を出力する。南西の反対は北東であり、それぞれ「南」と「北」、「西」と「東」を入れ替えるだけでよい。
ここまで単純な考察になると考慮漏れがないか不安になる。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
map<char,char>mp;
//逆の方角の準備
mp['N'] = 'S',mp['S'] = 'N';
mp['E'] = 'W',mp['W'] = 'E';
string s;
cin >> s;
for(auto x:s) cout << mp[x];
cout << endl;
}
B - Seek Grid
考察
言われた通りにやるとしか言いようがない。aとbの範囲に気を付けながら全探査。
a,bの値が教えられていることに優しさを感じる。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin >> n >> m;
vector<vector<char>>s (n,vector<char>(n)),t (m,vector<char>(m));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++) cin >> s[i][j];
}
for(int i=0;i<m;i++){
for(int j=0;j<m;j++) cin >> t[i][j];
}
//左上の座標を全探査していく
for(int a=0;a<=n-m;a++){
for(int b=0;b<=n-m;b++){
bool che = true;
for(int i=0;i<m;i++){
for(int j=0;j<m;j++){
if(s[a+i][b+j] != t[i][j]) che = false;
}
}
if(che) cout << a+1 << " " << b+1 << endl;
}
}
}
C - Pigeonhole Query
考察
それぞれの鳩の現住所と巣にいる鳩の数を管理する配列を用意する。
クエリ１ごとに鳩Ｐの住所を書き換え、鳩の匹数も変える。この時書き換えるべき巣は前住所と現住所だけ。
複数匹いる巣の数を管理する変数を用意し、前住所が２匹から１匹になったらマイナス、現住所が１匹から２匹になったらプラスをする。
クエリ２のタイミングで変数を出力するだけでＯＫ。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,q;
cin >> n >> q;
//巣にいる鳩の数
vector<int>num (n,1);
//鳩の住所録
vector<int>pos (n);
for(int i=0;i<n;i++) pos[i] = i;
int ans = 0;
for(int i=0;i<q;i++){
int x;
cin >> x;
if(x == 1){
int x,y;
cin >> x >> y;
x--,y--;
//鳩を移動させる
num[pos[x]]--,num[y]++;
//古巣が単体になったら答えを減らす
if(num[pos[x]] == 1) ans--;
//新居が複数になったら答えを増やす
if(num[y] == 2) ans++;
pos[x] = y;
}else{
cout << ans << endl;
}
}
}
D - Gravity
考察
1秒ごとに進めるとyが10億の高さにあるとき当然TLEなのでうまく盤面を圧縮する必要がある。
ここでそれぞれのxの位置において一番手前にあるブロックが落ち切ったときにブロックが消える。（一列埋まる前提）
つまりは一列が消えるタイミングはそれぞれのｘで一番落ちてくるのが遅いブロックに依存する。その時間がわかれば高速にブロックが消えるタイミングがわかる。
タイミングを求めてしまえば時刻ＴはブロックＡが消えるより後か前かを答えるだけ。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
int n,w;
cin >> n >> w;
vector<vector<pair<int,int>>>num (w,vector<pair<int,int>>(0));
for(int i=0;i<n;i++){
int x,y;
cin >> x >> y;
x--;
//それぞれのx座標のブロックがどの位置にあるかを格納
num[x].push_back({y,i});
}
//最大で何列消えるかをチェック
//一番下まで消えずに残ったとして一番低いブロック以下はすべて消える。
int siz = (1<<30);
for(auto x:num){
sort(x.begin(),x.end());
int s = x.size();
siz = min(siz,s);
}
//いったん答えに大きな値を入れておく（無限=消えない）
int lim = (1<<30);
vector<int> ans (n,lim);
int now = 0;
for(int i=0;i<siz;i++){
for(int j=0;j<w;j++){
now = max(now,num[j][i].first);
}
for(int j=0;j<w;j++){
ans[num[j][i].second] = now;
}
now++;
}
int q;
cin >> q;
for(int i=0;i<q;i++){
int x,y;
cin >> x >> y;
y--;
//ブロックが消えるのはyより前か後か
if(x < ans[y]) cout << "Yes" << endl;
else cout << "No" << endl;
}
}
E - Hierarchical Majority Vote
考察
それぞれ3つの組について3つが同じなら2つ、2つだけ同じなら1つ変更させる必要がある。それを踏まえすべての数に現在の値と変更のためのコストを持たせる。
$3^N$個を$3^{N-1}$に減らすとき、3つが同じなら2つのコストの合計が小さいものを、2つが同じならそのうちコストの小さいものをメモしておく。
これを繰り返せばセグ木チックにコストを確認できる。
しかし結果はＷＡ。20分格闘しなんとなくエラーコードを見ると添え字ミスが発覚。
20分を嘆き1文字変更するだけでＡＣ。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
int n;
cin >> n;
queue<pair<int,int>> que;
int siz = pow(3,n);
for(int i=0;i<siz;i++){
char x;
cin >> x;
//最初変更のコストは当然１
que.push({x-'0',1});
}
//初期の配列が1つだけになるまで
while(que.size() != 1){
vector<pair<int,int>>num (3);
int sum = 0;
for(int i=0;i<3;i++){
num[i] = que.front();
sum += num[i].second;
que.pop();
}
pair<int,int>ans;
//3つ同じか、2つ同じかで場合分け
if(num[0].first == num[1].first && num[1].first == num[2].first){
ans.first = num[0].first;
//コストのうち小さいほう二つの合計が併合後のコスト
ans.second = sum - max({num[0].second,num[1].second,num[2].second});
}else{
if(num[0].first != num[1].first) ans.first = num[2].first;
else ans.first = num[0].first;
ans.second = (1<<30);
//2つある文字のうちコストが小さいものが併合後のコスト
for(int i=0;i<3;i++){
if(ans.first == num[i].first) ans.second = min(ans.second,num[i].second);
}
}
//併合した値をqueに
que.push(ans);
}
cout << que.front().second << endl;
}
F - K-th Largest Triplet
考察
ABC331_E問題の変数が1つ増えたような問題。なので何とか剽窃できないかと解説を見るが上手くいかずTIME UP。
もっと素直でよかったのか。
結果
ABCDE(2) 5完 95:14
順位 1731位
パフォーマンス 1278
感想
エラーコードはしっかり確認するべきだったそうすれば500位くらいは順位が上がっていた。
入水はまだ遠い。