山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

[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)