はじめに
この春4月20日（木）～5月21日（日）にpaizaさんで開催された10万登録ありがとうスペシャルＷキャンペーンがゴルフ会場として一部で盛り上がりました。ゴルフ大会は無事閉幕したようなのですが、二次会としてコード晒し会が開催されているようですので、私も参加してみたいと思います。
提出コード
まずこちらが私の提出コードです。申し訳程度にインデントしてあります。空白を削れば数字は合うはずです。
Java: 375バイト
class Main{
public static void main(String[]Q)throws Exception{
byte[]f;
int a,t=1,s[]=new int[System.in.read(f=new byte[8820])*6],I=0,i=0,j,k,m;
for(;t>0;a=t>47?s[I]=s[I]*10+t-48:I++)t=f[i++];
for(Q=new String[m=s[0]],java.util.Arrays.sort(s,m+=i=2,m+s[1]);i<m;Q[i++-2]=a+"")
for(a=I,j=k=0;j<5;
k=k<91
? 0>t?k+1:t<a?a=t:I
: ++j)
t=s[m+k]*s[m+j]-s[i];
System.out.print("".join("\n",Q));
}
}
C#:285バイト
using System;
class X{
static void Main(){
int i=2,a,t=1,I=0,k,m,j;
var x="";
var s=new int[3006];
for(;t>0;a=t>47?s[I]=s[I]*10+t-48:I++)t=Console.Read();
for(Array.Sort(s,m=s[0]+2,s[1]);i<m;++i,x+=a+"\n")
for(a=I,k=j=0;j<5;
k=k<91
? 0>t?k+1:t<a?a=t:I
: ++j)
t=s[m+k]*s[m+j]-s[i];
Console.Write(x);
}
}
解説
今回の大会では「実行時間が短い方が勝ち」「実行時間が同じならバイト数が短い方が勝ち」「実行時間は0.01秒単位でしか測らない」という条件でした。実行時間をどう計っているのか謎なのですが、Javaなら平均実行時間0.07秒、C#なら平均実行時間0.01秒が最短です。この制限時間を守れる範囲内でコードをとっかえひっかえしながらコードを短くしていくのが今回の問題の醍醐味です。
今回の問題は大別すると
- 入力
- 探索アルゴリズム
- 出力
の３つに分解できるでしょう。荒くですが、それぞれ解説していきます。
入力
Java/C#とも行儀の良い方法を使うとプログラムが長くなる上に遅いです。そこで、プリミティブなものだけを使ってがんばることで、短く速いコードになりました。
Java/C#とも、やっていることは次のコードを短くしたものです。
for(;;) {
t = Console.Read(); // Java版では配列fから読む
if (t <= 0) { // Java版はt==0で脱出、C#版はt==-1で脱出
break;
} else if (t >= '0') {
s[I] = s[I] * 10 + t - '0';
} else {
// 空白・改行のときここに来る。空白・改行とも 0 < t < '0' の範囲内にある
++I;
}
}
JavaはSystem.in.read()で1バイトずつ読んでいくと実行時間が足りなくなります。そこでSystem.in.read(byte[])で一気に読んで、その後数値の配列に変換しました。入力用のバッファは8820バイト確保していますが、これは最大の入力が8819バイトであるためです。Javaの配列の初期化されていない要素は0であることを利用し、0に到達したらループを脱出するようなコードになっています。
C#のConsole.Read()は遅くなかったので、そのままです。
探索アルゴリズム
疑似コードになりますが、探索アルゴリズムはJava,C#共通で以下のような感じです。
int []s = 商品の個数;
int []p = 材料を短い方から順にソートしたもの;
for(int i = 0; i < 箱の個数; ++i) {
int min = 大きな数;
for(int j = 0; j < 5; ++j) {
for(int k = j; k < 91; ++k) {
long t = p[j] * p[k] - s[i];
if (0 <= t) {
if (t < min) min = t;
break;
}
}
}
output(min);
}
要は、材料で九九の表を作り、一行ずつ対角線位置から右に向かって順に調べていくやり方です。
疑似コード中の「大きな数」ですが、お作法的にはLong.MAX_VALUE等を入れるのがスジだと思います。ですがこれはゴルフ大会です。なんかテキトーな大きい数で良いでしょう。私の提出コードではIに「読み込んだ数の個数」が入っていたので、使ってみたところ、何故か通りました。
速度を稼ぐ鍵は5と91です。この数ですが「やってみたらできちゃった」というやつです。九九の表の左上の「5×91」の範囲内を調べるだけでテストに通ります1。なんか小さい数字なので超速いと思います。石を投げないでください。
ところでJavaの提出コードの s[]=new int[System.in.read(f=new byte[8820])*6] の部分ですが、これも91に関わりがあります。System.in.read(byte[])は読み込んだバイト数を返すのですが、Test case 1では16,17,18のいずれかが返されます（特定はしていません）。s[]は少なくとも91個の要素が必要ですので、*6する必要がありました。
出力
商品一種毎にSystem.out.println/Console.WriteLineで出力していると、実行時間が足りません。そこで出力したい文字列を連結してSystem.out.print/Console.Writeで一気に出力します。しかし文字列の連結もそれはそれで遅いので、何かしら考える必要があります。
C#の文字列の連結は簡単でした。+=で速度が足りてしまいました。
Javaの文字列の連結は+=では速度が足りません。文字列を連結していきたい場合StringBufferを使うのが常道ですが2文字数が多く嫌です。そこでJava1.8で追加されたモダンなメソッドString.joinを選びました。「改行をはさみつつ連結」がメソッドひとつでできる上にmainの引数を活用できる一石二鳥のメソッドです。
ところでString.join("\n",X)で連結すると末尾に改行文字を追加してくれません。paizaの問題文に「最後は改行し、余計な文字、空行を含んではいけません。」とありますので対策する必要があると思います…が、これは嘘です。最後の改行はなくても通ります。String.joinの後に改行を追加する必要はありません。
感想
コードゴルフ大会に参加したのはこれが初めてですがとても楽しかったです。速度とコード量の微妙なバランスを取るのがゲームとして面白かったと思います。
JavaとC#の微妙な違いに気付けたのも個人的には収穫だったかなと思います。最終的にはJavaとC#でほぼ同じコードになってしまいましたが、書いている途中は結構違うコードでした。
テストケースの穴を探すような方針になってしまったのはアレかなとも思うのですが、JavaもC#もヘンなコードを書き辛い言語なので、これぐらいしかすることがなく、まぁ、うーん…。