ShortCodingしましょうか！
この記事はCompetitive Programming Advent Calendarの１７日目の記事としてかかれています。
ShortCode 特にCのShortCodingの入門的なことをを書こうと思ったのですが、色々既出だったんで本記事ではちょっと入り込んだことを書こうと思います。
shortcodingとは
shortcodingは１６日目の記事を見た方はご存知でしょうが、平たく言うと、できるだけ短いバイト数で条件にあったコードを書くことです。またこの記事は１６日目の記事をひと通り読んだ前提で進ませて頂きます。競技プログラミングのアドベントカレンダーということで本記事では有名なアルゴリズムをできるだけ短く書いていきたいと思います。
なおアルゴリズムはWikipedia_アルゴリズムから選んでおります
ソートアルゴリズム
うれしいことに標準ライブラリにqsortという関数がございます。標準ライブラリなのでincludeしなくても使えます。クイックソートですので早めのソートです。 あらゆるアルゴリズムがソートから始まったりします。
しかし残念なことにqsortは第４引数としてcompareの関数が必要です。これをいかに短く定義するかがミソになってきます。
普通なら
int compare_int(const void *a, const void *b) {return *(int*)a - *(int*)b;}
こんな感じになるでしょう（実際にはaが著しく小さくbが著しく大きいなどの場合にオーバフローを起こす脆弱性があります）。
とりあえずreturn文は冗長すぎるので、グローバル変数への代入で済ませる。また、引数の型はint*でも正常に機能するので、型変更。
ついでに関数名縮小
d;c(int*a,int*b) {d=*a-*b;}
ビッグエンディアンだったら第二引数が第一引数のそばにあるはずなので 引数を省略し、ポインタでアクセス。
ポインタ(a)のポインタ(&a)の隣のポインタ(&a+1)の指す場所に格納されているポインタ(*(&a+1))の指す場所(**(&a+1))に格納されているのが*b。
d;c(int*a) {d=*a-**(&a+1);}
x[y]と*(x+y)は同値ということを利用して、**(&a+1)は*(*(1+&a))は*1[&a]
d;c(int*a) {d=*a-*1[&a];}
これが環境に依存しない最短コード。環境に依存するとqsort(a,b,c,"YXZQQQ\x8b\0+\x02\xc3")とかアセンブる。
またdというグローバル変数を必要とするが他の用途があればそれと兼用すればある意味byte数の節約になる。
素数判定
素数判定は基本的に自分以下の数字の剰余をとりまくる。
下コードではxの判定をする。
今回は素数判定だけなので結果を出力して終わっているが、実践ではそこに任意のコードを書いて利用することができる。
for(a=1;x%++a;); x-a?puts("素数"):puts("合成数");
1を代入するのが難点ではあるがa=scanf("%d",&x);などで節約することができたりする。
しかしこれではｘが大きすぎると対応できない。
aをsqrt(x)まで判定するとすると。
for(a=1,b=sqrt(x);x%++a&a<=b;); a>b?puts("素数"):puts("合成数");
bという変数を新しく作らないといけないのが面倒ですが、これがおそらく最短でしょう。
追記： よく考えたら a*a<=xで充分だった。こっちのほうが短い。
for(a=1;x%++a&a*a<=x;); a*a>x?puts("素数"):puts("合成数");
ご指摘ありがとうございました。
動的計画法
二次元配列を取ったり、多重のfor文で囲んだりと割りと難易度の高いアルゴリズム。JOI予選第４、５問目レベルの問題で必要となるアルゴリズム。
動的計画法の代表といえるナップサック問題をShortCodeしてみる。
価値vと体積wを複数個とり、体積がW以下の中で価値を最大にする。(v>0)
t[9999],W,i;main(v,w){ for(scanf("%d",&W);~scanf("%d%d",&v,&w);) for(i=W;i-w;t[i]=fmax(t[i--],t[i-w]+v)); i=!printf("%d",t[W]); }
配列を最利用することで１次元にしている。9999の部分にはWの最大値が入ります。
またfmaxという最大値を返す関数があるのでそれを利用しています。
for(a;b;c)for(d;e;f)g;はfが常に真であるかぎり
for(a;e?g,f:(c,d,b););と同値です
上のコードの二重for文ではc,gに当たる部分が無いのでコンマ2個分減ります。
t[9999],W,i;main(v,w){ for(scanf("%d",&W);i-w?t[i]=fmax(t[i--],t[i-w]+v):(,~scanf("%d%d",&v,&w),i=W);); i=!printf("%d",t[W]); }
これが最短でしょう。
ちなみにウンチクですが、しばしばShortCode競技の場として使われるPKUですがmain関数がreturnする値が１でもRuntimeErrorにならないので、最後の
i=!printf("%d",t[W]);
の部分の！演算子を外せます。
