SRM504 Div1Easy MathContest

http://community.topcoder.com/stat?c=problem_statement&pm=11233

愚直に再現すればよさそう。でも色反転の操作がダルそうだったので、状態を別で保持しxorを使うことで省略。初めは以下のコードをsubmitしたが、システスでTLE。よく考えればなので当然。

#include <bits/stdc++.h>
using namespace std;

class MathContest {
public:
   int countBlack( string ballSequence, int repetitions ) {
       int n=ballSequence.size();
       vector<bool> balls;
       for(int i=0;i<repetitions;i++){
           for(int j=0;j<n;j++){
               if(ballSequence[j]=='B') balls.push_back(1);
               else balls.push_back(0);
           }
       }
       int black=0; bool rev=1;
       while(balls.size()){
           bool color=balls.front();
           balls.erase(balls.begin());
           if(color^rev){
               reverse(balls.begin(),balls.end());
           }else{
               rev=!rev;
               black++;
           }
       }
       return black;
   }
};

• 一番上を取り出すときの、erase()
• スタック反転時の、reverse()

この二つがなので省略する必要があったが、ここで異常に悩む。eraseの代替をpop_backで考えていたため、reverseと両立できなかったのが原因。結局、reverseは色反転と同じようにフラグ管理で、eraseはindexを操作することで解決。

#include <bits/stdc++.h>
using namespace std;

class MathContest {
public:
   int countBlack( string ballSequence, int repetitions ) {
       int n=ballSequence.size();
       vector<bool> balls;
       for(int i=0;i<repetitions;i++){
           for(int j=0;j<n;j++){
               if(ballSequence[j]=='B') balls.push_back(1);
               else balls.push_back(0);
           }
       }
       int black=0; bool rev=1,LR=1;
       auto left=balls.begin(),right=balls.end()-1;
       while(left!=right){
           bool color;
           if(LR){
               color=*left;
               left++;
           }else{
               color=*right;
               right--;
           }
           if(color^rev){
               LR=!LR;
           }else{
               rev=!rev;
               black++;
           }
           if(left==right){
               color=*left;
               if(!(color^rev)){
                   black++;
               }
           }
       }
       return black;
   }
};

計算量を落とす問題がどうも苦手…