ABC192

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

def 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と判断した python

def 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)) py

def 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_{1} b^{w} + x_{2} b^{w - 1} + \dots \geq x_{1} b^{w}$
  - $M \geq x_{1} b^{w}$ を解いて $exp (lo g (M / x_{i}) / w) \geq b$ 、bを線形探索で見つければ良い、というもの
- 残念ながらこの問題条件の範囲だと倍精度浮動小数点数で精度が足りない
  - 10 ** 18 - exp(log(10 ** 18)) == 1408.0
  - 10 ** 18は64ビット弱あるが、倍制度浮動小数点数の仮数部は52ビット。

E - Train

考えたこと
- 距離があらかじめ決まってないダイクストラだね
- ダイクストラ法ではある頂点にたどり着く最速の時間が決まってから他の頂点への時間を計算する
- 今回の問題では最初は距離が決まってないけど、到着時刻が決まれば隣の街にいつ着くのかは決まる
実装
- TとKを取り違えたり、発車までの時間-currentTime % KをcurrentTime % Kにしてたりでデバッグに時間がかかった# (1) py

def 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 (mod 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 python

def 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位の速さになった
  - この枝刈りがとてもよく効くということか

🪴 Quartz 4.0

ABC192

Graph View

Backlinks