SRM445 550 （練習）

TopCoder

気分転換に練習問題として，解いてみた．
生成される数列（文字列）が再帰的構造のようなものをもっている．
なので，再帰で書けばシンプル．
アルゴリズムは結構，すぐ思いついた．
しかし，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)