ABC046 C - AtCoDeerくんと選挙速報 / AtCoDeer and Election Report

問題
 提出コード1
提出コード2
GCD求める関数書いてますが関係ないです。

解法

提出コード1は、単純に場合分けしていきます。
現在の高橋君の票数を $T$ 、青木君の票数を $A$ とします。

まず、1手前と比率が同じであった場合
その回をスルーします。
高橋君、もしくは青木君の票数を変えずに条件を満たすことができる場合
つまり、 $T \ mod \ t_{i} = 0$ かつ $a_{i} \times (T/ t_{i}) \geqq A$ となる場合、もしくは $t(T)$ と $a(A)$ を入れ替えたパターンが成り立つ場合です。
これは素直に $A = a_{i} \times (T/ t_{i})$ とすればよいです。
それ以外
$(T/t_{i} + 1) t_{i}$ と $(A/a_{i} + 1) a_{i}$ を計算します。
高橋君の票数が前者の値になるか、青木君の票数が後者の値になるか、の2択です。
まずは、票数が減るパターン、すなわち
$(T/t_{i} + 1) a_{i} \lt A$ 、もしくは $(A/ a_{i}+1)t_{i} \lt T$ となるパターンを排除します。これらのパターンになってしまった場合は、そうならない方を選択する必要があります。
これらのパターンにならない場合は、二人の票数を改めて計算し、票数が少なる方を選択すれば答えとなります。

想定解の提出コード2は、すごい綺麗な解法です。
$A \geqq k a_{i}$ かつ $T \geqq kt_{i}$ が成り立つ最小の $k$ を求めればよいので、
$k = max((A+a_{i} -1 )/a_{i} , (T+t_{i} - 1)/t_{i})$
を求めていけばよいです。
これを $N$ 回繰り返せば、あとは $A,T$ を計算して答えとなります。