Ouroboros Snake (UVa Live Archive Europe - Mid Central - 2000/2001 Freiburg (Germany))

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2201

問題

どの場所からnの長さの数値を取り出してきても全て違う数値になっている2^nの長さの円順列をウロボロス数と呼ぶことにする。最小のウロボロス数のk番目の位置の数値をは何か？
0

解法

最小のウロボロス数は00...0から始まって1 << (n - 1)で終わる。これを構成するためには数値を1bit左へシフトして、一番右に0か1を入れることを繰り返せば良い。優先的に0を入れるが、0をいれた場合にすでに出現した数値になったら1を入れる。最後のn個は11111,11110,11100,11000,10000という風な形になることも考慮に入れて構築すれば正しい答えが出る。