Codeforces #199, B : Xenia and Spies

問題文

http://codeforces.com/contest/342/problem/B

概要

n 人の人が一列に並んでいて、s 番目の人がノートを持っている。
ノートを隣の人に渡すことを繰り返して、ノートを f 番目の人に渡したい。
ただし、監視されている間はいかなる動き（ノートを渡す・ノートを受け取る）もできない。

監視は全部で m 回行われる。
i 番目の監視は、時刻 に於いて、[ , ] の区間を監視する。

最小手数で目標を達成するときの手順を求めよ。
解が存在することは保証される。

解法

ノートを逆方向に動かす操作は無駄になるので、そのような操作をする必要はありません。
また、目標方向へ動かすことができるとき、必ず動かした方が得になります。
従って、各ステップに於いて、「動かすことができるなら目標方向へ動かし、そうでないなら何もしない」という処理を繰り返すのが最適な行動となります。

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

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

	int n, m, s, f;
	cin >> n >> m >> s >> f;

	set<int> ts;
	map<int,int> ls, rs;
	REP( i, 0, m )
	{
		int t, l, r;
		cin >> t >> l >> r;
		t--;

		ts.insert( t );
		ls[t] = l - 1;
		rs[t] = r - 1;
	}

	bool right = s < f;
	int dist = abs( s - f ), cur = s - 1;

	for ( LL step = 0; dist; step ++ )
	{
		int next = cur + ( right ? 1 : -1 );
		VI target = { cur, next };
		if ( EXIST( ts, step ) && any_of( ALL( target ), [&]( int tmp ){ return ls[ step ] <= tmp && tmp <= rs[ step ]; } ) )
		{
			cout << 'X';
		}
		else
		{
			cout << ( right ? 'R' : 'L' );
			cur += right ? 1 : -1;
			dist --;
		}
	}
	cout << endl;

	return 0;
}