気分転換に練習問題として，解いてみた．

生成される数列（文字列）が再帰的構造のようなものをもっている．

なので，再帰で書けばシンプル．

アルゴリズムは結構，すぐ思いついた．

しかし，C++は慣れてないので，時間かかったよ． 

string password(int n, long long k) {
if (n == 1) return k == 1? "0": "1";
long long q = 1 << --n;
if (k <= q) return "0" + password(n, k);
return "1" + max(pass(n, q), password(n, k - 1 - q));
}
string pass(int n, long long k) {
if (n == 1) return k == 1 ? "0": "1";
long long q = 1 << --n;
if (k <= q) return "0" + pass(n, k);
if (k == q + 1) return "1" + pass(n, q);
return "1" + pass(n, k - 1 - q);
}

教訓

  • Stringの比較（辞書式）は <,> 等で可能
  • Stringのconcatは + でできる．
  • 2 ^ n は 1 << n
  • 自分の環境でコンパイルが通っても，相手（TopCoder）の環境でコンパルが通るとは限らない！

しかし，Haskellで書けばもっと，アルゴリズムが見えるのになぁ．

なぜ，TopCoderではHaskellが使えないのか．小一時間，問い詰めたい． 

password :: Int -> Integer -> String
password 1 1 = "0"
password 1 2 = "1"
password n k | k <= q    = '0' : password (n - 1) k
| otherwise = '1' : max (ppart (n - 1) q) (password (n - 1) (k - 1 - q))
where q = 2 ^ (n - 1)
ppart :: Int -> Integer -> String
ppart 1 1 = "0"
ppart 1 2 = "1"
ppart n k | k <= q     = '0' : ppart (n - 1) k
| k == q + 1 = '1' : ppart (n - 1) q
| otherwise  = '1' : ppart (n - 1) (k - 1 - q)
where q = 2 ^ (n - 1)