読者です 読者をやめる 読者になる 読者になる

CodeIQ Blog

自分の実力を知りたいITエンジニア向けの、実務スキル評価サービス「CodeIQ(コードアイキュー)」の公式ブログです。

C言語によるショートコーディング入門編解説その1〜中級の壁を突破するために

問題解説

CodeIQ中の人、millionsmileです。

Ozyさん出題のC言語によるショートコーディング入門編が無事に終わりました!

途中の暫定順位では、「中級の壁」「上級の壁」を設置しておりましたが、
ここでは「中級の壁」を突破するコツやヒントを出題者のOzyさんよりいただいていますので、今後の参考にしてください!

https://codeiq.jp/ace/ozy4dm/q246
f:id:codeiq:20130408150456p:plain

ーーーここから出題者Ozyさんによる「中級の壁」突破の解説記事ですーーー

ショートコーディング入門編にご参加いただいたみなさん、ありがとうございました。出題者のOzyです。また、ご参加いただいていない方も、「こういう遊びがあるのかー」と、一度ご覧いただけると嬉しいです。

中級の壁を突破するために

今回は、簡単な連立方程式を解く問題でした。扱うのは整数値で、解がない場合や無数にある場合は含んでいませんでしたので、それほど難しい問題ではなかったと思います。
まずは普通に書いてみましょう。

#include<stdio.h>
 
int main()
{
  int a,b,c,d,e,f,x,y;
  int n;
  int i;
 
  scanf("%d¥n", &n);
  for(i=0; i<n; ++i)
  {
    scanf("%d %d %d¥n", &a, &b, &e);
    scanf("%d %d %d¥n", &c, &d, &f);
 
/*
|a b||x| = |e|
|c d||y|   |f|
 
1/(ad-bc) | d -b||e|
          |-c  a||f|
*/
    x = (d*e-b*f)/(a*d-b*c);
    y = (a*f-c*e)/(a*d-b*c);
 
    printf("%d %d¥n", x, y);
  }
 
  return 0;
}

ビルトイン関数

gccでは、printfやscanfはビルトイン関数として定義されています。
http://gcc.gnu.org/onlinedocs/gcc-4.7.2/gcc/Other-Builtins.html#Other-Builtins
ですので、stdio.hのインクルードは省略することができます(もちろん警告は出ますが)。

型名の省略とmain関数

gccではグローバル変数・関数の型名を省略すると、自動的にint型として扱われます(もちろん警告は出ますが)。int型を使うのであれば、グローバル変数として使う方が有利な場合があります。


また、引数の型も省略することができますから、main関数の引数として宣言しておくこともできます。ただし、省略する場合はすべて省略しなければエラーになります。

main(a,b){} // ok
main(a,float b){} // error

main関数は

int main(void)

int main(int argc, char *argv[])

と等価である必要がある…ということになっていますが、実際はmainというシンボルさえ定義されていれば実行プログラムは生成されますので、

main(a,b,c,e,d,f){}

みたいなコードでもコンパイルされます。

returnの省略

関数の型名を省略するとint型とみなされますから、何らかの整数値をreturnしなければなりませんが、これも省略できます。省略した場合は、実行時にレジスタに残った何らかの値が返ることになります。これを利用したテクニックもありますが、今回は利用しません。

軽く短縮

main(a,b,c,d,e,f,n,i)
{
  scanf("%d",&n);
  for(i=0;i<n;++i)
  {
    scanf("%d%d%d%d%d%d",&a,&b,&e,&c,&d,&f);
    printf("%d %d¥n",(d*e-b*f)/(a*d-b*c),(a*f-c*e)/(a*d-b*c));
  }
}

色々と省略できる部分を削ってみました。scanf関数の書式にあったスペースや改行を省略しても、値を読み込むとき自動的に読み飛ばしてくれるので問題ありません。printfの引数に計算式を入れてしまっていますが、これには注意が必要です(後述します)。

上記のコードの、空白や改行を取り除くと154バイトあります。これをベースに短縮していきましょう。

危険なgetsとEOF

テストデータは、最初の行がデータセットの個数になっているのですが、scanfで最後までデータを読み込んでいけば、最終的にEOFにたどり着きます。

つまり、最初の行は読み飛ばし、あとはEOFに達するまでscanfを繰り返せばよいのです。

main()
{
  scanf("%*d");
  for(;scanf(...)!=EOF;)
  {
    ...
  }
}

最初のscanfをgetsに置き換えるとさらに短くなります。gets関数は引数にバッファのポインタを渡さなければなりません。適当な変数を使って、

gets(&k)

のように書くことで、やり過ごすことができますが、もう少し短くするために、main関数の第2引数を使います。

main(a,v)
{
  gets(v);
}

型名を省略することで、vはint型なのですが、その値はargvのアドレスが入っていますので、これをバッファとして使ってしまいます。あるいはgets()みたいに引数自体を省略してしまえば、どこかのアドレスに値が読み込まれることになり、そのアドレスにメモリ保護がかかっていなければ、それで切り抜けられる場合もありますが、大体メモリ違反で落ちます。今回は、最初に呼び出す関数で引数省略すると落ちるので、負荷としておきました。

というわけで、こんな風に書いてみます。

main(n,v)
{
  gets(v);
  for(;scanf(...)!=EOF;)
  {
    ...
  }
}

第1引数は適当に使えば良いし、第2引数自体も最初のgetsで使うだけですので後で使いまわしができ、無駄にはなりません。しかしこのコードでは問題が出てきます。EOFというのはマクロで、これを使うにはstdio.hをインクルードしなければなりません。
EOFを避けるには、EOFの定義を事前に調べておきます。多くの場合(必ずではありません)は-1になっていて、今回のテスト環境では-1になっていました。つまり、ループを抜ける判定には

  for(;scanf(...)!=EOF;)

の代わりに

  for(;scanf(...)!=-1;)

とすることができます。また、cではtrue/falseを整数値で表すと、非0/0となりますので、

  for(;scanf(...)+1;)

と書くと、scanfの戻り値が-1の場合だけ-1+1=0になって、ループを抜けることができます。さらに、-1は2進表記するとすべてのビットが1になっているので、'~'演算子を用いてビット反転してしまえば、0になります。つまり、

  for(;~scanf(...);)

のように書くのが最も短い書き方ということになります。

main(a,b,c,d,e,f)
{
  for(gets(b);~scanf("%d%d%d%d%d%d",&a,&b,&e,&c,&d,&f);)
    printf("%d %d¥n",(d*e-b*f)/(a*d-b*c),(a*f-c*e)/(a*d-b*c));
}

ループ内がprintfだけになり、{}も省略できました。さらに不必要な変数も減り、かなり短くなりました。これで131バイトですが、まだまだ縮めることができます。たとえば、a*d-b*cは2か所出てきていますから、もう一つ変数を用意して、一度計算したものを保持しておけば、130バイトを切ることができますね。

これくらいまで短縮できれば、中級ゴルファーの仲間入りです。ちなみに、今回は中級のボーダーを150バイトに設定していました。

ーーーここまでーーー
さぁ、どうでしたか?奥深いですね。
次は「上級の壁」を突破するためのコツを書きます。

f:id:codeiq:20130405145145j:plain