読者です 読者をやめる 読者になる 読者になる

マトリョーシカ的日常

ワクワクばらまく明日のブログ。

右がわ左がわ交互に見て!(SRM538 div2-1)

topcoder

あっちへいったりこっちへ来たり

 writer friend caught in action - 無料写真検索fotoq
photo by ♥ roco julie

 前からブログは書いていましたが、プログラミングの話題だけこちらに移転することにしました。topcoderというプログラミング大会に出場したり、過去問を解いたりしていこうと思います。言語はC++で。アカウントの登録方法など、topcoderの始め方も書いていけたらいいなぁ。

 

 さて、記念すべき第一回目はSRM538 div2 level1に挑戦です。topcoderは月に二回ほどネット上で開かれていて538はその大会の番号です。538回目という訳ではありませんが。また、アカウントのレートでdivision1とdivision2に分けられており、その中でそれぞれ三つの設問があります。div2のlevel1とは一番簡単な問題ということです。

 TopCoder Statistics - Problem Statement

 問題。一体の左右に動くロボットがいます。L,Rの二種類のコマンドによって左右に一歩ずつ進みます。コマンドはLとRからなる文字列として入力されます。出力は初期位置から最も遠くに移動したときの距離です。たとえば入力が"LLLR"なら出力は3です。

 しかし問題が発生し、コマンドに?が含まれてしまいました。?が含まれるコマンドが入力されるとき、出力の最大値を返せ。

 

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stdlib.h>
using namespace std;
 class LeftOrRight{
	public:
	int maxDistance (string str1)	{
        cout <<"str1=:"<< str1 <<endl;
        int i,j,k=3,dis=0,pos=0,maxd=0;
        string::size_type index=str1.find("?");
        if (index==string::npos) k=1;
        for(j=-1;j<k;j+=2){
            printf("-----\n");
            for(i=0;i<str1.size();i++){
                if(str1[i]=='R') pos++;
                if(str1[i]=='L') pos--;
                if(str1[i]=='?') pos+=j;
                dis=max(dis,abs(pos));
                printf("dis= %d : pos = %d\n",dis,pos);
            }
            maxd=max(dis,maxd);
            dis=0;pos=0;
        }
        printf("maxdistance:%d\n",maxd);
        return maxd;
    }
};

int main(){
    LeftOrRight ob1;
    string row("???LLLRLRRR");
    ob1.maxDistance(row);
    return 0;
}
  • 現在の位置と、距離という二つの変数を用意します。前の距離より現在の位置の絶対値がおおきければ新しい距離として上書きされます。
  • >||string::size_type index=str1.find("?");||<で文字列に?があるか探しています。

なかったら、string::nposを返します。

  • 最大の距離を返せばいいのだから、?は全てRか全てLになるはず。?を含む場合はループを二回にして、?が全てRのときとLのときで場合分けしています。