ABC189

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

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

浮動小数点数の大小比較、誤差でハマるのが嫌なので100倍して整数にした python

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

def 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くらい増える

python

def 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が取れなくて時間を食いつぶしてしまった。 python

def 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を使ってもオーバーヘッドが大きくてメリット少ないのだな python

def 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](https://twitter.com/kyasbal_1994/status/1353568891046223872)
    - もちろんプログラムに書かせた()

python

def 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}^{M} f (i + j)$
例外: i in ASの時
$f (i) = f (0)$
$x = f (0)$ とするとf(i)はax + bの形になる、なのでこの係数をDPする
最終的に $f (0) = a x + b$ が得られたら:
$f (0) = a f (0) + b$
$(1 - a) f (0) = b$
$f (0) = b / (1 - a)$
本番では最初から累積和高速化をやろうとしてバグらせたのでまずは素朴に書く。下記でサンプルAC python

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

def 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

🪴 Quartz 4.0

ABC189

Graph View

Backlinks