「 今週のお題：3進法だとどう変わる？」問題解答 ( CodeIQ )

CodeIQ

はじめに

CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。

codeiq.jp

問題

今回は次のような問題でした。

  • 整数の入力値 n に対し、0以上n以下の整数の中で、次の2通りの3進数表記いずれでも同じ表記になるものの個数を出力する
  • 2通りの3進数表記とは、1つは通常の3進数、各桁が 0,1,2 で構成される表記、もう1つは各桁が 0,1,T(=-1)で構成される表記。例えば10進数4はどちらでも 11 という表記になるが、8 はかたや 22、かたや 10T であり異なる。

解説

提出したのは次のRuby(61)でした。

m=gets.to_i+b=1
s=0
(s=3[r=m%3]*s+b*r;m/=3;b*=2)while m>0
p s

問題としては、入力nに対して 0以上n以下の数が対象ですが、+1したmを代わりに使い「0以上m未満」として処理します。

カウント対象となるのは結局、「3進数表記により2が現れない数」です。mがキレイに3のべき乗であれば、これは指数を同じくする2のべき乗になります。

ここで、求める答えを f(m) とし、例えば m を4ケタの3進数として上の桁から見ていった場合、

  • m=1xxx(3) の場合

    • 1000(3)未満 → 23 個
    • 1000(3)以上、1xxx(3)未満の4桁 → f(xxx(3))=f(m-33)個
    • 合計 f(m-33)+23個

  • m=2xxx(3) の場合

    • 1000(3)未満 → 23個
    • 1000(3)以上、2000(3)未満の数 → 1000(3)未満と同じく 23個
    • 2000(3)以上の範囲にはないため、下の桁xxxは関係なし
    • 合計 f(m)=23×2

と整理できます。

これで引数の桁を落としていっても良いのですが、逆に下の桁から見ていった場合、

  • 下からk桁目 ( 0開始 ) の数字が
    • 0,1 → 桁の数字×2k を加算
    • 2 → 今までの合計を破棄して、桁の数字(=2)×2kを加算

という計算ができます。こちらの方が、最上位の桁の位置を意識する必要がなくなるため実装が簡単になります。

(2016/4/8追記)

えちごやえちぜんさんから次のコードが。ループで3進数の桁を処理せずとも、文字列置換を行った後、2進数として変換すれば、というやり方です。

Rubyだと次のように。こちらの方がすっきりしますね。

p gets.to_i.to_s(3).sub(/2.*/){?1*$&.size}.to_i(2)+1

(追記終わり)

終わりに

うーむ。しかし ( 計算量が$O(log(n))$と$O(n)$の違いがあるとはいえ )、しえるさんのはすっきりして綺麗ですね。