ABC193

NISHIO Hirokazu [Translate]
ABC193
5問しか解けなかったけど自己ベスト更新でした。

C - Unexpressed
表せる数が大した個数ない
多くても\sum \log_i N [2 \le i \le \sqrt{n}]
なので全部数えれば良い
一番多いa=2の時で高々30ちょいで、aは最大で10^5までしかいかないので余裕だと判断できる
追記: 実際に数えた結果102230だった
pydef 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通りしかないので全部試せば良い
pydef 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が互いに素である仮定のものだったけど、今回はそうとは限らないので急いで修正
pythondef 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
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at 11/23/2025, 6:17:43 PM[Edit]
Related Pages
