等比？ 等差？ フィボナッチ？？ の解題解説

概要とか

「等比？ 等差？ フィボナッチ？？」という問題が先日締め切られました。
挑戦者数が多い割に正答率が低く、初回投稿の正解率 10% 以下 という状況でした。 間違ってしまった方のために、何がまずかったのか、どうすればよかったのかをコードを交えて解説させていただきたいと思います。

問題の方は、5要素の数列が

• 等比数列
• 等差数列
• フィボナッチ数列の一部
• 上記以外

のどれに該当するのかを答えるだけというシンプルなものでした。入力となる数は、1〜100億の整数で、昇順に整列済みです。

実際のテストケースは以下の通りでした：

罠・方針・実装(有理数クラスの利用)

テストケースの 11番 と 12番 は、等比数列ではないものの、隣接項の比を倍精度(double)で計算すると、全て「0.6180339887498949」になります。もう少し桁数を多くすると、「0.61803398874989485, 0.6180339887498948475, 0.6180339887498948485, 0.6180339887498948481」などとなり、等比数列ではないことが分かるんですが、double では表現できない桁で違いが発生しています。
5番や9番も double で計算すると、等比数列と判断されるでしょう。
つまり、double 程度の桁数では等比数列かそうでないのかは判断できないということです。
そもそも。浮動小数点数は、許容誤差がある世界で使うべき型です。許容誤差が全くないこの問題のようなケースでは浮動小数点数を使うべきではありません。

ではどうするか。
ruby のような、多倍長整数を使った有理数が利用可能な処理系であれば、有理数を使うのが良いでしょう。
フィボナッチ数については、 cia_rana 様の記事 のような計算をするとより美しいと思いますが、もっと平易で非効率的な実装でも何の問題もありません。

というわけで、まずは ruby による実装をお見せしましょう：

def is_g(nums)
  nums.each_cons(2).map{ |x,y| x.to_r/y }.uniq.size==1
end

def is_a(nums)
  nums.each_cons(2).map{ |x,y| y-x }.uniq.size==1
end

def is_f(nums)
  fibs = [ 0, 1, 1, 2, 3 ]
  while fibs[0]<nums[0] do
    fibs = fibs[1,4]+[fibs[-1]+fibs[-2]]
  end
  return fibs==nums
end

def solve(src)
  nums = src.split(/\s+/).map(&:to_i)
  return "G" if is_g(nums)
  return "A" if is_a(nums)
  return "F" if is_f(nums)
  return "x"
end

puts solve(gets)

Rational クラスのお陰で非常に楽に実装できます。

方針と実装(有理数クラスがない場合)

一方。C言語のような有理数がない処理系の場合、必要最小限の有理数を実装するのが良いでしょう。
挑戦頂いた方の中には

a, b, c が等比数列 ⇔ a×c=b×b

というわけで。
少々長くなりますが、必要最小限の有理数を使った、C言語の実装をお見せしましょう：

// clang -std=c99 -Wall
#include <stdio.h>
#include <stdbool.h>
#include <stdint.h>

/// 等差数列なら true を返す
bool is_a( int64_t const * nums )
{
  int64_t diff0=nums[1]-nums[0];
  for( int i=1 ; i<4 ; ++i ){
    int64_t diff = nums[i+1]-nums[i];
    if ( diff != diff0 ){
      return false;
    }
  }
  return true;
}

/// 分子(n) と分母(d) のペア
struct pair{ int64_t n, d; };

/// n と d の最大公約数
int64_t gcd(int64_t n, int64_t d)
{
  while ( n != 0 ) {
     int64_t c=n;
     n = d % n;
     d = c;
  }
  return d;
}

/// n を d で割り、約分した結果のペアを返す
struct pair div( int64_t n, int64_t d )
{
  int64_t c = gcd(n,d);
  return (struct pair){n/c, d/c};
}

/// 2つの約分済み有理数が等しいかどうかを調べる
bool equals( struct pair a, struct pair b )
{
  return a.n==b.n && a.d==b.d;
}

/// 等比数列なら true
bool is_g( int64_t const * nums )
{
  struct pair r0=div(nums[1],nums[0]);
  for( int i=1 ; i<4 ; ++i ){
    struct pair r =div(nums[i+1], nums[i] );
    if ( ! equals( r0, r ) ){
      return false;
    }
  }
  return true;
}

/// フィボナッチ数なら true
bool is_f( int64_t const * nums )
{
  struct fibs{ int64_t m[5]; };
  struct fibs fibs = {{ 0,1,1,2,3}};
  while( fibs.m[0]<nums[0] ){
    fibs = (struct fibs){{
      fibs.m[1],fibs.m[2],fibs.m[3],fibs.m[4],
      fibs.m[3]+fibs.m[4],
    }};
  }
  for( int i=0 ; i<5 ; ++i ){
    if ( fibs.m[i] != nums[i] ){
      return false;
    }
  }
  return true;
}

/// 問題を解く。
char solve( int64_t const * nums )
{
  if ( is_a( nums ) ){
    return 'A';
  }
  if ( is_g( nums ) ){
    return 'G';
  }
  if ( is_f( nums ) ){
    return 'F';
  }
  return 'x';
}

int main(int argc, char const * argv[] )
{
  int64_t nums[5];
  fscanf( stdin, "%lld %lld %lld %lld %lld", nums, nums+1, nums+2, nums+3, nums+4 );
  putchar(solve( nums ) );
}

有理数の実装というと大掛かりに聞こえるかもしれませんが、約分と比較があるだけです。約分のために最小公倍数も必要になります。
C言語なので、フィボナッチ数のチェックに行数を要してしまっていますが、この部分は ruby の実装と同等です。

最後に

この問題は、非常に多くの方に挑戦いただいたんですが、初回正解率 1割以下、最終正解率も6割ちょっとという惨状でした。敗因の殆どは、浮動小数点数で戦おうとしてしまったことにありました。

等比数列かどうかの判断には、許容誤差ゼロで比が等しいことの確認が必要です。許容誤差ゼロということは、浮動小数点数は使えない(例外はありますが)ということです。

というわけで。
浮動小数点は便利ですが、場面を間違えるとひどい目に合います。気をつけましょう。

多くの方の挑戦、ありがとうございました。
また楽しんでいただける問題を出していきたいと思います。