ABC189

I don’t think I’ll grow if I just enter a contest once a week without doing any diligence, so from this time onward, if I have extra time, I’ll solve one blue problem instead of writing an explanation first. approach to make the number of problems in ABC seven on its own. ABC110D

I only solved 4 questions because I couldn’t solve the TLE in E. I thought I was going to fall into light blue, but I stayed on.

B - Alcoholic

Compare large and small floating point numbers, I didn’t want to get into it with errors, so I multiplied by 100 and made it an integer. 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

I was not sure if 10^8 could be solved in time, so I wondered if I should divide the region in order from the smallest value. I thought about it, but I felt it was too difficult, so I put it on hold and solved D first.
When I come back and think about it again, I think I can lighten the content even 10^8, so let’s give it a try.
- 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

Think about how it changes when you add one more term.
- When AND is used, the number of cases does not increase because “the term to be increased must also be True”.
- When it is OR, it increases about 2^i because “when the term to be increased is True, it is True regardless of the past situation”.

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

At first I only followed the changes between (1, 0) and (0, 1).
The sample didn’t fit and I said, “Oops, there’s a transformation that shifts the origin, so I’ll have to set it to asymmetric matrix.”
Change of policy to go the route of using Numpy
I couldn’t get a TLE and it ate up a lot of time. 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 problem can be calculated all by simulating only 3 points (0,0),(1,0),(0,1) / With this solution, it takes 200ms for C and 1400ms for pypy, but it seems that the solution using the cumulative product of the transformation matrix of the affine transformation will take about 2100ms for pypy to TLE -. src
  - that’s exactly what (somebody) is doing
If you write your own matrix calculations and submit them on PyPy AC
- If you’re repeatedly multiplying small matrices, you have a lot of overhead and little benefit from using 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]
    ]

- I'm confident that if I were writing during the contest, I'd be unnerved by the indexing errors and bugs." [src](https://twitter.com/kyasbal_1994/status/1353568891046223872)
    - Of course, I had the program write it (...)

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

Solution equivalent to the linear equation DP in the official explanation
I used the time in E and implemented it just in time with 20 minutes left, so I couldn’t get the bug and noSub
The basics go like this
$f (i) = 1 + \frac{1}{M} \sum_{j = 1}^{M} f (i + j)$
Exception: when i in AS
$f (i) = f (0)$
If $x = f (0)$ , then f(i) is of the form ax + b, so DP this coefficient
If we finally obtain $f (0) = a x + b$ :.
$f (0) = a f (0) + b$
$(1 - a) f (0) = b$
$f (0) = b / (1 - a)$
In the production, I tried to speed up the cumulative sum from the beginning, but it was buggy, so I’ll start with a simple description. The following is a sample 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])

Rewritten and submitted to cumulative sum, 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])

This is due to unreachable checks being missed, so seriously check the AC

This page is auto-translated from /nishio/ABC189 using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.

🪴 Quartz 4.0

ABC189

Graph View

Backlinks