Codeforces #180, Division 2, A : Snow Footprints

問題文

http://codeforces.com/contest/298/problem/A

概要

グリッドが直線上に並んだ道路がある。
最初、ある位置にくまがいる。
くまが左右どちらかに移動したとき、元いた場所にその向きの足跡が残る。
既に足跡が存在した場合、新しい足跡のみが残る。
道路に残った足跡の情報が与えられるので、最初にくまがいた位置と、最後にいる位置の有効な組を一つ出力せよ。
答えが存在することが保証される。

解法

道路の状態として考えられるのは以下の三パターンです。

• 一つ以上の連続する R と一つ以上の連続する L が繋がっている
• 一つ以上の連続する R のみ
• 一つ以上の連続する L のみ

一つ目のパターンでは、どちらかの端から始めて反対側の端まで行き、RL が接する場所まで戻ってきた位置が最後です。
後ろ二つの場合は、R なら左、L なら右の端から始めて、反対側の端まで行った場所が最後です。
なお、移動をした場合にのみ足跡が付くので、例えば .RRR. だったら最後の位置は一番右の R の右隣になります。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	string road;
	cin >> road;

	int s = -1, t = -1;
	REP( i, 0, n - 1 )
	{
		if ( s == -1 && road[i] != '.' )
		{
			s = i + 1;
		}
		if ( road[i] == 'R' && road[ i + 1 ] == 'L' )
		{
			t = i + 1;
		}
	}
	if ( t != -1 )
	{
		cout << s << ' ' << t << endl;
		return 0;
	}

	for ( int i = n - 1; 0 <= i; --i )
	{
		if ( road[i] != '.' )
		{
			t = i + 1;
			break;
		}
	}
	if ( road[ s - 1 ] == 'L' )
	{
		swap( s, t );
		t--;
	}
	else
	{
		t++;
	}
	cout << s << ' ' << t << endl;

	return 0;
}