practice SRM 472 div2

SRM 472 Div2
250
R,G,B,Yの4パターンがランダムに並べられたとき、同じパターンが隣り合わないように他のパターンに差し替える最小回数を求めるらしい

#include<string>
using namespace std;
class ColorfulTilesEasy{
public:
  int theMin(string room){
    int j = room.length();
    int i,ans = 0;
    int chc;
    char ptn[] = {'R','G','B','Y'};
    for(i = 0; i < j - 1; i ++){
      if(room[i]  == room[i + 1]){
 ans ++;
 chc = 0;
 while(1){
   if((room[i + 1] != ptn[chc]) && (room[i + 2] != ptn[chc]))
     break;
   chc++;
 }
 room[i + 1] = ptn[chc];
 i++;
      }
    }
    return ans;
  }
};

適当に考えたけど、アルゴリズムとしては、隣り合った2つの2番目を入れ替えれば前にも後にも影響が無い、と思う。
後から気づいたけど、これi += 2でやっても多分問題ないよね。

500
タロイモと花子が揚げ芋を4の累乗ずつ食べていって最後の一個を喰らったら勝ちという問題。
実際いろいろ試した結果、末尾が0,2,5,7の時は花子が勝つらしいことに気づく。

#include<string>
using namespace std;
class PotatoGame{
public:
 string theWinner(int n){
  int ptn[] = {1,3,4,6,8,9};
  int i;
  n = n % 10;
  bool f = false;
  for(i = 0; i < 6; i++){
   if(n == ptn[i])
    f = true;
  }
  if(f == true){
   return ("Taro");
  }else{
   return ("Hanako");
  }
 }
};

今回は特に規則性を思いつかなかったからパターンを配列化してしまったけど、n%5 == 0 or 2なら花子が勝ちだから

#include<string>
using namespace std;
class PotatoGame{
public:
 string theWinner(int n){
  if(n % 5 == 2 || n % 5 == 0){
   return ("Taro");
  }else{
   return ("Hanako");
  }
 }
};

確認してないけどこれでいけると思う。
明日はこれの1000点問題をちょっとといてみたいと思う。