年内最後のABC、有終の美を飾りたかった男の備忘録です。
コンテスト概要
AtCoder Beginner Contest 386
開催日:2024年12月28日 21:00-22:40
A-Full House 2
考察
カードの状態は「1枚、1枚、1枚、1枚」「1枚、1枚、2枚」「1枚、3枚」「2枚、2枚」「4枚」の5パターンしかない。そしてこの中でフルハウスになりうるのは「1枚、3枚」「2枚、2枚」の2パターン。
ここでカードの種類に注目するとカードの状態の中で「2種類」の時だけとわかる。
なので、カードの種類が2種類か否かさえ調べればOK
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
vector<bool>num (14,false);//カードを見たか確認用
int ans = 0;
for(int i=0;i<4;i++){
int x;
cin >> x;
if(!num[x])ans++;//見てなければカウントを増やす
num[x] = true;
}
if(ans == 2) cout << "Yes" << endl;
else cout << "No" << endl;
}
B-Calculator
考察
実際に電卓に入れていくとき、"00"となる場所をあえて2回に分ける意味がない。
ただただ前から順に確認していき"00"となる部分を見つけたら次の文字はもう見たことにする。
(この問題どっかで見た気がするのだが気のせいだろうか？)
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
cin >> s;
int ans = 0,n = s.length();
for(int i=0;i<n;i++){
if(i!=n-1){
if(s[i] == '0' && s[i+1] == '0'){
i++;
}
}
ans++;
}
cout << ans << endl;
}
C-Operate 1
考察
そもそもsとtの長さが2以上のとき、明らかに1手で直せるわけがないので無視。
まずsとtの長さが同じとき、前から順番に見ていき文字が異なっている場所が帰るべき場所となる。異なっている場所が2以上なら不可能。
sとtの長さが1違いのとき、短いを基準として前から順にみていき長いほうの削除すべき文字を探す。削除すべき文字が2以上なら不可能。
一度これで実装するがWA。次に削除する文字を全探査するもTLE。もう一度この考察で提出しAC。何が駄目だったんだ？
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int k;
string s,t;
cin >> k >> s >> t;
if(s.length() < t.length()) swap(s,t);
//考えやすいようsが長いに統一
int n=s.length(),m = t.length();
if(1 < n-m){
cout << "No" << endl;
return 0;
}
//差が2以上ならそもそも調べない。
string ans = "Yes";
if(n-m == 1){
int now = 0;//何文字ずらすかの変数
for(int i=0;i<m;i++){
if(s[i+now] != t[i]) now++;
//文字が違う場合s[i+now]は削除される。
//そのため参照する場所が1ずれるのでnowを1増やす
if(now > 1){
ans = "No";
break;
}
//値が2ずれるなら一致不可能
}
}
if(n-m ==0){
int now = 0;
for(int i=0;i<n;i++){
if(s[i] != t[i]) now++;
}
//愚直に違う文字の数を数える
if(now > 1) ans = "No";
}
cout << ans << endl;
}
D-Diagonal Separation
考察
Nが$10^9$なので全マス管理はまず不可能。何とかして情報をコンパクトにする必要がある。
ここでマスを塗る順番で可能、不可能が変わることはない。なら黒と白をランダムに塗るよりどっちかを塗りきってから、もう一方がいけるかを確認したほうが良い。
(s,t)を白く塗った場合、(s,t)~(s,n),(s,t)~(n,t)も白く塗る必要がある。すると連鎖的に(s,t),(n,n)を頂点とする四角形内のマスはすべて白で塗る必要がある。
つまり、xがs以上のマスにおいてyの値がt以上の場所は白く塗ったことになる。のでこの範囲に黒を塗ろうとすると矛盾が生じる。
白く塗るマスについてxが小さい順に見ていきyの値を更新したらvectorに収めていく。これをyでも行う。
あとは黒く塗るときにこのxを塗るときに塗ってはいけないyの値の下限値を二分探査で検索して矛盾しなければOK。これをyでもすればおしまい。
添え字がぐちゃぐちゃになってパニックになっていたら1時間ほどとってしまった。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin >> n >> m;
vector<pair<int,int>>bl (0),whx (0),why (0);
for(int i=0;i<m;i++){
int x,y;
char c;
cin >> x >> y >> c;
if(c == 'B')bl.push_back({x,y});
else{
whx.push_back({x,y});
why.push_back({y,x});
}
}
sort(whx.begin(),whx.end());
sort(why.begin(),why.end());
//白く塗る場所をxの値、yの値でソート
map<int,int>wx ,wy;
wx[0] = n+1,wy[0] = n+1;
wx[n+1] = 0,wy[n+1] = 0;
//それぞれについて下限と上限を設けておく
vector<int>wwx (1,0),wwy (1,0);
int bf = n+1;
for(auto [s,t]:whx){
if(t >= bf) continue;
//yの値が更新されないなら無視
wwx.push_back(s);
wx[s] = t;
bf = t;
}
bf = n+1;
for(auto[s,t]:why){
if(t >= bf) continue;
//xが更新されないなら無視
wwy.push_back(s);
wy[s] = t;
bf = t;
}
wwx.push_back(n+1),wwy.push_back(n+1);
string ans = "Yes";
for(auto [s,t]:bl){
int xx = *prev(upper_bound(wwx.begin(),wwx.end(),s));
int yy = *prev(upper_bound(wwy.begin(),wwy.end(),t));
//塗ってはいけないyの下限とxの下限を二分探査
if(wx[xx] <= t) ans = "No";
if(wy[yy] <= s) ans = "No";
}
cout << ans << endl;
}
E-Maximize XOR
考察
どうせ$10^6$パターンしかないのでうまく全探査でできればいいんだろと残された20分でBFSを実装する。
が、途中で計算量が爆発しTLEでタイムアップ。
$nCk = nC(n-k)$をちゃんとケアできればと後悔するも焦る気持ちに20分は短すぎた。
提出(コンテスト後)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll>num;
ll che(int now,int rem,int sel,ll x,ll sum){
ll ans = 0;
if(sel == 1)ans = max(ans,(sum^(x^num[now])));
//選べるのがあと一つなら選んだものが最終結果
if(rem > sel) ans = max(ans,che(now+1,rem-1,sel,x,sum));
//まだまだ要素が残ってないなら選ばないという選択もとれる。
if(sel != 1) ans = max(che(now+1,rem-1,sel-1,(x^num[now]),sum),ans);
//選んだうえでまだ値が残ってるなら次のステップへ
return ans;
}
int main(){
int n,k;
cin >> n >> k;
num.resize(n);
ll sum = 0;
for(int i=0;i<n;i++){
cin >> num[i];
sum ^= num[i];
}
if(n-k < k) k = n-k;//(n-k)とnのうち小さいほうに合わせる
else sum = 0;
if(k == 0) cout << sum << endl;
else cout << che(0,n,k,0ll,sum) << endl;
//(n-k)に変えた場合全体から引く操作を行う
//変えてないなら0を引くことにする。
}
結果
ABC(2)D 4完 89：14
順位 2091位
パフォーマンス 1112
レート 1130(-2)
感想
最後の最後でこけるのは何とも私らしい。これもC問題を2回ミスり完全に平常心を失ったせいだろう。
まぁこの悪いものをすべて2024年に置いていく儀式だったとらえておこう。
来年は1月中に入水するぞ！