最近、競技プログラミング系のことをあまりやっておらず、ちょうどAOJの問題を数問解いて、その後、golf的にいくつかコードを書き直したので、そのコード晒しを…
Code Golfとは
このブログ上でCode Golfについて触れる機会はなかったので、簡単に説明しておきますと、一般的なスポーツのゴルフのように少ない打数(コード量)で動作するプログラムを作成するものです。
本当に言い出したら、コンパイラ依存レベルのコードやらにもありえますが、私はまだそこまでのコードは書けないので、とりあえず小手先の手段でコード量を削ってます。
Code Golfについて詳しくは、このサイトさん(code golf入門/C言語編 – プログラミングスレまとめ in VIP)や以下の本を参照ください。
私はこのCode GolfをたまにAOJ(Aizu Online Judge)で行なっています。
AOJ(Aizu Online Judge)とは
AOJとは会津大学の方が運営されているオンラインジャッジシステムです。決められた問題セットがあり、それを満たすプログラムを作成する競技プログラミングをオンライン上で問題配布、正誤チェックをおこなってくれるシステムで、競技プログラミングの練習によく利用させてもらっています。
本来、Code Golfを行うためのサイトではありませんが、こちらのサイトは日本語の問題セットが多くあり、また私自身もCode Golfだけやっているわけではなく、競技プログラミングの練習のための利用が大半で、新しい問題を普通に解く→余裕があり気が乗ったらGolfをするといったやり方をしています。(とはいってもGolfメインのサイトではないのに、コード長上位のコードはとんでもなく短いという…)
今回は、比較的初歩的な問題である1041と1042をたまたま未回答だったのを見つけたので、golfしました。
AOJ1041 Kyudo: A Japanese Art of Archery
この問題は、単純に言えば１行目に入力された値/4回続く行の合計値を出力する問題です。
この問題についてgolfしたコードは以下に…
i,a;
main(n)
{
for(;scanf("%d",&n),n;a=!printf("%d\n",a))
for(;scanf("%d",&i),a+=i,n-=4;);
}
最初の行ではnが0ならば終了なのでscanfでnに代入した後、nを評価して0ならば偽なのでforを抜けて終了します。
そして2つめのfor文ではnを4ずつ減らして、n/4回の入力値の合計を計算させています。このとき、n=0になれば終了なので、for内で除算してそのまま評価しています。
これで、改行空白を除けば、87byteになりました。…が、この問題の最短解は2012/03/15現在、73btyeなのでまだまだ遠く及んでいません。
AOJ1042 Yes, I have a number
この問題は、入力された文を空白で区切り、それぞれの文字数を出力する問題です。
この問題についてgolfしたコードは以下です。
#include
c;
main(i)
{
char s[99];
for(;fgets(s,99,stdin),c=i=!strstr(s,"END OF INPUT");printf("%d\n",c-1))
for(;s[i];)
c=s[i++]-32?c+1:!printf("%d",c);
}
最初の行でfgetsで文を取得、strstrで終了条件の文か判定した後、空白までカウント、出力を繰り返しています。
このコードは、改行空白を除けば、156Byteです。…が、この問題の最短解は2012/03/15現在、97btyeなのでさらに遠く及んでいません。
今回は、小手先の手段ばかりで短縮しているので、正直なところこのコード自体もまだ削れそうですし、アルゴリズムそのものも改善の余地がありそうです。(特に後者の問題にかんしては、行ごと取るため、fgets→stdinのためにinclude文を利用等しているので、割と予知が残っていそうです)
今回は時間的な関係であまりこのコードだけにとっかかるわけにも行かなかったので、ひとまずここで一区切りで掲載しましたが、また後日改善を行いたいと思います。