abc192

NISHIO Hirokazu [Translate]
ABC192
5問でした
F: 解説通りのDPしたけどPythonではTLEだったんだい(WAも残ってたのでそれどころではない
微増。精進しなければ伸びることはないか。

B - uNrEaDaBlE sTrInG
pythondef main():
    S = input().strip().decode('ascii')
    from string import ascii_uppercase, ascii_lowercase
    if all(c in ascii_uppercase for c in S[1::2]) and all(c in ascii_lowercase for c in S[::2]):
        print("Yes")
    else:
        print("No")

C - Kaprekar Number
制約を眺めて、高々10桁で、10^5回だったら文字列を使ってOKと判断した
pythondef main():
    N, K = map(int, input().split())
    for _i in range(K):
        s = str(N)
        g1 = int("".join(sorted(s, reverse=True)))
        g2 = int("".join(sorted(s)))
        N = g1 - g2

    print(N)

D - Base n
考えたこと
1桁の時、何進法でも値は変わらない、0か1通り
2桁以上の時、nを増やすと必ず値が増えるので、ようはM以下の条件を満たす最大のnを見つける問題
最悪ケースを考えると入力が10の時、最大で10^18進法になる
→線形探索はダメ
二分探索で良さそう
実装
intのbase指定を使おうとしたんだけど、36進法までしか対応してなかった
 int(s, base) を自前で実装しようとしたが、何も正確に数を求めなくてもMを超えてるかどうかだけ知れれば良い、と考え直した
自前実装してたらTLEしてたと思う
二分探索チェックリストを見て実装
WA
チェックリスト見てたのに失敗パターン4の「rightの初期値が条件を満たしてる」をやってしまった
初期値をMにしてたけど入力が10の時Mは条件を満たしてる、M+1にすべき( # (1) )
pydef lessEqual(s, base, limit):
    ret = 0
    for c in s:
        ret *= base
        ret += int(c)
        if limit < ret:
            return False
    return True


def solve(X, M):
    sX = str(X)
    if len(sX) == 1:
        if X <= M:
            return 1
        else:
            return 0

    d = max(int(c)for c in str(X))
    v = int(sX, d + 1)
    if M < v:
        return 0

    left = d + 1
    start = left
    right = M + 1  # (1)

    while left < right - 1:
        x = (left + right) // 2
        if lessEqual(sX, x, M):
            left = x
        else:
            right = x
    return right - start
Twitterで見かけた案
Xがw+1桁で、baseがbの時、 int(X, b) はx_1b^w + x_2b^{w-1} + \cdots \ge x_1b^w
M \ge x_1b^wを解いて \exp(\log(M / x_i) / w) \ge b、bを線形探索で見つければ良い、というもの
残念ながらこの問題条件の範囲だと倍精度浮動小数点数で精度が足りない
 10 ** 18 - exp(log(10 ** 18)) == 1408.0 
10 ** 18は64ビット弱あるが、倍制度浮動小数点数の仮数部は52ビット。

E - Train
考えたこと
距離があらかじめ決まってないダイクストラだね
ダイクストラ法ではある頂点にたどり着く最速の時間が決まってから他の頂点への時間を計算する
今回の問題では最初は距離が決まってないけど、到着時刻が決まれば隣の街にいつ着くのかは決まる
実装
TとKを取り違えたり、発車までの時間 -currentTime % K を currentTime % K にしてたりでデバッグに時間がかかった # (1) 
pydef one_to_one(
        start, goal, num_vertexes, edges,
        INF=9223372036854775807, UNREACHABLE=-1):
    distances = [INF] * num_vertexes
    distances[start] = 0
    queue = [(0, start)]
    while queue:
        d, frm = heappop(queue)
        if distances[frm] < d:
            # already know shorter path
            continue
        if frm == goal:
            return d
        for to, T, K in edges[frm]:
            # distance depends on currentTime
            currentTime = distances[frm]
            dist = (-currentTime % K) + T  # (1)
            new_cost = currentTime + dist
            if distances[to] > new_cost:
                # found shorter path
                distances[to] = new_cost
                heappush(queue, (distances[to], to))

    return UNREACHABLE

def main():
    N, M, X, Y = map(int, input().split())
    from collections import defaultdict
    edges = defaultdict(list)
    for _m in range(M):
        A, B, T, K = map(int, input().split())
        edges[A - 1].append((B - 1, T, K))
        edges[B - 1].append((A - 1, T, K))

    INF = 9223372036854775807
    r = one_to_one(X - 1, Y - 1, N, edges, INF)
    if r == INF:
        r = -1
    print(r)

F - Potion
考えたこと
最初「X以上」と勘違いしてた
しかしそれだと全部正なんだから全部入れるのが自明な解になる
おかしいとおもったら「ちょうどX」だった
k個選んでSとした時に\sum_{i\in S} A_i \equiv X \pmod{k}であることが必要
Aの部分集合全部について考えると2^50になって間に合わない
DPで状態を押しつぶす
今までに選んだ個数n、最終的に選ぶ個数k、今までの和Vとして (n, k, V % k) -> V のテーブルを最大値で更新すれば良い
最大以外のものは答えに影響しないから
それぞれ1〜100なのでテーブルサイズ10^6、更新回数100、合わせて10^8かー、ギリギリだなぁ
実装
サンプルは通ったが6WA 14TLE
WAのまま高速化してもデバッグが面倒になるだけ
バグを直したが未だ9WA 11TLE、ここでタイムアウト
公式解説
方針は違わないな
ACの人と比較
あー、これ2回目の提出の時に「バグを直して、軽く高速化」ってやって、その高速化でバグを入れてるじゃん
複数の変更を一度にしてはいけない、ソフトウェア開発の基本だぞー
バグを直して15TLE
添え字をタプルから整数に直して11TLE
辞書をリストに直して…あ、そうかこれ更新の順番に気をつけないといけなくて、辞書を二つ使ってたのか、それは遅いな
整数にパックする順番を工夫して大きい方から更新すれば問題が起きないようにし、リストにした、AC
pythondef solve(X, AS):
    from collections import defaultdict
    INF = 9223372036854775807
    N = len(AS)

    def to_key(mod, num, k):
        return num * (N + 1) * (N + 1) + k * (N + 1) + mod

    def from_key(key):
        num, km = divmod(key, (N + 1) * (N + 1))
        k, mod = divmod(km, N + 1)
        return (mod, num, k)

    SIZE = (N + 1) ** 3
    table = [-1] * SIZE
    sumAS = sum(AS)
    for k in range(1, N + 1):
        table[to_key(0, 0, k)] = 0

    for a in AS:
        for key in reversed(range(SIZE)):
            if table[key] == -1:
                continue
            mod, num, k = from_key(key)
            v = table[key] + a
            num += 1
            if num > k:
                continue
            mod = v % k
            key = to_key(mod, num, k)
            table[key] = max(table[key], v)

    ret = INF
    for key in range(SIZE):
        if table[key] == -1:
            continue
        mod, num, k = from_key(key)
        if num == k and num > 0:
            v = table[key]
            if mod == X % k:
                assert (X - v) % k == 0
                s = (X - v) // k
                ret = min(ret, s)

    return ret
1942msか…際どいな
これで問題ならキーの変換関数をインライン展開するとかかな…
他の人のコードを読む
あーなるほど、kの大きい(つまり増加速度の速い)方からチェックしていって、全部取っても無理になったらbreakする手があるのか a2stnk
まずkごとに分けることで1238msまで減る
そして枝刈りを追加することでなんと331msに！
Pythonの中で3位の速さになった
この枝刈りがとてもよく効くということか
"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, 5:14:55 PM[Edit]
Related Pages
