ショートコーディング～神になりたい～【解説】

本稿はCodeIQで2013年4月26日～同年5月20日に出題された「ショートコーディング～神になりたい～」という問題の解法に関する記事です。

問題文はこちら

ショートコーディング～神になりたい～【解説】

◆注意

本問は「ショートコーディング」・「コードゴルフ」と呼ばれる、ソースコードをできるだけ短く書く遊びの一環として出題されたものですので、一般的なプログラミング解説とは少し異なります。

◆基本的な実装

入力をnとするとき、「2の倍数・3の倍数以外の数を小さいものからn個足す」という意味になりますので、そのまま実装すると以下のようになります。

#include <stdio.h>

int main()
{
  int n, k=1, sum=0;
  scanf("%d", &n);
  while( n>0 ) {
    if( k%2!=0 && k%3!=0 ) {
      sum += k;
      --n;
    }
    ++k;
  }
  printf("%d\n", sum);

  return 0;
}

素直な考え方ではありますが、倍数に関する問題ですから、規則性をよく理解し、直接合計値を得られるようにします。 1から順に、数を6つずつ区切って書いてみると、よくわかります。

2の倍数と3の倍数を消去すると、縦に並んだ2種類の数列が現れます。 これらは、初項が1と5で異なるだけで、6ずつ増加する（公差が6の等差数列である）という点は共通しています。 等差数列の和は、直接求める計算方法がありますから、for文やwhile文を用いなくても解を得ることができるのです。

2種類の数列を、さらに足し合わせます。

このようにすると、新たな数列は初項が6、公差が12の等差数列になり、m項まで和は

m*(6 + 12*m-6) / 2 = 6*m*m

となります。 mの値はn/2（nが奇数の場合は小数点以下切り捨て）になります。

したがって、元の数列のn項までの和は、

(1)nが偶数のとき

6*(n/2)*(n/2)
= 6*n*n/4
= 3*n*n/2

(2)nが奇数のとき

6*floor(n/2)*floor(n/2) + 6*floor(n/2) + 1

と計算することができます。

コードにすると、

#include <stdio.h>

int main()
{
  int m, n, sum=0;
  scanf("%d", &n);
  m=n/2;
  if(n%2==0) {
    sum = 6*m*m;
  } else {
    sum = 6*m*m + 6*m + 1;
  }
  printf("%d\n", sum);

  return 0;
}

のようになります。 ‘floor’という記述がありませんが、Cでは整数型同士の演算結果は整数型になりますので、n/2を計算すると小数点以下は切り捨てられることになります。 これでループ制御は必要なくなりましたが、コード自体は少し長くなったように見えます。 nが奇数の場合は、左右2つの数列AとBのうち、Aで終わることになりますので、Aの最後の項を得るための式が追加され、結構長くなってしまいました。 ここで(2)の式のfloor(n/2)という部分を、(n-1)/2のように書き換えてみます。 nが奇数なら、1を引いておくことで偶数になり、必ず割り切れるようになりますので、小数点以下を切り捨てた場合と同じ値になります。

6*{(n-1)/2}*{(n-1)/2} + 6*{(n-1)/2} + 1

この式を展開し整理すると、

3*n*n/2 - 1/2

となり、nが偶数の場合の式とほとんど同じになります。 後ろの項にある1/2は、整数同士の演算の場合0と等しくなりますので、実質は前の項の

3*n*n/2

だけでよくなり、nが偶数の場合の式と完全に一致します。 したがって、先程のコードは次のような非常にシンプルなものになります。

#include <stdio.h>

int main()
{
  int n, sum=0;
  scanf("%d", &n);
  sum = 3*n*n/2;
  printf("%d\n", sum);

  return 0;
}

◆ショートコーディングの基本テクニック

ここからは、ショートコーディングの基本テクニックに従ってコードを短縮します。基本テクニックについては、次の記事を参照してください。

ショートコーディング入門編解説1～中級の壁を突破するために

ショートコーディング入門編解説2～上級の壁を突破するために

上記の記事で解説されているテクニックの、ビルトイン関数・型名省略・return文省略を利用して、45バイトまで短縮することが可能です。

main(n){scanf("%d",&n);printf("%d",3*n*n/2);}

最初のコードと比べると、非常に短くなりました。これで最短コードのように見えるかもしれませんが、実はさらに短くすることができます。

◆vprintf関数

あまり馴染みがないかもしれませんが、標準出力に出力する関数として、vprintf関数があります。 printf関数は引数が可変長ですが、vprintfは、vprintf(書式, 引数のリスト)の形で使用します。 引数のリストはva_listという型ですが、互換性のないポインタを、警告無視で無理やり渡すこともできます。

#include <stdio.h>
//#include <stdarg.h>

int main()
{
  int n;
  scanf("%d", &n);
  n = 3*n*n/2;
  // va_start, va_endマクロも省略
  vprintf("%d", &n); // &nの部分は、本当はva_list型でないとダメ

  return 0;
}

このコードはideone.com上で動作し、正しい解が得られます。

◆処理系に依存しすぎるテクニック

処理系の依存度が非常に高く、どんな環境でも必ずうまくいく方法ではありませんが、このテクニックはショートコーディングではよく使われます。 先程のコードの、scanf関数とvprintf関数の引数部分をよく見てみると、全く同じ記述になっています。 そこで、scanf関数の後に呼び出されているvprintf関数の引数を、思い切って取り除いてしまいます。 当然コンパイルエラーになりますから、includeの部分をコメントアウトして、再びビルトイン関数を用いるテクニックを使用します。

// きちんとincludeすると引数チェックされるので、
// コメントアウトしておく。
//#include <stdio.h>
//#include <stdarg.h>

int main()
{
  int n;
  scanf("%d", &n);
  n = 3*n*n/2;
  // va_start, va_endマクロも省略
  vprintf(); // 引数を1つも書かないと…？

  return 0;
}

vprintf関数の引数を指定していないにもかかわらず、このコードはideone.com上で動作し、正しい解が得られます。 ideone.comのgccは32bit環境でコンパイルされます。その場合、関数が呼び出される際に、コールスタックに引数情報が置かれます。 通常は、引数を指定して関数を呼び出すとき、コンパイラが引数情報をコールスタックに置くアセンブリ命令を生成しますが、引数情報が全く同じ値で、コールスタックに引数情報がそのまま残っている場合、あえて引数指定を書かずにアセンブリ命令を省略するようにしておくと、引数を指定した場合と同じように動作してくれます。 これを利用することで、さらにコードの短縮が可能になります（64bit環境の場合、引数が少ない場合は、引数の受け渡しがレジスタ経由になり、関数呼び出し時にレジスタの値が書き換えられていると、再度呼び出すときに再びレジスタにデータをロードしなければなりません）。

※「コールスタック」を「レジスタ」と誤った用語を使用しておりましたので訂正し、少し補足しておきました。ご指摘くださった神級のAnomaly様、ありがとうございます。

main(n){scanf("%d",&n);n=3*n*n/2;vprintf();}

これで44バイトになりました。 変数nのアドレスから出力値を取る必要があるので、計算結果をnに代入しなければならず、そこが少し気になります。 そこで、次のように書きます。

main(n){scanf("%d",&n);n*=n*1.5;vprintf();}

1.5を掛けてしまうと実数値の計算になり、nが奇数の場合に正しい解になりませんが、変数n自体は整数型ですので、代入する際に小数点以下は切り捨てられます。 これで43バイト、最短コードのでき上がりです。