ABCは126はA～Fの6問と、大幅に改変された節目の回になります。令和に切り替わったのもこの辺りなので、4問のABCを平成ABC、6問のABCを令和ABCとかって呼んでます(多分)。
単純に6問あるので埋めるのがしんどいということもあって放置していたのですが、少しずつ手を付けていきます。
A – Changing a Character
A – Changing a Character (atcoder.jp)
指定された文字を大文字から小文字に変換する問題。
C++だとtolowerとかを使えばOKです。注意点は文字列は0-indexなのに対し、Kは1-indexです。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int N,K;
cin>>N>>K;
string S;
cin>>S;
S[K-1]=S[K-1]-'A'+'a';
cout<<S<<endl;
}
大文字→小文字変換は、’A’を引いてabcd…の何番目かを抽出。そこに’a’を足すことによって小文字にしました。
B – YYMM or MMYY
YYは00～99どれでもあり得ますが、MMは01～12の範囲しかありえません。
入力値を上2桁と下2桁に分けて、01～12の間かどうかをチェックし、true,falseの組み合わせで出力文字を判定します。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int S;
cin>>S;
int aa=S/100;
int bb=S%100;
bool f1=aa>=1&&aa<=12;
bool f2=bb>=1&&bb<=12;
if(f1&&f2) cout<<"AMBIGUOUS"<<endl;
else if(f1) cout<<"MMYY"<<endl;
else if(f2) cout<<"YYMM"<<endl;
else cout<<"NA"<<endl;
}
C – Dice and Coin
C – Dice and Coin (atcoder.jp)
サイコロの目がAのとき、何回でKを越えるかはシミュレーションするのが早いです。
2倍していくため計算量はそこまで膨れません。(最低のA=1の時でもlogK程度。K=10^5でも20回以内に終わる)
Nの最大も10^5が最大なので、1～Nの全パターンに対して確率計算し、足して時間的に問題なさそうです。
確率の式は入力例 1に詳しく書いてあるので、それを元に実装すればOKです。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int N,K;
cin>>N>>K;
double No=1.0/N;
double ans=0;
for(int i=1;i<=N;i++){
int c=0;
int n=i;
while(n<K){
n*=2;
c++;
}
double co=1.0/pow(2,c);
//cout<<No<<","<<co<<endl;
ans+=No*co;
}
printf("%.12f\n",ans);
}
D – Even Relation
D – Even Relation (atcoder.jp)
この問題の制約下では、そのような塗り分け方が必ず 1 つは存在することが証明できます。
この文章がヒントです。つまり、ある頂点から見て、各頂点への距離が偶数である場所は必ず同じ色に、奇数は必ず違う色になります。
ある頂点は適当に決めてOKです。他の頂点で矛盾が生じるのでは？と感じそうですが、矛盾がある場合に問題のような塗り分けが不可能になるため、問題なしです。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int N;
cin>>N;
vector<pair<int,int>> e[N+1];
for(int i=0;i<N-1;i++){
int u,v,w;
cin>>u>>v>>w;
e[u].push_back(make_pair(v,w));
e[v].push_back(make_pair(u,w));
}
queue<int> q;
q.push(1);
int ans[N+1];
for(int i=0;i<N+1;i++) ans[i]=-1;
ans[1]=0;
while(!q.empty()){
int n=q.front();
q.pop();
for(int i=0;i<e[n].size();i++){
int t=e[n][i].first;
int c=e[n][i].second;
if(ans[t]==-1){
ans[t]=ans[n]+c;
q.push(t);
}
}
}
for(int i=1;i<=N;i++){
if(ans[i]%2==0) cout<<"0"<<endl;
else cout<<"1"<<endl;
}
}
E – 1 or 2
偶奇の足し算は以下になります。
偶+偶=偶 奇+奇=偶 偶+奇=奇
なので、Ziが奇数の場合、Xi+Yiは奇数でXiかYiのどちらかが偶数、どちらかが奇数になります。
Ziが偶数の場合、Xi+Yiは偶数で両方が偶数か、両方が奇数になります。
つまり、Ziの値に関わらずXiかYiのどちらかが確定しないと両方が判明せず、どちらかが分かれば両方判明します。
入力例2で4が判明した時を考えます。
4が判明 →4 5 1 があるので、5がどちらか判明する。 →5 6 5 があるので、6がどちらか判明する。
と、芋づる式に判明します。このように、数字で数珠繋ぎになっているものはどれか1つが分かれば一気に判明します。
この数珠繋ぎ…UnionFindっぽいですね。
ということで、この問題は各カードを頂点とし、UnionFindでグループ分けした際のグループ数が答えとなります。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
int N,M;
cin>>N>>M;
dsu d(N+1);
for(int i=0;i<M;i++){
int X,Y,Z;
cin>>X>>Y>>Z;
d.merge(X,Y);
}
auto v=d.groups();
cout<<v.size()-1<<endl;
}
atcoderライブラリのdsu(unionfind)では、group()で各グループの頂点が取得できます。
vector<vector<int>>で外側のvectorは頂点集合を持つグループです。なのでsize()でグループ数が取れます。
F – XOR Matching
難しそう。というか感覚で解いちゃって説明ができない。
まずXORの性質上桁が増えないので、Kが2^M以上なら不可能です。M=1,K=1とM=1,K=0は入力例に答えがあるので、これでM=1の時の答えは決まりました。
M=2以上の時ですが、
0 1 2 3 3 2 1 0
と並べることを考えます。こう並べると、任意の数字間のxorが全て0になります。
0 1 3 3 1 0
さらに数字を1種類消しても、任意の数字間のxorが0になります。なので、
0 1 3 2 3 1 0
真ん中に消した数字を入れると、2以外の任意の数字間のxorが2になります。さらに、
2 0 1 3 2 3 1 0
2を端に置くことで、2以外の任意の数字間には影響を与えず、2の間のxorを2にすることができます。つまり、全ての任意の数字間においてxorが2になります。
0～(2^N)-1のxorを考えます。 0:0 0 1:0 1 2:1 0 3:1 1 と、各桁の1bitが偶数回現れるため、0になります。 なので、どれかの数字を一個抜くと、その抜いた数字に立ってたbit1の場所が1つ減って奇数個になり、xorが抜いた数字と同等になります。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
int M;
int K;
cin>>M>>K;
if(M==1){
if(K==0) cout<<"0 0 1 1"<<endl;
else cout<<"-1"<<endl;
}
else if(K>=pow(2,M)) cout<<"-1"<<endl;
else{
cout<<K<<" ";
for(int i=0;i<=pow(2,M)-1;i++){
if(i!=K) cout<<i<<" ";
}
cout<<K<<" ";
for(int i=pow(2,M)-1;i>=0;i--){
if(i!=K) cout<<i<<" ";
}
cout<<endl;
}
}
何となく思いつきゲーな感じがしますが…。xorは色々暴れられるので個人的に好きです。
コメント