ABC193

5問しか解けなかったけど自己ベスト更新でした。

C - Unexpressed

• 表せる数が大した個数ない
• 多くても$\sum {\log }_{i}N[2\le i\le \sqrt{n}]$
  • なので全部数えれば良い
  • 一番多いa=2の時で高々30ちょいで、aは最大で10^5までしかいかないので余裕だと判断できる
  • 追記: 実際に数えた結果102230だった py

def main():
    N = int(input())
    from math import sqrt, floor
    ok = set()
    MAX_A = floor(sqrt(N))
    for a in range(2, MAX_A + 1):
        x = a * a
        while x <= N:
            ok.add(x)
            x *= a

    print(N - len(ok))

D - Poker

• 手札は高々81通りしかないので全部試せば良い py

def main():
    K = int(input())
    S = input().strip().decode('ascii')
    T = input().strip().decode('ascii')
    scount = [0] * 9
    tcount = [0] * 9
    rest = [K] * 9
    for i in range(4):
        s = int(S[i]) - 1
        t = int(T[i]) - 1
        scount[s] += 1
        tcount[t] += 1
        rest[s] -= 1
        rest[t] -= 1

    def calcScore(xs):
        ret = 0
        for i in range(9):
            ret += (i + 1) * (10 ** xs[i])
        return ret

    ret = 0
    for a in range(9):
        if rest[a] == 0:
            continue
        pa = rest[a]
        rest[a] -= 1
        scount[a] += 1

        for b in range(9):
            if rest[b] == 0:
                continue
            pb = rest[b]
            tcount[b] += 1
            if calcScore(scount) > calcScore(tcount):
                ret += pa * pb
            tcount[b] -= 1

        rest[a] += 1
        scount[a] -= 1

    ret /= (9 * K - 8) * (9 * K - 9)
    print(ret)

E - Oversleeping

• 問題文が長くてスクリーンショットに収まらないので割愛
• 要するに周期Nのうちのある範囲でONになるものと、周期Mのうちのある範囲でONになるものがあるときに、両方ONになるもっとも早い時刻を求めよという問題
  • NとMは10^9オーダーなので実際に各周期を試すのは無理
  • しかし、その周期の中でONになってる期間は最大500と小さく制限してある
• 中国剰余定理で「Nで割ってあまりa, Mで割ってあまりb」となる最小の値を対数オーダーで求めることができる
• 500×500の組み合わせ全部について中国剰余定理して、全体での最小を答えれば良い
  • 自分のライブラリ実装はN,Mが互いに素である仮定のものだったけど、今回はそうとは限らないので急いで修正 python

def crt(a, m, b, n):
    """
    Find x s.t. x % m == a and x % n == b

    >>> crt(2, 3, 1, 5)
    11
    >>> crt(1, 4, 3, 6)
    9
    """
    x, y, g = extended_euclidean(m, n)
    if g == 1:
        return (b * m * x + a * n * y) % (m * n)
    s = (b - a) // g
    return (a + s * m * x) % (m * n // g)

def main():
    from math import gcd
    T = int(input())
    for _t in range(T):
        X, Y, P, Q = map(int, input().split())

        m = 2 * X + 2 * Y
        n = P + Q
        ret = INF = 9223372036854775807
        g = gcd(n, m)
        for a in range(X, X+Y):
            for b in range(P, P + Q):
                if a % g == b % g:
                    x = crt(a, m, b, n)
                    ret = min(ret, x)

        if ret == INF:
            print("infinity")
        else:
            print(ret)

✅ABC193F

前回 ARC113