AOJ 2190 天使の階段

AOJ 探索

東京大学プログラミングコンテスト2009(Problem F)
いつの間にかUTPC2009の問題が追加されていたようだ。

問題概要

音の出るn段の階段を、長さmの決められた旋律を演奏しながら降りることはできるか。（n,m≦50000）
階段の降り方は以下の３通り。

  • 1段降りる（T[i]の音が出る）
  • 2段降りる（T[i]+1の音が出る）
  • 1段上る（T[i]-1の音が出る）

試行錯誤

数字が大きいので動的計画法は難しそう。
とりあえず演奏の条件が結構厳しいので探索空間はそんなに広くないだろうと思って、探索部分を何の枝刈りもないDFSで書いてみる。
→TLE
あんまり上のほうでうろうろしてるとm歩で降りられなくなるので、その枝刈りをつけてみる。
→TLE
最初のほうだけメモ化してみる。
→TLE
setで全部メモ化してみる
→TLE（時間増えてるしｗ）
BFSで書いてみる
→TLE

解法

BFS+自明な枝刈り。


1段飛ばしで降りるのが最も早い。
よって残りを全部一段飛ばしで降りても降りられない位置にいたら枝刈り。

bool bfs()
{
	queue<pi> Q;
	Q.push(mp(0,0));
	while(!Q.empty())
	{
		int cur=Q.front().first,step=Q.front().second;
		Q.pop();
		
		//brunch cut
		if(n+1-cur>2*(m-step+1))continue;
		
		if(step==m)
		{
			if(cur+1==n+1||cur+2==n+1)return 1;
			continue;
		}
		
		//1段降りる、1段飛ばしで降りる、1段上がる
		if(cur+1<=n&&t[cur]==s[step])Q.push(mp(cur+1,step+1));
		if(cur+2<=n&&(t[cur+1]+1)%12==s[step])Q.push(mp(cur+2,step+1));
		if(cur-1>0&&(t[cur-2]+11)%12==s[step])Q.push(mp(cur-1,step+1));
	}
	return 0;
}

（探索部分のみ）


LayCurseさんのタイムありえない！
一体どんなコードなんだろう。