torus711 のアレ

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

Croc Champ 2013, Round 2, Div2 Edition, B : Ksusha the Squirrel

概要

n 個の部分からなる直線上の道路がある。。
道路の各部分は、何も無いか、岩があるかのいずれかである。

はじめ、この道路の左端にリスがいて、右端までいきたい。
リスは、最大で k 個先の部分までジャンプすることができる。
岩の部分を踏まずに左端まで行くことができるかどうか判定せよ。

解法

k 個以上連続した岩の部分が無ければ右端まで到達することができます。

コード

typedef vector<string> VS;

#define ALL( c ) (c).begin(), (c).end()

vector<string> split( const string &str, const string &delim = " " )
{
	int start = 0, pos;
	vector<string> result;

	while ( ( pos = str.find_first_of( delim, start ) ) != string::npos )
	{
		result.push_back( str.substr( start, pos - start ) );
		start = pos + 1;
	}

	return result;
}

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

	int n, k;
	cin >> n >> k;

	string road;
	cin >> road;

	VS rocks( split( road, "." ) );
	cout << ( none_of( ALL( rocks ), [=]( string s ){ return k <= s.size(); } ) ? "YES" : "NO" ) << endl;

	return 0;
}