AOJ 2362 - Chicken or the Egg

問題概要

"Chicken"と"egg"のみで構成された文字列がある。
次のルールに従って先に生まれた方を出力する。

1. 異なる2つが並んでいる(chickenegg または eggchicken)場合、後ろのものが先に生まれる。
2. 同じ2つが並んでいる(eggegg または chickenchicken)場合、*egg egg*、*chicken chicken*に分解する。*は0文字以上の文字列。
3. ルール2で分解したそれぞれの文字列に対してeggとchickenの総数を求め、それが最大のものを選ぶ。複数ある場合は早く出現した文字列を選ぶ。例えば、サンプル2の"chickeneggeggchicken"という文字列ならば、"chickenegg"と"eggchicken"という文字列に分解して、それぞれ総数が2なので早く出現した"chickenegg"を選ぶ。最後に選ばれた文字列に対してルール1を適応する。

制約

入力の単語数は1以上1000以下。

解法

ルール通りシミュレーションする。

コード

#include <bits/stdc++.h>

using namespace std;

struct P{
  int a,b;
  string c;
  
  P(int a,int b,string c) : a(a),b(b),c(c) {}
  bool operator < (const P &p)const{
    if(a != p.a){
      return a > p.a;
    }else{
      return b < p.b;
    }
  }
};

int main(){
  string str,s;
  map<string,string> mp;
  mp["e"] = "egg";
  mp["c"] = "chicken";
  cin >> str;
  for(int i = 0 ; i < (int)str.size() ; i++){
    if(str[i] == 'e'){
      i += 2;
      s += 'e';
    }else{
      i += 6;
      s += 'c';
    }
  }
  int size = s.size();
  if(size == 1){
    cout << mp[s] << endl;
  }else{
    vector<P> vec;
    string tmp; tmp += s[0];
    for(int i = 1 ; i < size ; i++){
      if(s[i-1] == s[i]){
        vec.push_back(P(tmp.size(),i,tmp));
        tmp = "";
      }
      tmp += s[i];
    }
    if(!tmp.empty()){
      vec.push_back(P(tmp.size(),size,tmp));
      tmp = "";
    }
    sort(vec.begin(),vec.end());
    tmp += vec[0].c[vec[0].c.size()-1];
    cout << mp[tmp] << endl;
  }
  return 0;
}