Codeforces #162 Div2. A. Colorful Stone, B. Roadside Trees

続いて#162も練習。とはいえ#163で初参加した後に解いたんだけどね。
最初の２問は簡単なのでまとめて行きましょう。
http://codeforces.com/contest/265/problem/A
http://codeforces.com/contest/265/problem/B

A. Colorful Stone

石が１列に並んでおり、その色がRGBからなる文字列で与えられる。
また、一連の動作が同じくRGBからなる文字列で与えられる。

プレイヤーは最初一番左の石の上にいる。
動作を与えられたとき、プレイヤーの位置の石の色と同じ文字なら、プレイヤーは次の石に移る。
最終的にプレイヤーがいる位置を答える問題。

文字列長は50文字と短いので、そのままシミュレートすればよい。

void solve() {
	int f,r,i,j,k,l,cur,tar,ret,loop;
	char str[51],str2[51];
	
	GETs(str);
	GETs(str2);
	
	j=0;
	FOR(i,strlen(str2)) {
		if(str2[i]==str[j]) j++;
	}
	
	_P("%d\n",j+1);
	
	return;
}

B. Roadside Trees

一列に並んだN本の木の高さHiが与えられる。各木のてっぺんにはナッツがある。
最初プレイヤーは１本目の木の根元にいる。
時間１毎に、プレイヤーは木を上下に長さ１分移動するか、ナッツを取るか、次の木に移るのいずれかの処理を行える。
ただし、今の位置よりも次の木が低い場合は次の木には移れない。
全部のナッツを回収するまでにかかる時間を答える問題。

まず、ナッツを食べる時間Nと木の間の移動時間(N-1)は先にカウントしておこう。
後は、上下の移動時間だけ考えればよい。

一見「今の位置よりも次の木が低い場合は次の木には移れない」の条件が気になるが、実は木にすることはない。
今ある木のてっぺんにいるとき、次の木がより高い場合は先に次の木に移ってから上に上り、次の木が低い場合は先に木を下って次の木の高さに一致したら次の木に移ればよい。
どちらも上下移動にかかる時間はabs(H[i]-H[i+1])で同じである。

int N;
int H[100001];

void solve() {
	int f,r,i,j,k,l,cur,tar,ret,loop;
	int res;
	
	N=GETi();
	FOR(i,N) H[i]=GETi();
	res = N+(N-1)+H[0];
	FOR(i,N-1) res += abs(H[i]-H[i+1]);
	
	_P("%d\n",res);
	
	return;
}

まとめ

Bの問題、移動先は次の木だけだから簡単だけど、行ったり戻ったりできたらもう少し面白い問題になりそうね。
低い順に激しく横移動して回収するか、この問題の様に左から上下に移動して回収するかでアプローチが変わりそうだ。
…と思ったけど、頂点間の距離を求めてダイクストラするだけかな？