SRM445 550 (練習)

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

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

なので,再帰で書けばシンプル.

アルゴリズムは結構,すぐ思いついた.

しかし,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)