CodeIQ 挑戦の記録 :「レッド・アンド・ホワイト」問題
CodeIQというサイトで問題に挑戦した記録です。
問題文を要約すると下記の通り
- マス目が直線上に限りなく並んでいる（初期状態は全て白色）
- このうちの1つを赤色に塗る。
- 次のルールに従いマス目の色を塗り替える時、n秒後の赤色のマス目の個数を解答する。
- 1秒ごとに下記の通り変化する
左右のマス目が白赤または赤白のマス目->赤色に塗る。
左右のマス目が白白または赤赤のマス目->白色に塗る。
方針
題意に従い、二次元配列を使って状態の変化を表示してみる。
赤色のマス目を「1」で、白色のマス目を空白で表示すると、パスカルの三角形に似た図形が表示される。
この図形は、パスカルの三角形の奇数部分を塗りつぶしてできる「シェルピンスキーのギャスケット」と同様のものである。
パスカルの三角形には様々な規則性が隠れているが、n行目（最初を0行目とする）に含まれる奇数の個数はnを2進法で表記した時の1の個数をとすると
に等しい事が知られている。
[パスカルの三角形と2進法]
http://www7b.biglobe.ne.jp/~fukagawa/documents/mod2pascal.pdf
実装
上記の性質を用いて解答する。(Ruby・27文字)
なお、標準入力からの数値を2進法で文字列化する時に、Rubyではsprintfが使えるが、これの代わりに「%」で書式文字列が使えるのでこれを利用して2進法表記の文字列とし、その中の1を数えている。
p 2**(("%b"%gets).count'1')
おまけ
上記の規則性に気づく前に提出した1回目の解法
この三角形は0行目が1が1個、1行目が1が2個の2行でなる三角形が2行ごとに2倍ずつ繰り返し現れ、
2のべき乗行目に2に戻る事を繰り返している。
これより、与えられた数をその数より小さい最大の2のべき乗で引いていき、その回数の2倍を解答とする。
n=gets.to_i;a=1;while n>0;a*=2;n-=2**Math.log2(n).floor;end;p a
では、
Sponsored Link
