AtCoder Beginner Contest 046 C : AtCoDeerくんと選挙速報 / AtCoDeer and Election Report

abc046.contest.atcoder.jp

当初の方針

ううーん、難しそうだけど、式変形していけば良さそう。

・・・詳細は省くが、整数論を持ち出してやっている途中で、
$a_{i+1}$ が素数でないと成立しないことに気づく。

何故なら、モジュロ演算を行うときに逆元が必要になるのだが、
割る数aが素数でないと逆元が存在しないことがあるから。

そのまま時間切れ。

たぬたろう先輩に聞く

@arukuka Cですか？ある時点の割合が与えられたときに、現在の票数(v1, v2)より大きくて、T:Aの同数倍したもののうち最小の数にその時点の票数がなればいいので、T:Aをmax(v1/A, v2/T)倍したものに現在の票数をすればいいって感じでした。(説明が大変悪い。。
— たぬたろう (@tanutarou730) October 15, 2016

よく分からない・・・。
ACM-ICPC 2016 Asia Tsukuba Regionalで同じチームなため、
同じホテルに泊まっていて、解けたというたぬたろう先輩の下へ。

→分かった。少し違うので訂正。

@arukuka ご指摘の通りmax(v1/T, v2/A)です。。惑わせてごめんなさい。(なぜ文字としてTとAなのか。。。)
— たぬたろう (@tanutarou730) October 15, 2016

現時点での票数を $(T_i, A_i)$ とすると
（一番最初の状態は $T_i=1, A_i=1$ ）、

$\begin{cases} T_{i+1} = T_i \times v_{min} \\ A_{i+1} = A_i \times v_{min} \end{cases}$

$\begin{cases} v_{min} = T_i/t_{i+1} \\ v_{min} = A_i/a_{i+1} \end{cases}$

$v_{min} \in \mathbb{N}$

となる。

入力例1の最後の場合、 $T_i = 3, A_i = 3, t_{i+1}=3, a_{i+1}=2$

$\begin{cases} v &\geq 3/3 \\ & = 1, 2, 3 ... \\ v &\geq 3/2 \\ & = 2, 3, 4 ... \end{cases}$

両者を満たすには、maxをとればいい。

$v_{min} = max(ceil(T_i/t_{i+1}), ceil(A_i/a_{i+1}))$

ここで、ceil関数は切り上げのこと。doubleで返ってくると怖いので、

  long div(long a, long b) {
    return a / b + (a % b == 0 ? 0 : 1);
  }

こんな感じにする。

Submission #932267 - AtCoder Beginner Contest 046 | AtCoder

AC。

補足

なぜ $v_{min}$ をかけて、 $v_{min}$ は現在の票数を
$t_{i+1}, a_{i+1}$ で割ったやつなのか。

それは、次の票数はそれぞれ $t_{i+1}, a_{i+1}$ の倍数になるので、
今の票数がそれらの何倍に当たるのか求めているから。