[AtCoder] C - AtCoDeerくんと選挙速報 / AtCoDeer and Election Report - ヤマカサのプログラミング勉強日記

問題

beta.atcoder.jp

二分探索を使って解きましたが、数値が大きいのでPythonを使いました。

考え方

$x = T_1$ 、 $y = A_1$ とします。

互いに素という条件から、最初の投票数は $x + y$ となります。

次の得票数の比は、整数 $k_1, k_2$ を用いて次のように表現できます。

$x + k_1 : y + k_2 = T_2 : A_2$

この関係から、

$(x + k_1)A_2 = (y + k_2)T_2$

互いに素という条件から、整数 $m$ を用いて、

$k_1 = mT_2 - x$

$k_2 = mA_2 - y$

と表現できます。

ここで、 $k_1, k_2$ は前回の投票の比から増加した各投票数なので、 $0$ 以上でなければなりません。

したがって、 $k_1 \geq 0$ と $k_2 \geq 0$ を満たす最小の $m$ を求めれば良いことが分かります。

実現可能な $m$ の最小値は $1$ で投票数が増加していないことを表します。

$m$ を $1$ から一つずつ増やして調べると、時間が掛かってしまうので、 $m$ について二分探索を行います。

下限は $1$ ですが、上限は問題文の上限からある程度設定することができます。僕は試行錯誤で求めました。

あとはこれを $N$ まで繰り返します。

コード

N = int(input())
A = list()
T = list()

for i in range(N):
    x, y = map(int, input().split())
    A.append(x)
    T.append(y)

x = T[0]
y = A[0]

for i in range(1, N):
    k1 = T[i] - x
    k2 = A[i] - y
    if k1 == 0 and k2 == 0:
        continue

    l = 0
    r = 1000000000000000000
    mid = 0
    t1 = k1
    t2 = k2
    while r - l > 1:
        mid = (r + l) // 2
        k1 = T[i] * mid - x
        k2 = A[i] * mid - y
        if k1 == 0 and k2 == 0:
            t1 = 0
            t2 = 0
            break
        if k1 >= 0 and k2 >= 0:
            t1 = k1
            t2 = k2
            r = mid
        else:
            l = mid
    x += t1
    y += t2
    # print("%d %d" % (x, y))

print(x + y)