ABC189

NISHIO Hirokazu [Translate]
ABC189
何も精進しないで週に一回コンテストに出るだけでは成長するわけがないと思うので、今回以降は時間が余ったら、解説を先に書くのではなく、青の問題を1問解くことにしよう。ABCの問題数を勝手に7問にするアプローチ。 ABC110D


EのTLEが解決しなくて4問しか解けなかった。水色に落ちるかと思ったが踏みとどまった。

B - Alcoholic
浮動小数点数の大小比較、誤差でハマるのが嫌なので100倍して整数にした
pythondef main():
    N, X = map(int, input().split())
    X *= 100
    total = 0
    for i in range(N):
        V, P = map(int, input().split())
        total += V * P
        if total > X:
            print(i + 1)
            return
    print(-1)

C - Mandarin Orange
10^8が間に合うかどうか不安で、値の小さい方から順に領域を分割していくか？と考えたが、難しく考えすぎな気がしたので一旦保留して先にDを解いた
戻ってきてから改めて考えると、10^8でも中身を軽くできそうだから試してみよう
646ms AC
pythondef main():
    N = int(input())
    AS = list(map(int, input().split()))
    ret = max(AS)
    for i in range(N):
        maxA = AS[i]
        width = 1
        for j in range(i + 1, N):
            if AS[j] < maxA:
                maxA = AS[j]
            width += 1
            v = maxA * width
            if v > ret:
                ret = v
    print(ret)

D - Logical Expression
1つ項を増やした時にどう変化するか考える
ANDの時には「増やす項もTrueでなければならない」から場合の数が増えない
ORの時は「増やす項がTrueの時、過去の状況に関係なくTrue」なので2^iくらい増える

pythondef main():
    N = int(input())
    prev = 1
    for i in range(N):
        S = input().strip().decode('ascii')
        if S == "OR":
            prev = prev + (2 ** (i + 1))

    print(prev)

E - Rotate and Flip

最初(1, 0)と(0, 1)の変化だけ追ってた
サンプルが合わなくて「おっと、原点がズレる変換があるから斉次行列にしなきゃダメか」
Numpyを使う路線に方針転換
TLEが取れなくて時間を食いつぶしてしまった。
pythondef main():
    N = int(input())
    XY = []
    for _i in range(N):
        XY.append(tuple(map(int, input().split())))
    M = int(input())

    timeline = []
    for i in range(M):
        timeline.append(((i + 1) * 2, tuple(map(int, input().split()))))

    Q = int(input())
    QS = []
    for i in range(Q):
        q = tuple(map(int, input().split()))
        QS.append(q)
        timeline.append((q[0] * 2 + 1, q))
    timeline.sort()

    answer = {}
    trans = np.eye(3, dtype=np.int64)

    OP1 = np.array([
        [0, -1, 0],
        [1, 0, 0],
        [0, 0, 1]], dtype=np.int64)
    OP2 = np.array([
        [0, 1, 0],
        [-1, 0, 0],
        [0, 0, 1]], dtype=np.int64)
    OP3 = np.array([
        [-1, 0, 0],
        [0, 1, 0],
        [0, 0, 1]], dtype=np.int64)
    OP4 = np.array([
        [1, 0, 0],
        [0, -1, 0],
        [0, 0, 1]], dtype=np.int64)
    for t, x in timeline:
        if t % 2:
            # query
            q = x
            i = q[1] - 1
            x, y = XY[i]
            newXY = np.array([x, y, 1]).dot(trans)
            answer[q] = (newXY[0], newXY[1])
        else:
            # ops
            if x[0] == 1:
                trans = trans.dot(OP1)
            elif x[0] == 2:
                trans = trans.dot(OP2)
            elif x[0] == 3:
                P = x[1]
                OP3[2, 0] = 2 * P
                trans = trans.dot(OP3)
            elif x[0] == 4:
                P = x[1]
                OP4[2, 1] = 2 * P
                trans = trans.dot(OP4)

    for q in QS:
        x, y = answer[q]
        print(int(x), int(y))
