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
https://gyazo.com/d234f81a5294e5b0a658e36ec971f2f3
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.
https://gyazo.com/16f946ef228f369f1a0dbf3f3c007f89
B - Alcoholic
https://gyazo.com/eb68cd541517250df77564e56374120f
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.
code: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
https://gyazo.com/2f0680970cbdbd53b9343c2020e5d1fa
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
code:python
def main():
N = int(input())
AS = list(map(int, input().split()))
ret = max(AS)
for i in range(N):
maxA = ASi
width = 1
for j in range(i + 1, N):
if ASj < maxA:
maxA = ASj
width += 1
v = maxA * width
if v > ret:
ret = v
print(ret)
D - Logical Expression
https://gyazo.com/fd1d24b429cec954a5df9d2257d212a9
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".
https://gyazo.com/f76f3dc694e4fcbd5f14cbcea8e9a8ba
code: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
https://gyazo.com/9bb7f06e46fed0c174035ca151c9a7a4
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.
code: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((q0 * 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 = q1 - 1
x, y = XYi
newXY = np.array(x, y, 1).dot(trans)
answerq = (newXY0, newXY1)
else:
# ops
if x0 == 1:
trans = trans.dot(OP1)
elif x0 == 2:
trans = trans.dot(OP2)
elif x0 == 3:
P = x1
OP32, 0 = 2 * P
trans = trans.dot(OP3)
elif x0 == 4:
P = x1
OP42, 1 = 2 * P
trans = trans.dot(OP4)
for q in QS:
x, y = answerq
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.
code:python
def dot(a, b):
return [
a0 * b0 + a1 * b3 + a2 * b6,
a0 * b1 + a1 * b4 + a2 * b7,
a0 * b2 + a1 * b5 + a2 * b8,
a3 * b0 + a4 * b3 + a5 * b6,
a3 * b1 + a4 * b4 + a5 * b7,
a3 * b2 + a4 * b5 + a5 * b8,
a6 * b0 + a7 * b3 + a8 * b6,
a6 * b1 + a7 * b4 + a8 * b7,
a6 * b2 + a7 * b5 + a8 * b8
]
I'm confident that if I were writing during the contest, I'd be unnerved by the indexing errors and bugs." src
Of course, I had the program write it (...)
code: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
https://gyazo.com/c98e3a76d7f6ec84fb0970d0d5686351
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}^Mf(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) = ax + 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
code: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:
tablei = 0
tableFi = 1
else:
v = 0
f = 0
for j in range(1, M + 1):
v += tablei + j
f += tableFi + j
tablei = v / M + 1
tableFi = f / M
if tableF0 == 1:
return -1
return table0 / (1 - tableF0)
Rewritten and submitted to cumulative sum, 3WA
code: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:
tablei = 0
tableFi = 1
else:
v = sumTable
f = sumTableF
tablei = v / M + 1
tableFi = f / M
sumTable += tablei - tablei + M
sumTableF += tableFi - tableFi + M
if tableF0 == 1:
return -1
return table0 / (1 - tableF0)
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.