2007 JOI本選-5-モービル
解法が大体思いついてからすぐだった
解法
この問題は、
安定しているモービルの両端にかかっている重さを両方k倍しても、
モービルは安定する
ということに注目してやると簡単
左の重さをrt,右の重さをbtとする
ここでrt,btは
「下にある部分的なモービルが安定するモービル全体の最小の重さ」
である
下にあるものが錘である場合は1とすれば良い
左側の重さをm倍、右側の重さをn倍すれば、モービルが安定するとすると
rt * m * p = bt * n * q
(mとnは互いに素)
という等式が成り立ち
(rt * p) / (bt * q) = n / m
となる。mとnは互いに素なので左辺を約分しきった状態が右辺であるので
(rt * p) と (bt * q)の最小公倍数をgとすると
n = rt * p / g
m = bt * q / g
よって左の重さは
rt * n
右の重さは
bt * m
となるので、その棒の重さが求められる
あとは再帰するだけ
(僕のコード)https://joi2007ho.contest.atcoder.jp/submissions/1983911
こんな感じかな