CodeIQ に出した「中学入試から：概数と計算」の解説解題

CodeIQ に「中学入試から：概数と計算」という問題
https://codeiq.jp/ace/nabetani_takenori/q1282
を出した。

中学入試算数問題第6弾。

挑戦の募集はすでに締めきっている。
というわけで、解説・解題。

で。
まずは問題

問題

■問題の概要
中学入試算数の範囲で、以下の様な問題を作ることが出来ます。
ある数の小数第3位を四捨五入した結果を 1.7 倍してから小数第1位を四捨五入すると42になります。
この数はどんな範囲にありますか。
範囲は、「以上」「より大きく」「以下」「未満」を用いて答えなさい。
ある数にあてはまる数が全くない場合は「なし」と答えなさい。
この問題を
ある数の小数第【あ】位を【い】した結果を【う】倍してから小数第【え】位を【お】すると【か】になります。
この数はどんな範囲にありますか。
範囲は、「以上」「より大きく」「以下」「未満」を用いて答えなさい。
ある数にあてはまる数が全くない場合は「なし」と答えなさい。
と考え、【あ】〜【か】を入力として与えます。問題の答えを計算するプログラムを書いて下さい。
【あ】【え】には、正の整数が入ります。
【い】【お】には、「四捨五入」「切り捨て」「切り上げ」のいずれかが入ります。
■具体的な課題
下記リンクの zip 内に data.utf8.txt および data.sjis.txt というファイルがあります。
これらのファイルの各行は
　「データID、【あ】〜【か】の内容、【あ】〜【か】の内容に対応した答え」
を TAB区切りでならべたものです。
ほとんどのデータは正しい答えになっています。
答えが間違っているデータが数件あります。それらのデータの ID を答えて下さい。
data.utf8.txt と data.sjis.txt は、文字コードが異なるだけで内容はまったく同じです。
お好きな方をお使い下さい。
■補足
・データIDがTで始まるデータは、すべて正しい答えになっています。テストにお使い下さい。
・不正な入力に対処する必要はありません。
・間違いの数は、5件より多く、20件より少なくなっています。
■資料
http://nabetani.sakura.ne.jp/codeiq/q1282.zip
上記リンク先の zip ファイルの中には、以下のファイル含まれています。
・ data.utf8.txt
　→ 調査対象およびテストデータです。文字コードは UTF-8 になっています。
・ data.sjis.txt
　→ 調査対象およびテストデータです。文字コードは SHIFT_JIS になっています。
ふたつのファイルは、文字コードが異なるだけで内容は同じです。
■解答形式
「【解答】」の行に続いて解答をお書き下さい。
「【感想・工夫した点など】」の行に続いて、感想、引っかかった点、工夫した点、問題が曖昧だと感じた場合はそこをどう解釈したか、などをお書き下さい。
「【言語と処理系】」の行に続いて、言語名、処理系のバージョン、コマンドラインオプションなどをお書き下さい。
「【ソースコード】」の行に続いて、【あ】〜【か】の値を元に問題を解くプログラムのソースコードをお書き下さい。ソースコードが複数になるようでしたら、その旨がわかるようにお願いします。

こんな感じ。

出題の背景と意図とか

毎回おんなじことを書いているけど、これもかなりリアルな中学入試問題。
たぶん、中学入試算数のことを知っている方は、『範囲は、「以上」「より大きく」「以下」「未満」を用いて答えなさい。』という解答形式にリアリティを感じると思う。

出題意図は今まで出した問題の中で一番はっきりしている。
一言で言えば「浮動小数点の誤差に負けて下さい」である。

というのも、中学入試から：正三角形？二等辺？のような、浮動小数点の誤差に無頓着でも正しい答えに辿りつけてしまう問題を出してしまっていることを申し訳ないと感じていて。
浮動小数点で戦おうとするときっちり敗北する、敗北しないまでも大苦戦する問題を出しておかねばという使命感があり、この問題に至った。

実装戦略と例

たぶん、この手の話に慣れているプログラマなら、題意を理解した時点で浮動小数点でいくのはキツイなと理解したと思う。
浮動小数点ってのは、計算結果が常に適当に（あるルールに従って）丸められるもの。誤差のない計算をするためのものではない。
精度を状況に応じて変更するのも難しい場合が多い。
一方。この問題は許容誤差がとても少ないし、どれだけの制度があれば十分なのかがわかりにくい内容になっている。
精度の高い二進化十進数で行けば勝てたりもするんだけど、本当にそれで勝てているのかと自信は持てないと思う。
少なくとも、出題者として問題データを二進化十進数で用意する気にはならない。

