「エース・ナンバー」問題解答 ( CodeIQ )

はじめに

CodeIQというところでプログラミング問題「エース・ナンバー」に解答しましたので、ネタバレです。

問題

Aだけで構成されたn桁の16進数をF(n)とした時、mod(F(n),106)を計算し、出力するというものです。nは標準入力より与えられます。

解説

数学的には

F(n)は、結局の所等比数列 ( 公比16 ) の和として計算することができます。16進数Aは、10進数で10の事ですから、
 F(n)=10\times\frac{16^n-1}{16-1}=(2\times 16^n-2)/3
で終わりです。

コードとしては

とは言え、上記数式を素直に計算すると、大きな n に対しては値が大きすぎて話になりません。必要なのは 106 での剰余なのですから、その点を利用して如何にラクするか、ということになります。

素直な解

先に、÷3 の分数の形になっている点を扱いやすくするため、
 mod(F(n),10^6)=mod((2\times 16^n-2)/3,10^6)=mod(2^{4n+1},3\times 10^6)/3
としておきましょうか。ついでに16のべき乗を2のべき乗に替えています。

これの実装例が以下のPerl(44)です。

use bigint;print+(-2+bmodpow{2}4*<>+1,3e6)/3

別に任意精度にしなくても収まる範囲での計算なのですが、そのものズバリな機能を持つbmodpowのため、bigintを使っています。

golf解

正しい解が出ない場合があることに目を瞑れば ( 用意されているテストケースは通る )、べき乗とmodにおける周期性を利用して、もっと短くできます。以下、Ruby(33)です。( 2015/10/23 修正: 当初35文字と思っていましたが、ちょっと寝ぼけてましたね )

#$><<(32<<4*~-gets.to_i%h=10**6)/3%h
p (32<<4*~-gets.to_i%h=10**6)/3%h

見易くすると次のような感じに。( 2015/10/23 修正: 結果的には変わらないものの、ちょっと嘘がありました )

n=gets.to_i
h1=10**6
h2=h1/4
puts 32*2**((n-1)%h2*4)/3%h1

はい。実はnが2以上では、解が周期55=3125で同じ値を繰り返しますので、F(n)=(2\times 16^n-2)/3の代わりに32\times 16^{mod(n-1,10^6/4)}/3 を計算しているのですね ( 106/4は3125の倍数なので周期にはまっています )。Rubyの場合、整数の除算は余りの部分を切り捨てる形になりますので、-2 も不要です。
modを取らずにべき乗しているので、計算としてはムダが多いのですが、2の106乗位ならTLEせずに済むということで文字数を削った結果です。 ただし、n=106+1 等では ( n=1 と同じ値を計算しているので )、正しい解になりません。

周期 55 についてですが、 mod 3\times 10^6の世界なので、 mod 3, mod 2^6, mod 5^6と素因数毎に分解して考えることができます。そうすると、

  • 16\equiv 1\, mod 3のため、nに関わらずmod 3の値は一定
  • 2\times 16^n \equiv 0 \,mod 2^6\, \left( n\geq 2 \right)のため、n=0,1を除いてmod 26の値は一定
  • 16\equiv 1\, mod 5のため、nに関わらずmod 5の値は一定、mod 56では周期55

ということで、結局 mod 56 の部分だけが効いて、周期55になります。ただし、mod 26 のことを考えると n=1 だけ例外となるので、ちゃんと正しい値を出すためには n=1 を場合分けする必要があります。( もっといい方法あるかな?? )

更なる短みへ ( 2015/10/23 追加 )

実は、最初考えていたRuby(35)よりも短いコードを教えてもらいました。

Pythonのpow()は、上で挙げたPerlのbmodpow同様、冪剰余の機能を持っているのですね。なので34という短さを実現できます。
更に…。

なんという事でしょう。寝ぼけてないバージョンのRuby(33)よりも短い解があったとは!! 新しい宿題が増えてしまったかのよう。

…それで考えてみました、Ruby(32)。多分、こういうのじゃないでしょうか。

p (2<<gets.to_i%78125*4)/3%10**6

 mod(2\times 16^{mod(n,5^7)}/3,10^6) を計算するものです。57 は55=3125の倍数になってますから、やはり周期にちゃんとはまります。そうすると、n=57, 57+1 等では正しい値にならないのですが、テストケースにあった 106 なんかはパスできることになります。( mod(106,57)は0にならないことに注意!! )

( 2015/10/23: 更に追加 ) イイ線行っていたのですが、まだちょっと甘かったようです。答え合わせはこちら。

つまり、78125の代わりに何を使うか、ですね。3125の倍数、かつ、入力 n、もしくは n-1 の約数にならない数を見繕ってあげれば十分という事です。( なぜならば、n≦1 の部分が周期から外れているので、mod を計算して 0,1 になるケースだけが困るからです )

最後に

毎度恒例ながら、様々な人の解がtogetterでまとめられる予定のはずなので、そちらもご覧になってみては。 (2015/10/24 追記) CodeIQ「エース・ナンバー」問題 みんなのコード - Togetterまとめ にまとめられました。