本稿はCodeIQで2013年5月23日～2013年6月17日に出題された「ショートコーディング：パスカルの△」という問題の解法に関する記事です。

ちゃんとコーディング【解説】

◆注意

本問は（CodeIQでの）通常のプログラミング問題よりも条件や採点基準を細かく厳しく設定しました。近年のプログラミングコンテストでは当たり前に近い条件かもしれませんが、当時はプログラミング自体が初めてだという参加者も多数いました。そのような背景を踏まえた上でご覧いただけるとありがたいです。言葉遣いが悪い部分もありますが、ほぼ現文ママにしておきます。

◆はじめに

こんにちは、Ozyです。普段は主にショートコーディングという特殊なプログラミングの遊びで出題していますが、何度か出題しているうちに思ったことが1つあります。

ちゃんと問題文読まんかい(｀Д´)ﾉ

CodeIQの中の人に言われました。

CodeIQではできるだけポジティブな文章を書くことを推奨しています。

そうそう、わかっておりますとも。でもね、これは単なる腕試しだから良いとして、実際就職しようとしているとか、仕事でプログラム書いたりするのに、最低限きちんとしておかないといけないこともあります。だから、今回はちょっと厳しくしました。具体的には、

余計な出力があるものはアウト

たとえば、「入力データは××です」みたいな文言が出力に含まれているもの。わかりやすく書いたのかもしれないけれども、指定と違う書式というのはダメです。

impossibleの綴りが違う！！

解けない問題の場合、"impossible"と出力するように指定しています。これが、"imposible"みたいに's'が1個足りないというような単純ミスも不正解扱いとしました。綴りに自信がなければ、問題本文からコピペしてください。

改行・空白文字

x = 2

と出力すべきところを、

x=2

と出力するとアウトです。何故かというと、問題本文に、空白を入れるように指定してあるからです。「え～、そのくらいエエやん！」と思うかもしれませんが、こういうルールも“ちゃんと”守って完璧なコードを書いた挑戦者（後述）がいるのです。

というわけで、まずはテストケースの簡単な解説をしておきます。

◆テストデータの解説

今回は、4つのテストケースを用意しました。

テストケース1

問題文の例と全く同じデータです。提出前にテストしていれば、これが不正解になることはないはずです。テストをする場合も、単に目視でのチェックではなくdiffコマンドを使う等、正確なチェックをしましょう。そうでしておかないと、たとえば"impossible"という単語の綴りが間違えていた場合の不正解や、書式の間違いを見逃すことになります。

テストケース2

テストケース1と大差はありませんが、符号のチェック・約分が甘いと不正解になるデータです。例のデータだけで安心せず、色々な場所に'-'を付けてみたり、乱数を使って自分で問題を作るなどして入念にチェックしておけば、このケースで不正解になることはないと思います。

テストケース3

テストケース3は、大きめの値が1000組与えられます。たとえば、

-355817016 -182909952 -64304280 -58588344

のようなもので、解は

x = -29/68

のように、約分すると分母・分子が比較的小さな値になるものです。ユークリッドの互除法を使って約分できていれば問題ないと思いますが、符号の取り扱いを適切に行わないと間違いやすいです。また、互除法を使わずに2, 3, ...と試し割していると、時間制限にかかる可能性が高くなります。注意しましょう。

テストケース4

最後のテストケースは3番目のものによく似ていますが、計算の過程で変数が符号付き32ビットを超えてしまう場合を含んだデータのセットです。問題本文には、

約分後の分母・分子の値も符号付き32bit整数の範囲で収まる

とありますから、『約分後の』という記述に注意できていれば間違うことはありませんが、『符号付き32bit整数の範囲』の部分しか見ていないと、計算途中で範囲を超えてしまうことに気付かないか、そのようなデータはあり得ないと思い込んでしまいがちです。

全データはこちらからダウンロードできるようにしておきますので、全問正解ではなかった方、今回参加しなかった方も良ければ確認してみてください。

◆解答例（C）

#include <stdio.h>

#define MAX(a,b) ( (a) > (b) ? (a) : (b) )
#define MIN(a,b) ( (a) < (b) ? (a) : (b) )

unsigned int gcd(unsigned int a, unsigned int b)
{
  if( b==0 ) return 1;
  unsigned int m = a % b;
  if( m == 0 ) return b;
  return gcd( b, m );
}

int main()
{
  int a, b, c, d;
  int n;
  
  scanf("%d",&n);
  for(int i=0; i<n; ++i){
    scanf("%d%d%d%d", &a, &b, &c, &d );
    if( a == c ){
      printf("impossible\n");
      continue;
    }
    
    if( b == d ){
      printf("x = 0\n");
      continue;
    }
    
    // 符号
    int plus;
    if( ( a > c && d > b ) || ( a < c && d < b ) ){
      plus = 1; // +
    }else{
      plus = 0; // -
    }
    
    unsigned int p = a > c ? a - c : c - a;
    unsigned int q = d > b ? d - b : b - d;
    unsigned u = gcd( MAX(p,q), MIN(p,q) );
    
    p /= u;
    q /= u;
    
    if( p == 1 ){
      printf(plus ? "x = %u\n" : "x = -%u\n", q );
    }else{
      printf(plus ? "x = %u/%u\n" : "x = -%u/%u\n", q, p );
    }
  }
  
  return 0;
}

◆ちゃんとコーダーの皆さん

上記のテストケースをすべてクリアした挑戦者は、25名でした。おめでとうございます！！

全問正解者(25/79名、敬称略)

naoya_t
hogeover30
ushsh
ciel
じゃい
ayuzak
thasodahn
okzk
mkiken
rotary-o
アライブライム
folsena
yukim
mamekin
climpet
kuuso
sch
pepshiso
hm001
minghai
YuukiARIA
そらまめ
debiru
Azicore
TheO

※提出の早い順に掲載しています。