CodeIQ「中学入試から:図形と場合の数」
CodeIQ の鍋谷武典さん出題の問題。
問題と解説はこちら。
「中学入試から:図形と場合の数」の 解説・解題
下が提出したコード。言語は Ruby。
問題データをつけてすぐに実行できるものを http://ideone.com/cvjXrT に置いておいた。
今回力尽くな方法しか思いつかなかったが、他にうまいやり方ってあるんだろうか。
問題データで頂点がアルファベット順に並んでいることと、combination で取り出される要素の順序がもとの配列での順序と同じことを仮定している。
10行目くらいで端数を切り上げてるのは正三角形に対処するため。
# データは data.txt から読み込む # 正n角形の頂点のうち vertices で指定される頂点で作られる三角形の数を返す def solve(n, vertices) t = Array.new(n ** 2) vertices.combination(3) do |a, b, c| # a < b < c となることを仮定 x, y, z = b - a, c - b, a - c + n t[n * x + y] = t[n * y + z] = t[n * z + x] = true end -(-t.count(true) / 3) # 端数切り上げ end open('data.txt') do |file| file.each do |line| data = line.split("\t") id = data[0] n, expected = [1, 3].map {|i| data[i].to_i} vertices = data[2].split(',').map {|c| c.ord - 'A'.ord} answer = solve(n, vertices) # 計算した答が用意されたものと異なるとき、id, 用意された答, 計算した答 を出力 puts "#{id} #{expected} #{answer}" unless expected == answer end end