腹痛と闘い続けた男の備忘録です
コンテスト概要
AtCoder Beginner Contest 426
開催日:2025年10月4日 21:00-22:40
A - OS Versions
考察
久々にパット分かりづらいA問題。
要するにXがY以降のバージョンか？という問題だが、こう具体例になると少々わかりづらくなる。どっちが古いんだ？表にするとこうなる。
| X\Y | Ocelot | Serval | Lynx |
|---|---|---|---|
| Ocelot | Yes | No | No |
| Serval | Yes | Yes | No |
| Lynx | Yes | Yes | Yes |
実装は好きにすればいいが、Yesのほうが多いのでNoの時をうまく例外処理すればOK。
なんとなくいつぞやの"YELLOW"→"RRR"を思い出す問題だがここもAIトラップがあったんだろうか？
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
string s,t;
cin >> s >> t;
string ans = "Yes";
//表を参照して上手く場合分け
if(s == "Ocelot" && t != "Ocelot") ans = "No";
if(s == "Serval" && t == "Lynx") ans = "No";
cout << ans << endl;
}
B - The Odd One Out
考察
テクニカルなことをしようとすると失敗しそうな問題。
おとなしく文字ごとに個数を数えて1個だったものを出力。
大抵B問題で手の込んだことをすると失敗するんだよね。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
string s;
cin >> s;
vector<int>num (26,0);//文字ごとの個数を管理
for(auto x:s){
num[x-'a']++;
}
for(int i=0;i<26;i++){
char ans = 'a' + i;
//使った回数が1回なら出力
if(num[i] == 1) cout << ans << endl;
}
}
C - Upgrade Required
考察
シンプルに考えるのであればX以前のバージョンであるものの個数を答えとして出力。
その後、X以前の個数を0にしたうえでバージョンYにアップデートした数を足せばいい。
この手のものは遅延セグメントツリーを使えば実装可能である。
が、あくまでこれはC問題もう少し簡単に解ける方法はないか探ってみる。
例えばある時点でバージョン10以前のものはすべて11以降にアップデートしたとする。
このときで10以前のバージョンがインストールされたPCは存在しない。
となると、これ以降10以前のバージョンが存在するか確認する必要がそもそもなくなる。
まとめると、あるバージョンをアップデートするとき、それがいくつ存在するかを確認するタイミングは高々1回しか存在しないということになる。
なので、バージョンごとにインストールされているPCの数を記録しておき、前から順に1回だけ見ればうまくいく。
高等知識で殴るか、しっかりとかみ砕くか。方針が分かれそうな問題だった。
私は遅延セグ木をちゃんと理解していないので殴れませんでした。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
int n,q;
cin >> n >> q;
//バージョンがインストールされているPCの数
vector<int>cnt (n+1,1);
cnt[0] = 0;
int now = 0;
for(int rp=0;rp<q;rp++){
int x,y;
cin >> x >> y;
int sum = 0;
//まだアップデートされたことのないバージョンの最初からバージョンXまで
//Xが古いならそもそもforが回らない。
for(int i=now;i<=x;i++){
sum += cnt[i];
cnt[i] = 0;
}
//バージョンYの数を増やす
cnt[y] += sum;
//次に見始めるべきバージョン
now = max(now,x+1);
cout << sum << endl;
}
}
D - Pop and Insert
考察
01の数列を操作するやつは丁寧な考察が求められるので得意じゃない。
最終的な形を定めないとわかりづらいので、すべて1とすべて0の2パターンを分けて考える。
例えば"000110111000"をすべて1にするとき、どこかしらの1の塊を基準にしてなるべく動かしたくない。そして塊ごとに動かしても問題はないので圧縮して動かす。
左にある"11"を基準にすると何とかして右にある1つの"0"を取り出す必要がある。
結果としてその0より右にあるものもすべて移動させなければならない。
この時に移動させた"111"は"000"になるのでもう一度動かす必要がある
動かし方は下の通り
"000"110111000
↓
"111"110111000
↓
111110111"000"
↓
11111"111"0111
↓
111111110"111"
↓
11111111"000"0
↓
111111110000
↓
11111111"0000"
↓
11111111"1111"
よく観察すると塊以外の"1"は2回動かし、"0"は1回だけ動かしている。
なので、どこかの塊を指定して、同じ数字は2回、違う数字は1回動かせば目的の数列になる。
これを実装すればOK。
こうなると、一番デカい塊を基準にすればいいんだけど、コンテスト中は気づかずすべての塊をチェックしてた。
まぁ通ればいいんですよ。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
int t;
cin >> t;
for(int rp=0;rp<t;rp++){
int n;
cin >> n;
//0と1ごとに塊の数を管理
vector<vector<int>>num (2,vector<int>(0));
//0と1の個数もチェック
int s1 = 0,s0 = 0,cnt = 0;
int bef = -1;
for(int i=0;i<n;i++){
char x;
cin >> x;
int now = x - '0';
//値が切り替わったら配列に追加
if(bef != now){
if(bef == 0) num[0].push_back(cnt),s0 += cnt;
if(bef == 1) num[1].push_back(cnt),s1 += cnt;
cnt = 0;
}
cnt++;
bef = now;
}
//最後も忘れずに
if(bef == 0) num[0].push_back(cnt),s0 += cnt;
else num[1].push_back(cnt),s1 += cnt;
int ans = (1<<30);
//基準の塊以外の同じ数の2倍と違う数の合計が移動回数。
for(auto x:num[0]){
int sum = (s0-x)*2 + s1;
ans = min(ans,sum);
}
for(auto x:num[1]){
int sum = (s1-x)*2 + s0;
ans = min(ans,sum);
}
cout << ans << endl;
}
}
E - Closest Moment
考察
幾何苦手なんだよな。
移動時間を算出して、止まっていることも加味しながら3分探査したがWA。
止まった時間で場合分けしないといけなかったんですね。
結果
ABCD 4完 21:17
順位 1519位
パフォーマンス 1378
レート 1354(+3)
感想
やはり数学も勉強しないといけないのか。数学センスってどうやったら磨けますか？
あと、賞味期限が切れたものは食べないようにしましょう。集中できなくなります。