Codeへの愛とCuriosity

CodeIQ への出題・解説解題・その周辺について、思いつくままに。

今まで CodeIQ に出した問題のリスト

自分のためでもある、今まで CodeIQ に出した問題のリスト。つまり、前回( 今まで CodeIQ に出した問題 - Codeへの愛とCuriosity )の続き。

一年以上たっているので、だいぶ問題が出ている。
前回は 29番までだったんだけど、20番以降は挑戦者数が増えていたりするので再掲。

# 問題へのリンク 募集期間 挑戦者数
20 バスの料金を計算しよう(ややリアル編) 2015/09/11 ～ 2016/08/31 180人
21 バスの料金を計算しよう(初級編) 2015/09/11 ～ 2016/08/31 308人
22 先制 hello, world 2015/09/03 ～ 2015/09/21 106人
23 ボタンを押して数を作ろう 2015/10/06 ～ 2016/08/31 497人
24 くねくね最短経路 2015/10/23 ～ 2016/08/31 106人
25 最寄りの素数 2015/11/26 ～ 2016/08/31 139人
26 【機械学習 超初級】【選択式】機械学習の基本のようなそうでもないような問題です 2015/12/03 ～ 2017/06/30 861人
27 遠い昔、はるか彼方の銀河系の カレンダー（初級編） 2015/12/24 ～ 2016/03/24 186人
28 遠い昔、はるか彼方の銀河系の カレンダー（ややリアル編） 2015/12/24 ～ 2016/03/24 113人
29 パスカルの　三角形では　ありません（字余り） 2016/01/21 ～ 2016/08/31 233人
30 1の並びで小さい方から 2016/02/25 ～ 2016/08/31 111人
31 世界は歪んでいる。それでも君は歩む。 2016/03/17 ～ 2016/08/31 100人
32 ２つの円の位置関係 2016/04/21 ～ 2016/07/21 135人
33 円と線分の位置関係 2016/04/21 ～ 2016/07/21 83人
34 カードを使って数を作ろう（簡単編） 2016/06/02 ～ 2016/09/02 114人
35 カードを使って数を作ろう（両面編） 2016/06/02 ～ 2016/09/02 89人
36 共通の祖先は誰だろう 2016/05/19 ～ 2016/08/19 105人
37 排他的n乗数 2016/06/09 ～ 2016/09/09 182人
38 うそつきがいる！（いないかもしれません） 2016/06/23 ～ 2016/09/23 135人
39 連分数の足し算 2016/06/16 ～ 2016/09/16 123人
40 等比？ 等差？ フィボナッチ？？ 2016/07/14 ～ 2016/10/14 258人
41 限られた数字で作れる数の、まんなかの値 2016/07/21 ～ 2016/10/21 158人
42 【100名限定】変進小数の足し算【手動採点】 2016/07/28 ～ 2016/08/08 101人
43 チェックポイントを順番に 2016/08/10 ～ 2016/11/10 73人
44 三角形と点の関係 2016/08/18 ～ 2016/11/18 120人
45 共通部分は何角形？ 2016/08/25 ～ 2016/11/25 75人
46 左と右の有理数 2016/09/15 ～ 2016/12/15 132人
47 ヘックス上の最長狭義単調増加列 2016/09/29 ～ 2016/12/29 109人
48 単調増加で単調減少な数 2016/10/13 ～ 2017/01/13 102人
49 異世界のブラウザの判定 2016/10/20 ～ 2017/01/20 141人
50 撤去作業の果てに現れる数列 2016/10/27 ～ 2017/01/27 124人
51 ちょっと奇妙な足すと引く 2016/11/02 ～ 2017/02/03 160人
52 ダブルテトロミノ 2016/11/17 ～ 2017/02/17 69人
53 ぐるぐるスクエア 2016/11/24 ～ 2017/02/24 138人
54 ぐるぐるペンタゴン 2016/11/24 ～ 2017/02/24 51人
55 外周の折り目 2016/12/08 ～ 2017/03/08 69人
56 放物線とマス目の関係 2016/12/15 ～ 2017/03/15 177人
57 縦線と横線でマス目を塗る 2016/12/22 ～ 2017/03/22 183人
58 境界線の長さ 2017/01/19 ～ 2017/04/19 162人
59 周期表 2017/01/26 ～ 2017/04/26 162人
60 素数の足し算で 2017/02/23 ～ 2017/05/23 164人
61 ◯はぴったり☓は無し 2017/03/02 ～ 2017/06/01 82人
62 メビウスの亀 2017/03/23 ～ 2017/06/23 77人

