CodeIQ に出した「中学入試から：対称軸の本数を数えよう」の解説・解題

CodeIQ に「中学入試から：対称軸の本数を数えよう」という問題
https://codeiq.jp/ace/nabetani_takenori/q1318
を出した。

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

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

で。
まずは問題

問題

■問題の概要
中学入試算数の範囲で、以下の様な問題を作ることが出来ます。
円周上を6等分する点を考え、順に点Aから点Fとします。
ここで、BE, EC, CF, FB の4本の線でできている図形を考えます。
この図形には線対称となる対称軸は何本あるでしょうか。
ただし、線対称ではない場合は 0 と答えること。
この問題を
円周上を【あ】等分する点を考え、点の名前を点A, 点B, ... と順につけます。
ここで、【い】の【いの要素の数】本の線でできている図形を考えます。
この図形には線対称となる対称軸は何本あるでしょうか。
ただし、線対称ではない場合は 0 と答えること。
と考え、【あ】と【い】を入力として与えます。問題の答えを計算するプログラムを書いて下さい。
【あ】には、正の整数が入ります。
【い】には、「BE,EC,CF,FB」のような形式で、この図形を構成する線分がコンマ区切りでならべられます。
■具体的な課題
下記リンクの zip 内に data.txt というファイルがあります。
このファイルの各行は
　データID、【あ】の内容、【い】の内容、【あ】【い】の内容に対応した答え
の4件を TAB区切りでならべたものになっています。
ほとんどのデータは正しい答えになっています。
答えが間違っているデータが数件あります。それらのデータの ID を答えて下さい。
■補足
・データIDがTで始まるデータは、すべて正しい答えになっています。テストにお使い下さい。
・不正な入力に対処する必要はありません。
・間違いの数は、5件より多く、20件より少なくなっています。
■資料
http://nabetani.sakura.ne.jp/codeiq/q1318.zip
上記リンク先の zip ファイルの中には、以下のファイル含まれています。
・ data.txt
　→ 調査対象およびテストデータです。
■解答形式
「【解答】」の行に続いて解答をお書き下さい。
「【感想・工夫した点など】」の行に続いて、感想、引っかかった点、工夫した点、問題が曖昧だと感じた場合はそこをどう解釈したか、などをお書き下さい。
「【言語と処理系】」の行に続いて、言語名、処理系のバージョン、コマンドラインオプションなどをお書き下さい。
「【ソースコード】」の行に続いて、【あ】、【い】の値を元に問題を解くプログラムのソースコードをお書き下さい。ソースコードが複数になるようでしたら、その旨がわかるようにお願いします。

こんな感じ。

出題の背景と意図とか

前回難しすぎたという反省のもとに、だいぶ簡単にしてみたつもり。

ジャンルとしては、平面図形の問題。
直感的には明らかな話を、ソースコードでどう表現するかを問う感じ。

書き始まるまでちょっと悩むんだけど、わかってしまえばさらっと書ける感じを狙ってみた。

どうでしたか？

あと。やはりこれもかなりリアルな中学入試問題。
実際に入試に出る場合には、問題用紙に図があると思うけど。

実装戦略と例

最大でも 26角形なので、そうとう変なことをしない限り、計算量のことは度外視できる。
ということで、プログラミングコンテスト文化圏の方以外は、最大26本の対称軸候補について調査し、実際に対称軸になっているものを数え上げる、という作戦で十分。

で。ruby による実装例。

def mirror(a, b, x)
  b.map do |line|
    line.map { |pt| (x - pt) % a }.sort
  end.sort
end

def solve_impl(a, b)
  return 2 if b.size == 1
  a.times.count do |x|
    b == mirror(a, b, x)
  end
end

def solve(a, b)
  points = b.split(',').map do |line|
    line.chars.map { |x| x.ord - 'A'.ord }.sort
  end.sort
  solve_impl(a.to_i, points).to_s
end

if $PROGRAM_NAME == __FILE__
  File.open('data.txt') do |f|
    wrongs = f.map do |line|
      line.strip.split(/\t/)
    end.select do |data|
      _, a, b, expected = data
      solve(a, b) != expected
    end.map(&:first)
    puts wrongs.join(',')
    puts wrongs.size
  end
end

変数名にやる気がなくてすいません。

実装のポイントは、 solve_impl の最初の行。
今回のデータには入っていなかったんだけど、実は線分が一本の場合には対称軸が2個になるので、特別扱いする必要がある。

これに気づいている方はあまり多くなかった。

ruby の場合は、「負の数 % 正の数」が正の数になるので、mirror の実装が簡単になる。
java や Cファミリーの場合は剰余を正の値にするために被除数が正になるように工夫する必要がある。

偶数角形と奇数角形を区別するコードを書いている方も多かったんだけど、上記の通り、条件を整理すると分ける必要はなくなる。

感想など

今回もほとんど全員正解でした。おめでとう！

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

次の問題は、数日のうちに公開される予定。
どうなるか、ちょっとドキドキ。

Codeへの愛とCuriosity

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

CodeIQ に出した「中学入試から：対称軸の本数を数えよう」の解説・解題

問題

出題の背景と意図とか

実装戦略と例

感想など