作題者によるまとめはhttp://togetter.com/li/971415から。
問題解説はhttps://codeiq.jp/magazine/2016/05/40858/から。
問題の概要はこちら。
■ １ ■
四角形ABCDについて、∠ABD＝a，∠CBD＝b，∠ACB＝c，∠ACD＝d とおきます。
∠ADB を求めることを考えましょう。
さて、a，b，c，d の値（単位は度）に対し、∠ADB の値（単位は度）を 10^6 倍したものの整数部分を F(a，b，c，d) と定義します。
F(a，b，c，d) を求めるプログラムを書いてください。
■ ２ ■
自然数 n に対し、次の性質をもつ自然数 d の総和を G(n) と定義します。
n を d で割った余りが 1 に等しい。
G(n) を求めるプログラムを書いてください。
■ ３ ■
先頭にゼロを持たない自然数であって、逆から読んでも同じ数になる数を回文数と呼びます。
自然数 m に対し、m 以下の回文数の総和を H(m) と定義します。
例えば、H(20)＝56 です。20 以下の自然数では 1～9 と 11 が回文数だからです。
H(m) を求めるプログラムを書いてください。
■ 問 ■
標準入力から、半角空白区切りで自然数 a，b，c，d（a＋b＋c ＜ 180 かつ b＋c＋d ＜ 180）が与えられます。
標準出力に H( G( F( a，b，c，d ) ) ) の値を出力してください。
rubyで書いて提出した回答は下記の通り。
最初に提出したものでは f の計算で数値誤差があって間違った。この手の話は久々。
下のコードでは、切り捨て前に十分小さい値として0.00001をたしている。
この手の問題は整角四角形問題というらしい。学生の頃、三角関数なしでどうやって解くんだと悩んだ記憶がある。
h の計算では、1ケタの数は別に足しておいてから、11 から順に、回文数をひたすら小さい方から生成して順にたしているだけ。数値を文字列にしてひっくり返して足して、、と、手抜きだけど通ったのでまぁいいや、という感じ。
# 正弦定理で等しい辺の長さを探してごにょごにょいじると計算できる。
def f(_a,_b,_c,_d)
include Math
a=_a*PI/180
b=_b*PI/180
c=_c*PI/180
d=_d*PI/180
s=sin(b)*sin(d)*sin(a+b+c)/sin(a)/sin(c)/sin(b+c+d)
ret = atan(sin(b+c)/(s+cos(b+c)))/PI*180*(10**6) + 0.00001
ret < 0 ? (180000000 + ret).to_i : ret.to_i
end
# ナイーブに全通り1からnまで探索すると時間切れなので、少し工夫。
# n=(n-1)/d * d + 1 なので、nをdで割った余りが1のときは、
# (n-1)/dで割った余りも1になる。
# これを使って、1 から sqrt(n)までしか探索しない。
# また、nをdで割った余りが1でないときは、d*i(i>1)で割った余りも
# 1でないということを利用して、判断する回数を減らす。
def g(n)
res=n-1
max=Math.sqrt(n).to_i
arr=Array.new(1+max, false)
(2..max).each{|d|
next if arr[d]
if n%d == 1
res+=d+(n-1)/d
else
(1..(max/d)).each{|i| arr[d*i] = true }
end
}
res
end
# 回文数を小さい方から全通り生成して、mより小さければ結果に足す。
def h(m)
i=1
tmp=-1
len = m.to_s.length
if len == 1 # 1桁のときは別処理。
return (1..m).reduce(&:+)
else
res=45
end
while tmp != res
tmp=res
str=i.to_s
if str.length * 2 == len
wk=(str+str.reverse).to_i
res+=wk if wk < = m
else
([""] + %w(0 1 2 3 4 5 6 7 8 9)).each{|sp|
wk=(str+sp+str.reverse).to_i
res+=wk if wk <= m
}
end
i+=1
end
res
end
a,b,c,d=gets.chomp.split.map(&:to_i)
puts h(g(f(a,b,c,d)))
とすると、