AtCoder Beginner Contest 244 D - Swap Hats
問題の要約
1,2,3の番号が付いた3人のT君がおり、赤・緑・青の色がついた3種類の帽子がそれぞれ1つずつある。
それぞれのT君は帽子を1つかぶっており、T君iがはじめにかぶっている帽子の色は文字Siで表される。
ここで、Rは赤、Gは緑、Bは青に対応している。これから、以下の操作をちょうど10^18回行う。
操作
・3人のT君のうち2人を選ぶ。2はお互いのかぶっている帽子を交換する。
10^18回の操作の後、T君iが文字Tiに対応する色の帽子をかぶっているようすることはできるか?
制約
S1,S2,S3はR,G,Bの並べ替え
T1,T2,T3はR,G,Bの並べ替え
入力
S1 S2 S3
T1 T2 T3
考え方
1,R,G,Bの順列は3P3=3!/(3-3)!=3*2*1=6である。
その6通りは
R,G,B
G,R,B
R,B,G
B,G,R
G,B,R
B,R,G
2,S1,S2,S3をR,G,Bとしたときの操作の回数に注目する。
R,G,B -> 0回
G,R,B -> 1回
R,B,G -> 1回
B,G,R -> 1回
G,B,R -> 2回
B,R,G -> 2回
3,S1,S2,S3をR,G,Bとしたときの操作の回数の共通点に注目する。
0回は1つだけで全ての文字が同じ。
1回は3つだけで同じ文字が1つ必ずある。
2回は2つだけで同じ文字がない。
4,S1,S2,S3が任意のときに成り立つか考える。
0回の操作では、文字の順序を変えないので必ず全ての文字が同じになる。
1回の操作では、2つを選んで交換するので、必ず一つの文字が同じになり、他2つは違う文字になる。
2回の操作では、2回目の操作の時に1回目の操作で選んだ2つを選ぶと0回の操作と同じになり、それ以外では必ず全てが違う文字になる。
5,ちょうど10^18回のときを考える。
10^18は偶数なので必ず偶数回操作になる。
よって、S1,S2,S3とT1,T2,T3のそれぞれの文字が全て同じときと、全て違うときだけ可能である。
実際のプログラム
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int main(){
vector<string> S(3);
cin >> S[0] >> S[1] >> S[2];
string Sstr = S[0]+S[1]+S[2];
vector<string> T(3);
cin >> T[0] >> T[1] >> T[2];
string Tstr = T[0]+T[1]+T[2];
bool check = false;
if(S[0] == T[0] && S[1] == T[1] && S[2] == T[2]){
check = true;
}else if(S[0] != T[0] && S[1] != T[1] && S[2] != T[2]){
check = true;
}
if(check){
cout << "Yes" << endl;
}else{
cout << "No" << endl;
}
return 0;
}