ショートコーディング超入門
この記事はCompetitive Programming Advent Calendar 16日目の記事です。実際のプログラミングコンテストでショートコーディングすることはあまりないかもしれませんが、この記事でショートコーディングに興味を持つ人が増えればさいわいです。
ショートコーディングとは
ショートコーディングとは、プログラミングのソースコードを限られた環境の中で最短のものを目指すことです。1byteでも短いコードを書くために安全性を欠いたコードを書くこともあり競技プログラミングや仕事のプログラミングにはあまり役に立たないかもしれません。C言語(gcc)でのショートコーディング超入門
- Aizu Online Jadge(AOJ)で問題を解くことのできる短いコードを書いてみましょう。
Problem 1000：A + B Problem
整数を2つ読み込んでその和を出力しましょう。データセットは複数あり、入力の終わり(EOF)まで処理します。
普通にC言語で書いたら次のようになるでしょう。
#include<stdio.h> int main(){ int a, b; while( scanf("%d %d", &a, &b) != EOF ){ printf("%d\n", a + b); } return 0; }
C言語ではincludeやmain関数のreturnを省略してコードを短くします。AOJでreturn 0;を省略したコードを提出するとRuntime Errorになることがあるようです。eaxレジスタに0が記録された状態で終了すればRuntime Errorは出ないようです。Runtime Errorが出るときは大域変数に0を代入するなどの工夫が必要だそうです。私にはこのあたりがよく分からないので詳しい人に聞いてください。
またEOFまで処理するときは
while( scanf("%d %d", &a, &b) != EOF ){ ... }
の代わりにビット否定の演算子~(チルダ)を使い次のように書きます。
while( ~scanf("%d %d", &a, &b) ){ ... }
と書くことができます。
EOFは
int main(){ int a, b; while( ~scanf("%d %d", &a, &b) ){ printf("%d\n", a + b); } }
それなりに短くなりました。ショートコーディングでは変数を宣言するときや関数の戻り値の型intを省略します。
変数はmain関数の引数とすることが多いです。
main(){int a,b; ... }
のようにint型変数a,bを二つ使うときは
main(a,b){ ... }
のように書くことでセミコロンを削ることができます。
またループではwhile文の代わりにfor文を使いましょう。
while();とfor(;;);では文字数が同じなので行末のセミコロンを削ることができます。
for文のブロック{}も極力削るようにします。
for(;;){A;B;}
はカンマ演算子,を使い
for(;;)A,B;
のようにしましょう。(A,Bは式)
main(a,b){
for(;~scanf("%d %d",&a,&b);)
printf("%d\n",a+b);
}
とても短くなりました。最後に余分な改行やスペースを除いて完成です！
main(a,b){for(;~scanf("%d%d",&a,&b);printf("%d\n",a+b));}
これで57byteです。おそらくこの問題の最短コードでしょう。
その他のテクニック
配列に値を格納する
配列に値を格納するときは普通は次のようになるでしょうfor(i=0;i<n;i++)scanf("%d",&a[i]);
しかし&a[i]はa+iと書くことができるので次のように少し短く書けるでしょう。
for(i=0;i<n;i++)scanf("%d",a+i);
インクリメントi++の部分をscanfの中に書いてしまうことでさらにコードを短くできます。
for(i=0;i<n;)scanf("%d",a+i++);
変数iをグローバル変数で宣言していると0で初期化されているのでその場合にはi=0の部分も省略でき、さらに短いコードになるでしょう。
配列a[0]の値を使うときは*aと書いてコード削減
a[0]の代わりに間接参照演算子を使い*aと書くとコードを短くできます。指定回数のループ
n回のループは次のように書くのが普通だと思います。for(i=0;i<n;i++) ... ;
しかしforループの中で単純にn回ループしたいときは
for(;n--;) ... ;
と書くことで短くできます。
!=演算子は極力使わない
C言語では条件式は0のときfalse, それ以外の値のときtrueとして扱われるので、次のようなコードif( a != b ) ... ;
の代わりに
if( a - b ) ... ;
と書くことでコード1byteだけを短くできます。
条件分岐でif文は極力使わない
条件演算子:?を使うことでコードを短くすることができます。if(条件式)式1;else 式2;
は
(条件式)?式1:式2;
と書くことができます。条件式の中身によっては()を省略できることがあります。演算子の優先順位によるのでもし()が省略可能な場合は省略しましょう。式1や式2にfor文が入ってくるなど、単純な書き換えができない場合もあるので気をつけましょう。
文字リテラル
文字リテラルを書くときは'A'の代わりに65と、'B'のかわりに66と書きます。'A'は数値65なのでこのように書くことができます。このように書くと1byte削ることができます。他の文字についてはASCIIコード表を見ましょう。改行つきで文字列を出力するときputs関数が役に立つ
AOJの問題の中には"Yes"や"No"で答えを出力する問題があります。このように文字列のみを出力するときはprintf("Yes\n")と書くよりもputs("Yes")と書いた方がコードが短くなります。浮動小数を使うときはdouble型の代わりにfloat型を使う
doubleよりfloatの方が1文字短いので1byte短くすることができます。ただし精度が落ちるので誤差に気をつけましょう。誤差によりどうしても問題がAcceptできないときはdouble型のほうがよいこともあるかもしれません。他にもテクニックはたくさんありますが、ショートコーディングは極めるとキリがないので自分で追求してみましょう。
終わりに
参考書籍
「Short Coding -職人達の技法-」Ozy (著), やねうらお (監修)
ISBN-10: 4839925232
ISBN-13: 978-4839925239
「独習KMC vol.1」
京大マイコンクラブ (著)
「Short Coding -職人達の技法-」はショートコーダーのバイブルともいえる本です。ショートコーディングに興味を持った人は買ってみてはいかがでしょうか。
