5完はしたはずの男の備忘録です
コンテスト概要
ユニークビジョンプログラミングコンテスト2025 春（AtCoder Beginner Contest 398）
開催日:2025年3月23日 21:00-22:40
A - Doors in the Center
考察
久々に面倒なA問題が来たという印象。
'='の場所について小難しく書いているが、要するに回文の真ん中が'＝'と言ってるだけ。
とりあえず文字列を'-'で初期化して、奇数偶数に気を付けて真ん中を'='にすればOK。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
vector<char> s(n,'-');
if(n%2 == 0) s[n/2] = s[n/2 - 1] = '=';//偶数なら真ん中2つを変える。
else s[n/2] = '=';//奇数ならド真ん中1つを変える。
for(auto x:s) cout << x;
cout << endl;
}
B - Full House 3
考察
Aに続きちょっと面倒なB問題。
3枚になりうるカードと2枚になりうるカードが別々に存在しうるかという問題。
とりあえずカードの種類ごとの枚数を数えて
・3枚以上のカードが2組以上あるか？
・3枚のカードが1組、2枚のカードが1組以上あるか？
のどちらかが当てはまればOK
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
vector<int>num (14);
for(int i=0;i<7;i++){
int x;
cin >> x;
num[x]++;
}
int c2 = 0,c3 = 0;
//2枚の組と3枚以上の組を数える
for(auto x:num){
if(x == 2) c2++;
if(x >= 3) c3++;
}
if(c3 >= 2) cout << "Yes" << endl;//3枚のカードが2組以上ならOK
else if(c3 == 1 && c2 >= 1) cout << "Yes" << endl;//3枚のカードが1組、2枚のカードが1組以上ならOK
else cout << "No" << endl;
}
C - Uniqueness
考察
今日の問題、ずっとちょっと面倒だな。
まず、重複なしのカードが何かを知りたい。その後最大のカードを持っている人が知りたい。
なのでmapを使いすでに出た数かと、その数字を持ってる人は誰かを管理。その後最大の値と調べそれを持っている人を出力。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
map<int,int>mp; //出てきた回数を管理
map<int,int>num;//その数字を持っている人を管理
set<int>st;//重複のない数字を管理
for(int i=0;i<n;i++){
int x;
cin >> x;
mp[x]++;
num[x] = i+1;
if(mp[x] == 1) st.insert(x);//初めての数字ならsetに入れる
if(mp[x] == 2) st.erase(x);//かぶったらsetから出す。
}
if(st.empty()) cout << "-1" << endl; //setが空=解なし
else cout << num[*st.rbegin()] << endl;//最も大きい数字を持った人を出力
}
D - Bonfire
考察
煙がわりと動くのでいちいち追尾するのが大変。
なら逆に煙を固定して人と火を動かしたほうが効率がよさそう。
煙は最大$2\times10^5$マス動かす必要があるが逆なら人と火の2マスで済む。
問題では煙が風に流されるが、コードは人と火が風に逆らう形で進める。
そうすれば、一度でも火が通太場所に煙があり、そこを人が通れば煙がかぶることになる。
まず人と火を風に逆らう向きに進める。そして火の位置をメモする。人がこれまでに火があった場所にいるなら1,そうじゃないなら0を出す。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,s,t;
cin >> n >> s >> t;
map<pair<int,int>,bool>mp;//一度でも火が通ったことのある場所をメモ
pair<int,int>now = {0,0};
mp[now] = true;
for(int i=0;i<n;i++){
char c;
cin >> c;
//風に立ち向かう方向に人と火を進める。
if(c == 'N') now.first++,s++;
if(c == 'S') now.first--,s--;
if(c == 'W') now.second++,t++;
if(c == 'E') now.second--,t--;
mp[now] = true;
if(mp[{s,t}]) cout << '1';//人の現在地にかつて火があったら１
else cout << '0';//そうでなければ０
}
cout << endl;
}
E - Tree Game
考察
久々のインタラクティブ問題。デバックは大変だが、少々テンションが上がる。
奇閉路ができないように云々と書いていて分かりづらいので簡単に言い換えたい。
奇閉路になる場合の説明を噛み砕くと二つの頂点が奇数距離離れてるものと読み取れる。つまり二つの頂点が偶数離れているか奇数離れているかが分かればほぼ終わり。
この手のものは偶奇性を使うと上手くいく。頂点を黒と白に塗り分けるとして、ある頂点をとりあえず黒く塗る。その後塗ったところから順に隣り合う頂点を別の色に塗る分ける。この時同じ色は奇数個、違う色は偶数個離れていることになる。
あとは全ての頂点に対して色の違う組を列挙すれば結ぶことのできる辺が全てもとまる。
ここまで来ればK個の辺を順に選び、選べなくなったら負けという~何の面白みもない~ゲームになる。このゲームはKが奇数なら先攻有利、偶数なら後攻有利となる。
方針をまとめると
・頂点を白と黒で塗り分ける。
・白い頂点と黒い頂点の組を全探索。
・組数が偶数なら後攻、奇数なら先攻を選ぶ。
・まだ使ってない辺を宣言する。
で上手くいく。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
vector<vector<bool>>path (n,vector<bool>(n,false));
for(int i=0;i<n-1;i++){
int x,y;
cin >> x >> y;
x--,y--;
path[x][y] = true;
path[y][x] = true;
}
vector<int>cl (n,-1);//色を塗り分けを管理
queue<int>que;
que.push(0);
cl[0] = 0;//とりあえず頂点0を黒にする
while(!que.empty()){
int x = que.front();
que.pop();
for(int i=0;i<n;i++){
if(path[x][i] && cl[i] == -1){
cl[i] = 1 - cl[x];//隣の色を自分とは別の色に
que.push(i);
}
}
}
set<pair<int,int>> st;//白と黒の頂点の組みを探す。
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(!path[i][j] && cl[i] != cl[j]) st.insert({i,j});
}
}
if(st.size()%2 == 0) {
cout << "Second" << endl;//偶数なら後攻
int x,y;//相手の一回目を確認
cin >> x >> y;
x--,y--;
if(x == -2) return 0;
if(x > y) swap(x,y);
st.erase({x,y});
}
else cout << "First" << endl;//奇数なら後攻
while(true){
auto[x,y] = *st.begin();//まだ呼ばれていない先頭の辺を出力
st.erase({x,y});//使った辺は消す。
cout << x+1 << " " << y+1 << endl;
int s,t;
cin >> s >> t;
if(s == -1) return 0;
if(s > t) swap(s,t);//小さい順にしておく
st.erase({s-1,t-1});
}
}
結果
バーチャル参加
ABCDE 5完 49:07
順位 2466位(相当)
パフォーマンス 1113(相当)
感想
50分で5完しても緑パフォなんですか⁉︎
多分インタラクティブを避けてF問題に行った人が多いんだろうなぁ。
参加たら冷えてたと思うと背筋が凍る。
頼む、点数よ。暴れないでくれ。