torus711 のアレ

主に競技プログラミングの問題について書きます

Good Bye 2014, A : New Year Transportation

問題概要

 1 \times n のグリッド状の盤面でゲームを行う.1 \leq i \leq n - 1 の各 i について,セル i からは a_i 個右のセルにのみ移動することができる.
 セル 1 からスタートして,セル t に到達することは可能か?

解法

 題意より,各セルから移動できる場所は一意に定まります.従って,セル t に辿り着くか,右端に到達するまで移動を繰り返すことで,,セル t に到達できるか否かを判定することができます.
 実装に於いては,セル p からの移動は p \left a_p という更新でシミュレートできます.

コード

using VI = vector< int >;

template < typename T > inline istream& operator>>( istream &s, vector< T > &v ){ for ( T &t : v ) { s >> t; } return s; }

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

	int N, T;
	cin >> N >> T;
	--T;

	VI A( N - 1 );
	cin >> A;

	int p = 0;
	while ( p < N - 1 && p < T )
	{
		p = p + A[p];
	}

	cout << ( p == T ? "YES" : "NO" ) << endl;

	return 0;
}