Codeforces #287 Div2 C. Guess Your Way Out!

CF287に参加。
Div2回とは難易度が低めで何とか全完。
ただしD,Eで手間取ってだいぶ時間をくった。
http://codeforces.com/contest/507/problem/C

問題

高さH、葉ノード2^H個の完全二分木の形状を成す迷路がある。
この葉ノードを左から順に1～2^Hの番号をふる。
その時N番目のノードが迷路のゴールとなる。

プレイヤーの現在位置は根ノードである。
プレイヤーはそこから出口へ到達するため、、左の子・右の子を交互に選択し、子ノードに移動していく。
ただし特定条件では以下の通り動く。

• 移動先子ノードがすでに訪問済みなら、その子ノードへの移動は行わない。
• ２回連続子ノードに移動できない、すなわち左右両子ノードが訪問済みなら親ノードに戻る。
• 出口でない葉ノードに到達したら親ノードに戻る。
• 出口である葉ノードに到達したら迷路探索終了。

プレイヤーが出口に到達するまでに訪問するノード数を答えよ。

解法

ある高さhのノードにおいて、出口と逆方向のノードに移動してしまった場合、そこのサブツリーにある全ノード(2^h-1)個を訪問してこないと出口側のノードには移動してこない。

よって高さH～1の各高さhにおいて、逆方向のノードに行くかどうかを判定して(2^h-1)を加算していけば良い。
逆ノードに行くのは、右右や左左のように２回連続同じ方向の子ノードに移動しなければならない場合となる。

ll H,N;
ll tot;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>N;
	N--;
	l=0;
	for(i=H-1;i>=0;i--) {
		
		if(((N>>i)&1)!=l) {
			tot += (1LL<<(i+1))-1;
		}
		else {
			l^=1;
		}
		tot++;
	}
	
	cout<<tot<<endl;
}

まとめ

ちょっと迷ったけどシンプルで面白い問題。