サンプルを抜けるバグに翻弄された男の備忘録です
コンテスト概要
AtCoder Beginner Contest 396
開催日:2025年3月8日 21:00-22:40
A - Triple Four
考察
$A_i$を基準として、$A_i = A_{i-1}$,$A_i = A_{i+1}$ になっている場所が1つでもあればYes。
にしてもトリプル４の由来はなんだろうか？同じ名前のサービスはあったが...
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
vector<int>num (n);
for(int i=0;i<n;i++) cin >> num[i];
string ans = "No";
for(int i=1;i<n-1;i++){
//ひとつ前、ひとつ後と同じならYes
if(num[i-1] == num[i] && num[i] == num[i+1]) ans = "Yes";
}
cout << ans << endl;
}
B - Card Pile
考察
カードを上において、上から取り出す典型的なStackの練習問題。
stackが空の時０を出力としてもいいが例外処理がめんどくさいのであらかじめstackに０を連打。
後はひねりのないStackを。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
//とりあえず100枚の0をstackに積む
stack<int>st;
for(int i=0;i<100;i++) st.push(0);
for(int i=0;i<n;i++){
int x;
cin >> x;
if( x== 1){
//クエリ１ならstackに積む
int y;
cin >> y;
st.push(y);
}else{
//クリエ２なら上のカードを取り出し捨てる
cout << st.top() << endl;
st.pop();
}
}
}
C - Buy Balls
考察
ややこしそうで、ややこしくない、ちょっとややこしい問題。
まずは白のボールに注目する。白のボールをn個以内選ぶときの価値の最大を求めたい。
基本的には価値が高いものから順に選んでいく。ただ価値がマイナスのボールはとるだけ損なのでそれ以降は無視。
その後、黒を価値の高い順にとっていく。黒をn個とったとき、白をn個以下選んだ価値の最大を足せばよい。
黒と白を逆にとらえておりあわや1ペナ。サンプル様様。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
int n,m;
cin >> n >> m;
vector<ll>bb (n),wb (m);
for(int i=0;i<n;i++) cin >> bb[i];
for(int i=0;i<m;i++) cin >> wb[i];
sort(bb.begin(),bb.end(),greater<ll>());
sort(wb.begin(),wb.end(),greater<ll>());
//サイズが小さいと比べずらいので無価値なボールを追加し数合わせ
while(wb.size() < bb.size()){
wb.push_back(-(1LL<<30));
}
vector<ll>wv (n+1,0);
for(int i=0;i<n;i++){
//追加して価値が増えるなら追加、そうでないなら何もしない。
wv[i+1] = max(wv[i],wv[i] + wb[i]);
}
ll ans = 0,sum = 0;
for(int i=0;i<n;i++){
sum += bb[i];
//価値のある順に足していき、i個以下の白の価値の最大値を足す。
ans = max(ans,sum + wv[i+1]);
}
cout << ans << endl;
}
D - Minimum XOR Path
考察
制約が10なのでnext_permutationの出番濃厚。
XORの最小値を調べるので、全探査を背ざる負えない。順列全探査確定！
next_permutationで調べるべきルートを全て調べる。終わり。
個人的にはC問題よりやることがはっきりしていて実装しやすかった印象。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
int n,m;
cin >> n >> m;
//最初以降のルートを調べるため、1以降の数列を用意
vector<int>num (n-1);
for(int i=1;i<n;i++) num[i-1] = i;
vector<vector<ll>>path (n,vector<ll>(n,-1));
for(int i=0;i<m;i++){
int x,y;
ll c;
cin >> x >> y >> c;
x--,y--;
path[x][y] = c;
path[y][x] = c;
}
ll inf = (1LL<<61);
ll ans = inf;
do{
int bef = 0;
ll now = 0;
for(auto x:num){
//そもそもルートがつながっていないなら論外
if(path[bef][x] == -1){
now = inf;
break;
}
//通った辺のラベルをXOR
now ^= path[bef][x];
bef = x;
//早めにn番目が来たら終了
if(x == n-1) break;
}
ans = min(ans,now);
}while(next_permutation(num.begin(),num.end()));
cout << ans << endl;
}
E - Min of Restricted Sum
考察
とっかかりがあまり見えてこない問題。飛ばそうかとも思ったがそれで一度失敗してるのでとりあえず考える。
考えにくくなるのでまずは「矛盾はしない」「最小値じゃなくてもいい」という前提で考える。そうすれば適当な1点から始めそこを0とおく。その後BFSないしDFSで辺に合わせた数を連鎖的においていけば解は求まる。この時うまくいかなければ「矛盾」ということにすればいい。
問題は「最小値」。ここでサンプルのキャプションを見ると{1,2,5},{7,4,3},{0,3,4}という3つの解が乗っている これを二進数で見ると
001 111 000
010 100 011
101 011 100
となっている。ここで縦に見ると１と０の出現パターンが同じもしくは完全な反転になっていることがわかる。となれば1の数が少ない出現パターンのほうに合わせればうまくいくはず。
グラフが連結とは限らないことも考慮して実装。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
int n,m;
cin >> n >> m;
vector<vector<int>>num (n,vector<int>(0));
map<pair<int,int>,ll>mp;
map<pair<int,int>,bool> che;
for(int i=0;i<m;i++){
int x,y;
ll c;
cin >> x >> y >> c;
x--,y--;
//自己ループが０じゃないなら矛盾
if(x==y && c != 0LL){
cout << "-1" << endl;
return 0;
}
if(x == y) continue;
//多重辺の要素に食い違いがあるなら矛盾。
if(che[{x,y}] && mp[{x,y}] != c){
cout << "-1" << endl;
return 0;
}
if(!che[{x,y}]){
che[{x,y}] = true;
che[{y,x}] = true;
mp[{x,y}] = c;
mp[{y,x}] = c;
num[x].push_back(y);
num[y].push_back(x);
}
}
vector<ll>ans (n,-1);
for(int i=0;i<n;i++){
//まだ見てないならそれを0とする。
if(ans[i] != -1) continue;
ans[i] = 0;
vector<int>grp (0);
queue<int>que;
que.push(i);
while(!que.empty()){
int x = que.front();
que.pop();
grp.push_back(x);
for(auto y:num[x]){
ll q = mp[{x,y}];
if(ans[y] == -1){
//まだ行ってないならXORをラベルに合わせる
ans[y] = (ans[x]^q);
que.push(y);
}else{
//すでに言ってる場合ラベルと食い違うなら矛盾
if((ans[y]^ans[x]) != q){
cout << "-1" << endl;
return 0;
}
}
}
}
ll p = 0;
//各桁ごとに１と０のどちらが多いかを確認
for(int j=0;j<31;j++){
int co = 0,cz = 0;
ll che = (1LL<<j);
for(auto x:grp){
if((che&ans[x])) co++;
else cz++;
}
if(co > cz) p += che;
}
//１が少ないパターンに合わせる。
for(auto x:grp) ans[x] ^= p;
}
for(auto x:ans){
cout << x << endl;
}
}
F - Rotated Inversions
考察
ある数が0になるときに転倒数が変わるので各数字ごとに左右にある大きい数、小さい数の個数を持っているとよさそう。
ということは分かったが、さすがに10分ではどうしようもなかった。
結果
ABCDE(2) 5完 94:18
順位 1645位
パフォーマンス 1334
感想
欲を言えばもう少し上位を目指せた気がするが定位置に戻ってきたのでいったん良しとする。
無事再入水！まじで落ちたくない