というわけで有理数を使うのがおそらく唯一の安心できる実装になる。

有理数は、ruby や python には組み込みのものがあるのでそれを使うのがいい。
JavaScript や C には標準的な有理数はないので、そういう処理系の場合には自作する必要があるんだけど、それは面倒ということであれば、有理数のある言語を選べばいいと思う。言語の選択は自由だから。

で。ruby による実装例。

# 四捨五入などの結果から、四捨五入などをする前の値の範囲を求める。
# @param [Array] medi 値の範囲。[ [ 下限, 境界含む ], [上限, 境界含む ] ] という内容。
# @param [Integer] pos 四捨五入などをする桁
# @param [String] m "四捨五入" などの丸め方を示す文字列
# @return [Array] 元の値の範囲。[ [ 下限, 境界含む ], [上限, 境界含む ] ] という内容。範囲が空集合の場合は nil。
def range(medi, pos, m)
  fail [medi, pos, m].inspect unless pos == pos.round
  r = 1.to_r / 10**pos
  lo = (medi[0].last ? (medi[0].first / (r * 10)).ceil : (medi[0].first / (r * 10)).floor + 1) * r * 10
  hi = (medi[1].last ? (medi[1].first / (r * 10)).floor : (medi[1].first / (r * 10)).ceil - 1) * r * 10
  return nil unless lo <= hi
  case m
  when '四捨五入' then [[lo - r * 5, true], [hi + r * 5, false]]
  when '切り捨て' then [[lo - r * 0, true], [hi + r * 10, false]]
  when '切り上げ' then [[lo - r * 10, false], [hi + r * 0, true]]
  end
end

# 有理数の文字列化。20桁までの有限小数になるもののみ対応。
# ruby2.2.0 なら ( "%.20f" % r ).gsub( /0*$/, "" ) でいいけど、2.1以前だとこういう処理が必要。
def str(r)
  i = r.floor
  f = r - i
  if f == 0
    i.to_s
  else
    frac = 20.times.find { |n| # 遅い。
      x = (r * 10**n)
      x.round == x
    }
    '%d.%0*d' % [i, frac, (r - i) * 10**frac]
  end
end

# 問題を解く
def solve(a, i, u, e, o, ka)
  a, e = [a, e].map(&:to_i)
  u, ka = [u, ka].map(&:to_r)
  medi = range([[ka, true], [ka, true]], e, o)
  r = medi && range(medi.map { |x, y| [x / u, y] }, a, i)
  if r
    [str(r[0][0]), r[0][1] ? '以上' : 'より大きく', str(r[1][0]), r[1][1] ? '以下' : '未満'].join
  else
    'なし'
  end
end

if $PROGRAM_NAME == __FILE__
  File.open('data.utf8.txt', 'r:utf-8').flat_map do |line|
    next if line.strip.empty?
    id, a, i, u, e, o, ka, expected = line.split(/\s+/)
    actual = solve(a.to_i, i, u.to_r, e.to_i, o, ka.to_r)
    actual != expected ? [id] : []
  end.join(',').tap { |x| puts x }
end

str が残念な感じ。すいません。
詳しくは
('%.20g' % 1.001r).to_r != 1.001r - Qiita
をご覧ください。

感想など

今回も大半の方が正解だったんだけど、今までよりも挑戦者数が少なかった。
解けなかった方が多くいたんではないかと想像していて、申し訳なかったような、むしろいいことをしたような、微妙な感じ。

あと。挑戦いただいた方々から難しかったという声を多く頂いた。
まあ私としても難しかったと思っている。

いつも通り、締切後はコード公開大歓迎。
コードを公開したら、 twitter などで知らせてくれると見つけやすくて助かります。

次の問題は、数日のうちに公開される予定。今回と比べるとずっと簡単。のつもり。

Codeへの愛とCuriosity

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

CodeIQ に出した「中学入試から：概数と計算」の解説解題

問題

出題の背景と意図とか

実装戦略と例

感想など