kmjp's blog

競技プログラミング参加記です

UnKoder #01 : FT Robot

UnKoder始めました。
https://www.hackerrank.com/contests/unkoder-01/challenges/ft-robot

問題

左右に伸びる1次元の数直線上でロボットが命令に従って動く。
ロボットは初期状態は原点のおり、右(数直線の正の向き)を動く。

命令は文字列で与えられ、1文字毎に以下のように動く。

  • F : 向いてる向きに1進む
  • T : 向きを左右反転する
  • ? : 上記の2つのどちらを行っても良い。

命令が与えられたとき、命令を処理したのちにロボットがいる可能性があるもっとも右の座標を答えよ。

解法

ロボットについて、

  • 最終的に左向きの状態で存在しうる最も右の座標
  • 最終的に右向きの状態で存在しうる最も右の座標

を1命令ごとに更新していけば良い。

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>s;
	int left=-1000,right=0;
	FORR(c,s) {
		if(c=='F') left--, right++;
		if(c=='T') swap(left,right);
		if(c=='?') {
			x=left,y=right;
			left=max(x-1,y);
			right=max(y+1,x);
		}
	}
	cout<<max(left,right)<<endl;
}

まとめ

ここらへんはまだ簡単。