Computer Transformation(4) - カメヲラボ

Javaによる最短コード

前回導いた公式

$floor(\frac{2^{n-1}+1}{3})$

を使うと、多倍長でシフト演算・除算が出来るJavaではこのような非常に単純で短いコードを書くことが出来る。(namasuteさんhttp://d.hatena.ne.jp/namasute0/20060911#1157951574の日記より引用)

import java.util.*;
class Main{
  static{
    java.math.BigInteger a=null;
    for(Scanner s=new Scanner(System.in);a==a;)
      System.out.println(a.ONE.setBit(s.nextInt()-1).divide(a.valueOf(3)));
  }
}

例外を発生させてループを停止させる技も使って、さすがと言うしかない。
しかしショートコーダーたる者、感心してばかりではならない。多倍長クラスを持っているというだけで、いつまでもJava様万歳ではならない・・・。

Cで同じ実装してみる。

上記と同じアルゴリズムで実装してみる。この問題の厄介な部分は、インプットの回数が非常に多く、同じ値の入力も複数含まれているということ。入力毎の計算をしようと思えば、多倍長のシフト演算や高速な除算を考えなければならない。そこで、入力値の最大1000を越える入力までの解を計算しておく必要がある。

*p,v[2002][606];c;
main(i,j){
  for(;*v[1]=++i<2e3;++*v[i-1])
    for(p=v+i;p<v-~i;*p++%=10)*p=p[-606]*2+c,c=*p/10;
  for(;~scanf("%d",&i);c=puts(c?v:"0"))
    for(p=v-~i,j=*--p;p>=v+i;j=j%3*10+*--p)c+=j/3,c&&putchar(48+j/3);
}

3での除算を出力時に行ってもTLEにはならなかったので、多少は短く書くことが出来たが、これでも200バイト程度。さらに短縮できるとしても、Javaの179バイトには及びそうにない。数式では単純に書けたものの、乗算・除算を行うにはどうしても2回のループが必要になる。なんとかして演算回数を減らすことはできないものか。

つづく