Twitter
>E問題は、(0,0),(1,0),(0,1)の3点だけシミュレーションすれば全部計算できる/この解法ならCで200ms、pypyで1400msだけど、アフィン変換の変換行列の累積積を使う解法だとpypyでも2100msくらいでTLEになるみたいだねー。src
まさにそれ
行列計算を自前で書いてPyPyで出したらAC
小さな行列の掛け算を繰り返す場合、Numpyを使ってもオーバーヘッドが大きくてメリット少ないのだな
pythondef dot(a, b):
    return [
        a[0] * b[0] + a[1] * b[3] + a[2] * b[6],
        a[0] * b[1] + a[1] * b[4] + a[2] * b[7],
        a[0] * b[2] + a[1] * b[5] + a[2] * b[8],
        a[3] * b[0] + a[4] * b[3] + a[5] * b[6],
        a[3] * b[1] + a[4] * b[4] + a[5] * b[7],
        a[3] * b[2] + a[4] * b[5] + a[5] * b[8],
        a[6] * b[0] + a[7] * b[3] + a[8] * b[6],
        a[6] * b[1] + a[7] * b[4] + a[8] * b[7],
        a[6] * b[2] + a[7] * b[5] + a[8] * b[8]
    ]
「絶対コンテスト中書いてたらインデックスミスってバグって無気力になる自信ある。」src
もちろんプログラムに書かせた()
pythondef gen_dot():
    for i in range(9):
        x, y = divmod(i, 3)
        print(
            f"a[{x * 3}] * b[{y}] + "
            f"a[{x * 3 + 1}] * b[{y + 3}] + "
            f"a[{x * 3 + 2}] * b[{y + 6}],")

F - Sugoroku2

公式解説の一次式DPに相当する解法
Eで時間を使って残り20分でギリギリ実装したのでバグが取れずnoSub
基本はこう
f(i) = 1 + \frac{1}{M} \sum_{j=1}^Mf(i+j)
例外: i in ASの時
f(i) = f(0)
x = f(0)とするとf(i)はax + bの形になる、なのでこの係数をDPする
最終的に f(0) = ax + b が得られたら:
f(0) = a f(0) + b
(1 - a)f(0) =  b
f(0) =  b / (1 - a)
本番では最初から累積和高速化をやろうとしてバグらせたのでまずは素朴に書く。下記でサンプルAC
pythondef solve(N, M, K, AS):
    setA = set(AS)
    table = [0] * (N + M + 1)
    tableF = [0] * (N + M + 1)

    for i in range(N - 1, -1, -1):
        if i in setA:
            table[i] = 0
            tableF[i] = 1
        else:
            v = 0
            f = 0
            for j in range(1, M + 1):
                v += table[i + j]
                f += tableF[i + j]
            table[i] = v / M + 1
            tableF[i] = f / M

    if tableF[0] == 1:
        return -1
    return table[0] / (1 - tableF[0])
累積和に書き換えて提出、3WA
pythondef solve(N, M, K, AS):
    setA = set(AS)
    table = [0] * (N + M + 1)
    tableF = [0] * (N + M + 1)
    sumTable = 0
    sumTableF = 0
    for i in range(N - 1, -1, -1):
        if i in setA:
            table[i] = 0
            tableF[i] = 1
        else:
            v = sumTable
            f = sumTableF
            table[i] = v / M + 1
            tableF[i] = f / M

        sumTable += table[i] - table[i + M]
        sumTableF += tableF[i] - tableF[i + M]

    if tableF[0] == 1:
        return -1
    return table[0] / (1 - tableF[0])
これは到達不能のチェックに取りこぼしがあるせいなので真面目にチェックしてAC
"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:15:05 PM[Edit]
Related Pages
