【解答】
111,222,321,333,432,444,543,555,654,666,765,777,876,888,987,999
【感想・工夫した点など】
問題を読んだときは、探索が大変そうだという気がしましたが、
対称にした図形を求めれば良いということがわかり、道が開けました。
対称となる点を求める数式が完成したあとは、迷うことなく、解答にたどり着きました。
nが奇数の場合の多角形の処理は別に考える必要がありそうだったのですが、
全て同じ処理で行うことができました。
前回の問題はお手上げだったのですが、今回は簡単でした。
【言語と処理系】
ruby 2.0.0p598 (2014-11-13) [x64-mingw32]
【ソースコード】
# 円周上を n 等分する点を考え、順に 点0, 点1, 点2, ... , 点(n - 1) とする
# 点 axis を通る対称軸で、点 pos と対称となる点を求める
# なお、axis の少数第一位が 5 である場合は、
# axis を少数第一位で切り捨てた値と、少数第一位で切り上げた値の間の点を通る対称軸とする
def symmetry_pos(n, pos, axis)
return (n - (n + pos - axis).floor % n + axis).floor % n
end
# 点 axis を通る対称軸で、線分 line と対称となる線分を求める
def symmetry_line(n, line, axis)
return [symmetry_pos(n, line[0], axis), symmetry_pos(n, line[1], axis)].sort
end
# 点 axis を通る対称軸で、図形 lines と対称となる図形を求める
def symmetry(n, lines, axis)
return lines.collect {|line| symmetry_line(n, line, axis)}
end
# 点A, 点B, 点C, ...という形式を
# 点0, 点1, 点2, ...といういう形式に変換する
def convert(lines)
line_set = []
lines.each do |line|
line_set << [line[0].ord - 'A'.ord, line[1].ord - 'A'.ord].sort
end
return line_set
end
# 対称軸の数を数える
def count_axis(n, lines)
count = 0
# 隣り合う点の間を通る対称軸は、0.5, 1.5, 2.5, ...として表す
0.step((n-1)/2.0, 0.5) do |i|
if symmetry(n, lines, i).sort == lines.sort
count += 1
end
end
return count
end
File.open("data.txt", "r") do |f|
wrong_id = []
while problem = f.gets
id, a, i, answer = problem.strip.split(" ")
n = a.to_i
lines = i.split(",").collect {|line| line.split('')}
answer = answer.to_i
# 点A, 点B, 点C, ...という形式を
# 点0, 点1, 点2, ...といういう形式に変換
lines = convert(lines)
# 対称軸の数を数える
count = count_axis(n, lines)
if count != answer
wrong_id << id
end
end
puts wrong_id.join(",")
end
44CQ6Kej562U44CRCjExMSwyMjIsMzIxLDMzMyw0MzIsNDQ0LDU0Myw1NTUsNjU0LDY2Niw3NjUsNzc3LDg3Niw4ODgsOTg3LDk5OQrjgJDmhJ/mg7Pjg7vlt6XlpKvjgZfjgZ/ngrnjgarjganjgJEK5ZWP6aGM44KS6Kqt44KT44Gg44Go44GN44Gv44CB5o6i57Si44GM5aSn5aSJ44Gd44GG44Gg44Go44GE44GG5rCX44GM44GX44G+44GX44Gf44GM44CBCuWvvuensOOBq+OBl+OBn+Wbs+W9ouOCkuaxguOCgeOCjOOBsOiJr+OBhOOBqOOBhOOBhuOBk+OBqOOBjOOCj+OBi+OCiuOAgemBk+OBjOmWi+OBkeOBvuOBl+OBn+OAggrlr77np7DjgajjgarjgovngrnjgpLmsYLjgoHjgovmlbDlvI/jgYzlrozmiJDjgZfjgZ/jgYLjgajjga/jgIHov7fjgYbjgZPjgajjgarjgY/jgIHop6PnrZTjgavjgZ/jganjgornnYDjgY3jgb7jgZfjgZ/jgIIKbuOBjOWlh+aVsOOBruWgtOWQiOOBruWkmuinkuW9ouOBruWHpueQhuOBr+WIpeOBq+iAg+OBiOOCi+W/heimgeOBjOOBguOCiuOBneOBhuOBoOOBo+OBn+OBruOBp+OBmeOBjOOAgQrlhajjgablkIzjgZjlh6bnkIbjgafooYzjgYbjgZPjgajjgYzjgafjgY3jgb7jgZfjgZ/jgIIK5YmN5Zue44Gu5ZWP6aGM44Gv44GK5omL5LiK44GS44Gg44Gj44Gf44Gu44Gn44GZ44GM44CB5LuK5Zue44Gv57Ch5Y2Y44Gn44GX44Gf44CCCuOAkOiogOiqnuOBqOWHpueQhuezu+OAkQpydWJ5IDIuMC4wcDU5OCAoMjAxNC0xMS0xMykgW3g2NC1taW5ndzMyXQrjgJDjgr3jg7zjgrnjgrPjg7zjg4njgJEKIyDlhoblkajkuIrjgpIgbiDnrYnliIbjgZnjgovngrnjgpLogIPjgYjjgIHpoIbjgasg54K5MCwg54K5MSwg54K5MiwgLi4uICwg54K5KG4gLSAxKSDjgajjgZnjgosKCiMg54K5IGF4aXMg44KS6YCa44KL5a++56ew6Lu444Gn44CB54K5IHBvcyDjgajlr77np7DjgajjgarjgovngrnjgpLmsYLjgoHjgosKIyDjgarjgYrjgIFheGlzIOOBruWwkeaVsOesrOS4gOS9jeOBjCA1IOOBp+OBguOCi+WgtOWQiOOBr+OAgQojIGF4aXMg44KS5bCR5pWw56ys5LiA5L2N44Gn5YiH44KK5o2o44Gm44Gf5YCk44Go44CB5bCR5pWw56ys5LiA5L2N44Gn5YiH44KK5LiK44GS44Gf5YCk44Gu6ZaT44Gu54K544KS6YCa44KL5a++56ew6Lu444Go44GZ44KLCmRlZiBzeW1tZXRyeV9wb3MobiwgcG9zLCBheGlzKQogIHJldHVybiAobiAtIChuICsgcG9zIC0gYXhpcykuZmxvb3IgJSBuICsgYXhpcykuZmxvb3IgJSBuCmVuZAoKIyDngrkgYXhpcyDjgpLpgJrjgovlr77np7Dou7jjgafjgIHnt5rliIYgbGluZSDjgajlr77np7Djgajjgarjgovnt5rliIbjgpLmsYLjgoHjgosKZGVmIHN5bW1ldHJ5X2xpbmUobiwgbGluZSwgYXhpcykKICByZXR1cm4gW3N5bW1ldHJ5X3BvcyhuLCBsaW5lWzBdLCBheGlzKSwgc3ltbWV0cnlfcG9zKG4sIGxpbmVbMV0sIGF4aXMpXS5zb3J0CmVuZAoKIyDngrkgYXhpcyDjgpLpgJrjgovlr77np7Dou7jjgafjgIHlm7PlvaIgbGluZXMg44Go5a++56ew44Go44Gq44KL5Zuz5b2i44KS5rGC44KB44KLCmRlZiBzeW1tZXRyeShuLCBsaW5lcywgYXhpcykKICByZXR1cm4gbGluZXMuY29sbGVjdCB7fGxpbmV8IHN5bW1ldHJ5X2xpbmUobiwgbGluZSwgYXhpcyl9CmVuZAoKIyDngrlBLCDngrlCLCDngrlDLCAuLi7jgajjgYTjgYblvaLlvI/jgpIKIyDngrkwLCDngrkxLCDngrkyLCAuLi7jgajjgYTjgYbjgYTjgYblvaLlvI/jgavlpInmj5vjgZnjgosKZGVmIGNvbnZlcnQobGluZXMpCiAgbGluZV9zZXQgPSBbXQogIGxpbmVzLmVhY2ggZG8gfGxpbmV8CiAgICBsaW5lX3NldCA8PCBbbGluZVswXS5vcmQgLSAnQScub3JkLCBsaW5lWzFdLm9yZCAtICdBJy5vcmRdLnNvcnQKICBlbmQKICByZXR1cm4gbGluZV9zZXQKZW5kCgojIOWvvuensOi7uOOBruaVsOOCkuaVsOOBiOOCiwpkZWYgY291bnRfYXhpcyhuLCBsaW5lcykKICBjb3VudCA9IDAKICAjIOmao+OCiuWQiOOBhueCueOBrumWk+OCkumAmuOCi+WvvuensOi7uOOBr+OAgTAuNSwgMS41LCAyLjUsIC4uLuOBqOOBl+OBpuihqOOBmQogIDAuc3RlcCgobi0xKS8yLjAsIDAuNSkgZG8gfGl8CiAgICBpZiBzeW1tZXRyeShuLCBsaW5lcywgaSkuc29ydCA9PSBsaW5lcy5zb3J0CiAgICAgIGNvdW50ICs9IDEgCiAgICBlbmQKICBlbmQKICByZXR1cm4gY291bnQKZW5kCiAgICAKRmlsZS5vcGVuKCJkYXRhLnR4dCIsICJyIikgZG8gfGZ8CiAgd3JvbmdfaWQgPSBbXQogIHdoaWxlIHByb2JsZW0gPSBmLmdldHMKICAgIGlkLCBhLCBpLCBhbnN3ZXIgPSBwcm9ibGVtLnN0cmlwLnNwbGl0KCIgIikKICAgIG4gPSBhLnRvX2kKICAgIGxpbmVzID0gaS5zcGxpdCgiLCIpLmNvbGxlY3Qge3xsaW5lfCBsaW5lLnNwbGl0KCcnKX0KICAgIGFuc3dlciA9IGFuc3dlci50b19pCgogICAgIyDngrlBLCDngrlCLCDngrlDLCAuLi7jgajjgYTjgYblvaLlvI/jgpIKICAgICMg54K5MCwg54K5MSwg54K5MiwgLi4u44Go44GE44GG44GE44GG5b2i5byP44Gr5aSJ5o+bCiAgICBsaW5lcyA9IGNvbnZlcnQobGluZXMpCgogICAgIyDlr77np7Dou7jjga7mlbDjgpLmlbDjgYjjgosKICAgIGNvdW50ID0gY291bnRfYXhpcyhuLCBsaW5lcykKICAgIAogICAgaWYgY291bnQgIT0gYW5zd2VyCiAgICAgIHdyb25nX2lkIDw8IGlkCiAgICBlbmQKICBlbmQKICBwdXRzIHdyb25nX2lkLmpvaW4oIiwiKQplbmQ=