「エース・ナンバー」問題解答 ( CodeIQ )
はじめに
CodeIQというところでプログラミング問題「エース・ナンバー」に解答しましたので、ネタバレです。
問題
Aだけで構成されたn桁の16進数をF(n)とした時、mod(F(n),106)を計算し、出力するというものです。nは標準入力より与えられます。
解説
数学的には
F(n)は、結局の所等比数列 ( 公比16 ) の和として計算することができます。16進数Aは、10進数で10の事ですから、
で終わりです。
コードとしては
とは言え、上記数式を素直に計算すると、大きな n に対しては値が大きすぎて話になりません。必要なのは 106 での剰余なのですから、その点を利用して如何にラクするか、ということになります。
素直な解
先に、÷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で同じ値を繰り返しますので、の代わりに を計算しているのですね ( 106/4は3125の倍数なので周期にはまっています )。Rubyの場合、整数の除算は余りの部分を切り捨てる形になりますので、-2 も不要です。
modを取らずにべき乗しているので、計算としてはムダが多いのですが、2の106乗位ならTLEせずに済むということで文字数を削った結果です。
ただし、n=106+1 等では ( n=1 と同じ値を計算しているので )、正しい解になりません。
周期 55 についてですが、の世界なので、と素因数毎に分解して考えることができます。そうすると、
- のため、nに関わらずmod 3の値は一定
- のため、n=0,1を除いてmod 26の値は一定
- のため、nに関わらずmod 5の値は一定、mod 56では周期55
ということで、結局 mod 56 の部分だけが効いて、周期55になります。ただし、mod 26 のことを考えると n=1 だけ例外となるので、ちゃんと正しい値を出すためには n=1 を場合分けする必要があります。( もっといい方法あるかな?? )
更なる短みへ ( 2015/10/23 追加 )
実は、最初考えていたRuby(35)よりも短いコードを教えてもらいました。
@riverplus 提出解(Haskell) https://t.co/AaDBjKJmVf と、golf解(Python2(標準ライブラリ関数使用)34b) https://t.co/ASXlLD09je ←Python3では動作しません
— あんちもん2 (@antimon2) October 23, 2015
Pythonのpow()は、上で挙げたPerlのbmodpow同様、冪剰余の機能を持っているのですね。なので34という短さを実現できます。
更に…。
@angel_p_57 @cielavenir ちなみにテストケースだけ通れば良い答案ならRuby32b見付けています。
— あんちもん2 (@antimon2) October 23, 2015
なんという事でしょう。寝ぼけてないバージョンのRuby(33)よりも短い解があったとは!! 新しい宿題が増えてしまったかのよう。
…それで考えてみました、Ruby(32)。多分、こういうのじゃないでしょうか。
p (2<<gets.to_i%78125*4)/3%10**6
を計算するものです。57 は55=3125の倍数になってますから、やはり周期にちゃんとはまります。そうすると、n=57, 57+1 等では正しい値にならないのですが、テストケースにあった 106 なんかはパスできることになります。( mod(106,57)は0にならないことに注意!! )
( 2015/10/23: 更に追加 ) イイ線行っていたのですが、まだちょっと甘かったようです。答え合わせはこちら。
@antimon2 @riverplus あ…。5のべきに拘っていましたが、3125×3=9375 あたりで良いんですね。テストケース良く覚えていないので、9375×k (+1) があったかどうか、ですが、3125×7 or 11 or 13 とか代わりは ありそうですね。
— angel-p57 (@angel_p_57) October 23, 2015
つまり、78125の代わりに何を使うか、ですね。3125の倍数、かつ、入力 n、もしくは n-1 の約数にならない数を見繕ってあげれば十分という事です。( なぜならば、n≦1 の部分が周期から外れているので、mod を計算して 0,1 になるケースだけが困るからです )
最後に
毎度恒例ながら、様々な人の解がtogetterでまとめられる予定のはずなので、そちらもご覧になってみては。 (2015/10/24 追記) CodeIQ「エース・ナンバー」問題 みんなのコード - Togetterまとめ にまとめられました。