yokobuttonの不定期で競技プログラミングをするブログ

不定期で解けた競技プログラミングコンテストの問題を載せています。

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;
}