CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第87回「3進法だとどう変わる？」

CodeIQというサイトで問題に挑戦した記録です。

codeiq.jp

問題文を要約すると下記の通り、

• 3進法を2通りの方法で表現する
  {0,1,2}の3つの数字で表現する場合
  {-1,0,1}の3つの数字で表現する場合
• 標準入力より整数nが与えられる。
  0からnまでの整数のうち、上記のいずれの表現でも全ての桁が全く同じになるものの個数を解答する。

方針

-1を使って3進法を表現する時、上位桁に1を立てて-1を使って2を表現する。つまり-1と2は完全に対応する事になる。
2を使用しない数値はいずれの表現でも全ての桁が同じになるので、2を使用しない数値の個数を数えれば良い。

3進法でk桁目に2がでる数値を10進法で表すと、その数値をで割った余りがの2倍以上の時である。
これを用いて、からまでの数値全てに対して、どの桁にもが含まれないものの個数を数えて解答とする。

なお、この方法では計算量はとなると思われる。
数学的に、包除原理を用いればで計算できると思って考えていたが、重複を差し引く良い方法が思いつかなかったので、実行時間制限をクリアできない事を覚悟で上記の方法で提出した。
幸い想定より入力が小さかったのでTLEにならず正解をもらえたが、全探索のコードを提出していては、自分としては負けた気がしている。

提出したコード(Ruby)

では、

Sponsored Link