というわけで、いままで 63問出したらしい（最初が0なので）。

常にネタ切れ感があって自転車操業なんだけど、自転車は好きだよ。

最近のお気に入りはぐるぐるペンタゴンとメビウスの亀。他にも色々だけど。
地味な感じだけど周期表も結構好き。

CodeIQ に出した「等比？ 等差？ フィボナッチ？？ 」の解説解題ではない何か

CodeIQ に出した「等比？ 等差？ フィボナッチ？？ 」の解説解題は CodeIQ Magazine (
https://codeiq.jp/magazine/2016/10/46246/ ) の方に書いたので、ここに書くのはそれ以外の何か。

出題意図

解説解題を読んでいただければわかる通り、肝は等比数列。
息をするように有理数を選んだ人（私もそうすると思う）は気づかないような肝だけど、出題意図はそこにあった。

フィボナッチはむしろオマケの感じだった。

問題文の罠

当初は「等差？　等比？」の順だったんだけど、問題文の順にテストをしたときに
「9999999990 9999999991 9999999992 9999999993 9999999994 」
のようなテストデータで失敗するように、「等比？　等差？」の順にした。

テストデータ

数列は「ハズレ」を含めて 4種類×3件 にした。
浮動小数点で来た人が不正解になるように頑張ってデータを作った。
まずは前掲のデータ。これはかなりの精度で等比数列っぽくなっている。しかしこれだけでは、評価の順序を変えると等差数列であって等比数列ではないとバレてしまう。
で。等差数列ではない、等比数列っぽい数列を探したところ。
フィボナッチ数（のようなもの）が該当することに気がついた。

たとえば、12番の「1032569015 1670731762 2703300777 4374032539 7077333316」はフィボナッチ数的な数列になっている。これが非常に等比数列っぽい。初項が異なるので、この問題の意味ではフィボナッチ数ではない。というわけで、このテストデータは２つの意味で罠になっている。

反省

64bit 整数しかないのに a1×a3=a2×a2 で判定した場合にちゃんと負けるような問題にできていなかった。
詰めが甘い。

それと。 long double だと浮動小数点でも勝ってしまう


(ciel さん ありがとうございます）

ようで、ここも詰めが甘いなという感じ。

反省。

CodeIQ に出した「1の並びで小さい方から」の解説解題

CodeIQ に「1の並びで小さい方から」( https://codeiq.jp/q/2706 )という問題を出した。

問題の概要はこんな感じ：

数を2進数で表します。このとき、1 の連なりの最大の長さを
F(n)
と書きます。
X と Y という2つの数を与えます。
1以上の整数 n について、F(n)=X である n のうち、小さい方から Y 番目の数を求めてください。

入力は、XとY をコンマ区切りで繋いだ文字列です。
ただし：

  • X は、1以上32以下の整数です。
  • Y は、1以上1000以下の整数です。

数学的背景とかアルゴリズム的背景はいつもどおり特になくて、ふと思いついたから出したという感じ。
「32,10000」とか「1,1000」で計算時間が多くなりすぎて敗北しがちなのがこの問題の面白みだと思う。

で。どうするか。

比較的読みやすいけど実行時間はギリギリになりやすい実装から。

字句解析を省略するけど、こんな感じ：

def f(n)
  len=maxlen=0
  m=1
  loop do
    if 0 != (m & n )
      len+=1
      maxlen = len if maxlen<len
    else
      len=0
    end
    return maxlen if n<m
    m<<=1
  end
end

def solve( keta, ord )
  cands = {(1<<keta)-1=>true}
  memo={}
  keta.upto(Float::INFINITY) do |k|
    cands.keys.each{ |x|
        [x*2, x*2+1, x+(1<<k)].each do |y|
          cands[y]=true if (memo[y]||=f(y))==keta
        end
    }
    return cands.keys.sort[ord-1] if ord<cands.size
  end
end

たとえば X が 3 の場合。
まず、0b111 だけがある集合（実装の都合で Hash だけど）を用意する。
桁数を X から順に増やしていって、集合に含まれている要素について

  • 右にゼロをつける( x*2 )
  • 右に 1 をつける( x*2+1 )
  • k 桁目に 1 をつける( x+(1<<k) )

の3つの数について調査して、F(n) が X であれば集合に追加する。
集合のサイズが Y を超えたところで小さい方から Y 番目を返せば終了。

でも、この実装だとちょっとギリギリ。

f は to_s(2) を使えばもっと短く書けるんだけど、実行速度を優先して整数演算のみにした。

もうちょっと速い実装はだいぶ長いんだけどこんな感じ：

# 1の連なりが len 個で、桁数 keta 桁以下の数のリスト
def just_lte(len,keta)
  (len..keta).flat_map{ |k|
    just_just(len,k)
  }
end

# 1の連なりが len 個で、桁数 keta 桁の数のリスト
def just_just(len,keta)
  return [] if keta<len
  return [2**len-1] if keta==len
  #len より少ない 1の連なり + ちょうど len 個を含むパターン
  lt_just=(1...len).flat_map{ |x|
    lows=just_lte(len, keta-x-1)
    head = (2**x-1)<<(keta-x)
    lows.flat_map{ |o|
      o+head
    }
  }
  #ちょうど len個の 1の連なり + len 以下のパターン
  lt_just+lte_lte(len, keta-len-1).flat_map{ |o|
    ((2**len-1)<<(keta-len))+o
  }
end

$memo={}
# 1の連なりが len 個以下で、桁数が keta 桁以下の数のリスト（メモ化）
def lte_lte(len,keta)
  $memo[[len,keta]]||=lte_lte_impl(len,keta)
end

# 1の連なりが len 個以下で、桁数が keta 桁以下の数のリスト（実装）
def lte_lte_impl(len,keta)
  len = [len, keta].min
  (len+1).times.flat_map{ |x|
    head = (2**x-1)<<(keta-x)
    lows=lte_lte(len, keta-x-1)
    lows=[0] if lows.empty?
    lows.flat_map{ |o|
      o+head
    }
  }
end

def solve( len, ord )
  r=[]
  (len..Float::INFINITY).each do |k|
    r+=just_just(len, k)
    if ord<r.size
      return r.sort[ord-1]
    end
  end
end

行ったり来たりの再帰呼び出しになっていて追いにくい。すいません。
1の連なりが len 個以下で、桁数が keta 桁以下の数のリスト をメモ化付き再帰呼び出しで創りだして、そこからちょうどのものを構成するという流れ。
自分でもわかりにくいと思う。

パスカルの　三角形では　ありません（字余り） の解説解題

CodeIQ に、「パスカルの　三角形では　ありません（字余り）」( https://codeiq.jp/q/2630 ) という問題を出していたんだが、先日締め切られた。

で。解説解題。

二次元の表に数字が埋まっていて、表外の数字を外挿して計算せよ、という問題。

表の数字などについては
http://ange1.hateblo.jp/entry/2016/09/06/124121
を参考にしていただくとして、規則性の方はタイトルの通りパスカルの三角形からヒントを得た二次元数列になっていて。
左上隅を {a(0,0)} とすると、こんな感じ：

{ \displaystyle a(x,y)=1~~if~x<0~\lor~y<0 }
{ \displaystyle a(0,0)=1 }
{ \displaystyle a(x,y)=a(x-1,y)+a(x,y-1)+a(x,y-2)~~otherwise }

で。これを定義のとおりに計算すれば良いという簡単な問題だったつもり。まあ計算量を減らすためにメモ化ぐらいはした方がいい。

とはいえ。

ルールが簡単なので、漸化式ではない形にできてしまう。

計算のために、先ほどの式に以下のように意味づけする：

縦の道が x+1 本。横の道が y+1 本ある経路を左上から右下まで最短経路で行く方法の場合の数。ただし、横方向に行く方法は、1マス進む「歩く」と、2マス進む「ジャンプ」の2通りがある。そして「歩く」と「ジャンプ」は区別する。

で。

ジャンプが n回の場合を考える。
ジャンプをいつ使うのかを気にしなければ、横方向のマスが n 個減った場合と同じなので
{\binom{x+y-n}{y-n}}
となる。
横方向の移動は x-n 回ある。そのうち n 回「ジャンプ」を使うのでジャンプする場所の選び方は
{\binom{x-n}{n}}
となる。
したがって、ジャンプが n 回の場合の場合の数は
{\binom{x+y-n}{y-n}×\binom{x-n}{n}}
になる。
ジャンプの回数は 0回以上 {\lfloor x/2 \rfloor}回以下なので、

{\displaystyle a(x,y)=\sum_{n=0}^{\lfloor x/2 \rfloor}{\binom{x+y-n}{y-n}×\binom{x-n}{n}}}

となる。

とまあ、こんな計算をしてもいいんだけど、むしろこちらは想定外。

想定解答はあくまでもメモ化付きの漸化式なのでありました。

CodeIQ に出した「共通の祖先は誰だろう」の解題解説

CodeIQ に出した「共通の祖先は誰だろう」の解題解説

「共通の祖先は誰だろう」( https://codeiq.jp/q/2825 )という問題を CodeIQ に出していたが、先日締め切られた。

100名を超える方の挑戦をいただいた。ありがとうございます。

で。

まずは問題。

問題

問題は

f:id:Nabetani:20160820141059p:plain
図のような家系図があります。
紙面の都合で 29 までしか書いていませんが、正の整数が全て含まれています。
上が祖先で下が子孫です。
上から順、左から順に 1, 2, ... と番号が振られています。
偶数には子が2人、奇数には子が3人います。
で。
複数の数を与えます。共通の祖先の番号のうち、最大のものを出力してください。

  • 入力の値は、10億を超えることはありません。
  • 入力の数は、10個を超えることはありません。
  • 「祖先」には自分自身を含みません。[A]と[Aの親]の共通の祖先は[Aの親の親]ということになります。
  • 「共通の祖先」に該当する数がない場合には「-」を出力して下さい。

というような内容だった。

解題解説

作問の意図としては、ツリーを扱う問題を作ろいうという辺り。
やや不規則なツリーを扱うという辺りが見どころかも。

ツリーをじっと見ると。あるいはもう少し大きな数まで作ってみるともっと明らかなんだけど、だいたい 2.5 で割ると親になる。偶数と奇数をセットにすると 親2人に対して子が5人なので、その比率になる。

たとえば、 27。27÷2.5=10.8。実際の親は 11。だいたい合っている。
あとは端数を微調整すると親を求めることができるようになる。
親が計算できれば、そのまた親、そのまた親 と辿っていける。

自分自身は「祖先」に含まないとか、「1」には祖先がいないとか、その辺りが要注意。

実装例

ruby による実装例は以下の通り：

def parent(x)
  return nil if x==1
  x/5*2 + ( x%5<2 ? 0 : 1 )
end

def parents(x)
  pas=[]
  loop do
    pa = parent(pas.last || x)
    return pas unless pa
    pas.push pa
  end
end

def solve(src)
  ( src.split(",").map{ |x|
    parents(x.to_i)
  }.inject(&:&).max || "-" ).to_s
end

puts solve(gets.strip)

ツリーの構造は parent メソッドにに入っている。parents メソッドで祖先をたどり、solve で共通部分の最大値を求めている。
簡単でしょ？

他の方の実装

他にもありましたら twitter のメンションなどで教えていただけると助かります。

「変進小数の足し算」の解題解説

変進小数の足し算の解説・解題

「変進小数の足し算」( https://codeiq.jp/q/2924 )という問題を CodeIQ に出題させて頂いた。

久々の手動採点問題。

フィードバックは終えているが、なにせ手動なので、採点ミスなどあるかも。あったらすいません。twitter DM などで連絡いただければと思います。

多くの方の挑戦があり、大変嬉しく思っています。

採点は久々なのとシステムに慣れていないのとで思ったよりも大変だったんだけど、無事終了。

問題の概要

小数の足し算をして下さい。 ただしこの小数は、

  • 小数第 n 位 が 11-n 進数

という不思議なルールになっています。例えば、小数第1位は 10進数、小数第9位は2進数です。
このルールを「変進小数」と呼びます。
【入出力】
入力は
8.622+3.177
こんな感じです。
2個の変進小数が「+」で区切られて並んでいます。

出力は、
11.811
のように、足し算の結果を変進小数で出力して下さい。

具体的な課題として、変進小数の足し算とその結果が含まれるファイル data.txt があり、結果が間違っているデータの ID を答えさせるという趣向になっている。

解題とか

位取り記数法とは何か、みたいなところに趣旨がある。
そう見せかけておいて、きちんと文字列処理ができるかどうか、というテーマもあったりする。
それと。誤差を許容しない問題なので、浮動小数点で書くとやや負けるようにしたつもり。

採点した感触としては、簡単な問題だった様子。

実装方針

実装方針は

  • 繰り上がりの計算をする
  • 変進小数との普通の数の相互変換を実装する
    • 有理数との相互変換
    • 整数との相互変換
  • それ以外

と、いくつかの方針があり得る。

「それ以外」以外が想定解。それ以外の例は、 haruya 様のこんな
http://ideone.com/GOIUuC
実装。素晴らしいです。

実装例( 繰り上がりの計算をする )

繰り上がりの計算の例は、こんな感じ：

C++11 で

// "clang++ -std=c++11 -Wall"
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <string>

/** 変進小数 v の小数第 pos0 桁目を取り出す */
int at( std::string const & v, int pos0 )
{
  size_t pos = v.find( '.' ) + pos0;
  return  ( pos < v.size() ) ? v.at(pos)-'0' : 0;
}

/** 整数部 z、小数部 v の変進小数文字列を構築する 
 * @note v を関数内で変更するので const 参照にしない。
 */
std::string build_string( int z, std::vector<char> v )
{
  while( '0'==v.back() ){
    v.pop_back();
  }
  std::stringstream ss;
  ss << z;
  if ( !v.empty() ){
    ss <<"." << std::string( v.data(), v.size() );
  }
  return ss.str();
}

/** 変進小数 a と 変進小数 b を加えた結果の文字列を返す */
std::string add_varbase( std::string const & a, std::string const & b )
{
  std::vector<char> v(9);
  int carry=0;
  for( int i=9 ; 0<i ; --i ){
    int base = 11-i;
    int val = carry+at(a,i)+ at(b,i);
    v[i-1]=( val % base ) + '0';
    carry = val / base;
  }
  return build_string( std::stoi(a)+std::stoi(b)+carry, v );
}

/** 問題を解く */
std::string solve( std::string const & src )
{
  std::string lhs, rhs;
  std::stringstream stream( src );
  std::getline( stream, lhs, '+' );
  stream >> rhs;
  return add_varbase( lhs, rhs );
}

/** delim でつなげて begin から end までを出力する */
template< typename iter_t, typename delim_t >
std::ostream &
join( std::ostream & ostr, iter_t begin, iter_t end, delim_t const & delim )
{
  bool first_time = true;
  for( auto it = begin ; it != end ; ++it ){
    if ( first_time ){
      first_time = false;
    } else {
      ostr << delim;
    }
    ostr << *it;
  }
  return ostr;
}

/** data.txt に含まれる間違いの id を出力する */
int main()
{
  std::vector<std::string> ids;
  for( std::ifstream stream( "./data.txt" ) ; stream ; ){
    std::string id, src, expected;
    stream >> id >> src >> expected;
    if ( ! src.empty() ){
      auto actual = solve( src );
      if ( actual != expected ){
        ids.push_back( id );
      }
    }
  }
  join( std::cout, ids.cbegin(), ids.cend(), "," ) << std::endl;
}

正直、挑戦いただいた方の実装にもっといいのがあった。ちょっと悔しい感じ。
join に10行以上要しているのが残念な感じ。

実装例( 有理数との相互変換 )

ruby のような、有理数が組み込み型にある場合には、有理数との相互変換を書くとわかりやすくていいと思う。

組み込み型に有理数がない場合には、10の階乗 倍 したら必ず整数になるので、その整数との変換をするといい。

で。ruby なので、有理数との相互変換を書くとこんな感じ：

def to_num(x)
  a,b=x.split(".")
  bases = [*2..10].reverse.inject([1]){|acc,n|
    acc+[acc.last*n]
  }.drop(1)
  b2=[*2..10].reverse
  a.to_i + b.chars.zip(bases, b2).map{ |n,base,limit| 
    raise "#{n} in #{x} is not valid" unless n.to_r<limit
    n.to_r/base
  }.inject(&:+)
end

def to_digit(x)
  int=x.floor.to_i
  return int.to_s if x==int
  frac = x-int
  d=int.to_s+"."
  [*2..10].reverse.each do |b|
    c=(frac*b).floor.to_s
    raise "bug?" unless c.size==1
    d+=c
    frac*=b
    frac-=frac.floor
  end
  raise "#{x} is not valid for to_digit" unless frac==0
  d.gsub( /0*$/, "")
end

def solve(src)
  to_digit(src.split("+").map{|x| to_num(x)}.inject(&:+))
end

File.open( "data.txt", "r" ) do |f|
  f.map{ |line|
    line.split("\t").map(&:strip)
  }.select{ |id, src, expected|
    expected != solve( src )
  }.map(&:first).join(",").tap{ |x| puts x }
end

私なりだとこんな感じ。
挑戦いただいたものにはもっとコンパクトで読みやすいものがあったように思うので、ちょっと悔しい。

その他の話題

英語

「変進小数」という この問題固有の造語をどう変数名やクラス名にするかという問題があって、そこに悩む方が多くいらっしゃった。

「小数」の英語が「decimal」なのがよくなくて、「decimal」には10進法という意味もあるので今回の問題にはそぐわないと思う。

「可変進法表記」を英語にして「variable base notation」ぐらいが良いかと思う。長いか。

「変進小数」を漢字表記のまま使っている方や、「HenshinShosu」とローマ字で来る方も多かった。潔くて良いと思う。

納品物

問題文中に「足し算の結果を変進小数で出力して下さい。」と書いたので、そのような関数なりクラスなりを用意してほしいと考えていた。
結果と合っているかどうかを見るだけでも「具体的な課題」の結果は正しくできるようにしたし、それを理由に減点したりもしなかったけど。

実装例

気づいた範囲内では、下記の通りです。皆様公開ありがとうございます。

他にもありましたら、 Twitter のメンションなどでお知らせ下さい。

位置関係2題の解説・解題

先日、CodeIQ に出していた

という２つの問題が締め切られた。

私が出した問題が締め切られるのは久々だったので、ちょっと慣れない感じ。

で。

この問題は、タイトルの通り、2つの図形の位置関係を分類する問題になっている。
２つの円の方は、中心と中心の距離を見ればいいだけなので簡単。
円と線分はいろいろ見なくちゃいけないし、分類も多いのでちょっと大変、ということになっている。

数学力はあまり問うていないつもり。高校程度なんだと思う。

いつもなら、一つの事象をひとつのテストデータにするんだけど、今回はそれだと件数が多くなりすぎる感じなので、ひとつのテストデータにたくさんの事象を仕込むことにした。


問題の概要については
http://ange1.hateblo.jp/entry/2016/07/23/001128
をご覧いただくことにして、出題意図を列挙すると。

  • ごちゃごちゃした分類を誤らずに実装できるかどうか
  • 浮動小数点の除算や平方根を使うべきではないという判断ができるかどうか

というつもり。浮動小数点を使っても解決できてしまう場合が多かったようで、この点はテストデータの追い込みが足りなかったと反省している。


「接する」というデリケートな条件を判断する必要がある問題になっているので、誤差がまったくない計算をする必要がある。そして、この問題はそのような実装を無理なくできる問題になっている。入力は整数だし。


誤差のない計算ということで、有理数が簡単に扱える ruby や python だと実装が楽になる。
JavaScript だと苦しい感じかもしれない。


私の場合はやっぱり ruby でこんな感じ：

２つの円の位置関係の実装例：

def solve_one(s)
  x0,y0,r0,x1,y1,r1 = s.scan( /\d+/ ).map(&:to_i)
  d2 = (x0-x1)**2 + (y0-y1)**2
  r0,r1=[r0,r1].minmax
  return "A" if d2==0 && r0==r1
  sr2 = (r0+r1)**2
  return "F" if sr2<d2
  return "E" if sr2==d2
  dr2=(r1-r0)**2
  return "B" if d2<dr2
  return "C" if d2==dr2
  return "D" if d2>dr2
  raise "unexpected"
end

def solve( src )
  src.split(" ").map{ |s|
    solve_one( s )
  }.join("")
end

puts solve(gets)

円と線分の位置関係の実装例：

def calc_min2( a, b, c )
  candidates=[
    c, # x==0
    a+b+c # x==1
  ]
  x=-b/2.to_r/a
  candidates.push( a*x*x+b*x+c ) if 0<=x && x<=1
  candidates.min
end

def solve_one(s)
  cx,cy,r,ax,ay,bx,by = s.scan( /\d+/ ).map(&:to_r)
  ax-=cx
  ay-=cy
  bx-=cx
  by-=cy
  a=ax*ax+ay*ay<=>r*r
  b=bx*bx+by*by<=>r*r
  return "A" if a<0 && b<0
  return "C" if a==0 && b==0
  return "B" if a<=0 && b<=0
  return "F" if a*b<0
  vx=bx-ax
  vy=by-ay
  min2 = calc_min2(vx*vx+vy*vy, 2*(ax*vx+ay*vy), ax*ax+ay*ay )
  case min2<=>r*r
  when -1; a*b==0  ? "D": "E"
  when 0; a*b==0  ? "G": "H"
  when 1; "I"
  end
end

def solve( src )
  src.split(" ").map{ |s|
    solve_one( s )
  }.join("")
end

puts solve(gets)

我ながらもう少しなんとかならなかったのかと思わなくもない。

ともあれ。


多くの方に挑戦いただき大変うれしく思っています。ありがとうございました。