uniの競プロlog

適当に書いていきます

【精進】ABC046 C - AtCoDeer and Election Report

毎日自分のレート+400以上のdiffの問題を解きます。
問題リンク C - AtCoDeer and Election Report

解法

投票数が満たすべき条件は 「広義単調増加」 かつ 「比が T_i:A_i
したがってi回目での投票数は
(i-1) 回目の投票数以上の最小の T_i の倍数 ÷T_i
(i-1) 回目の投票数以上の最小の A_i の倍数 ÷A_i
のうち大きい方を (i-1) 回目の投票数にかければ良い。計算量は O(N)
Submission #53756132 - AtCoder Beginner Contest 046