AtCoder Regular Contest 108 - AtCoder C was written with recursive calls and was 21 TLE in PyPy and 16 TLE in raw Python, and with a few minutes left I switched to depth-first search using my own stack, but I bugged it and got a lot of WAs, which I didnāt fix in time.
- Thoughts.
- The range of values is up to 10^12, but finding the divisor is on the square root order, so 10
- Just check if x+P/x=S for all divisors x python
def solve(S, P):
i = 1
while i * i <= P:
if P % i == 0:
s = i + P // i
if S == s:
return "Yes"
i += 1
return "No"
B
- Thoughts.
- A non-nesting FOX can be accepted by an automaton with three states.
- Push the state to the stack if f comes up in the middle of the process.
- Pop the stack when accepted.
- If it is not accepted, all the higher-level āin-processā items are also not accepted, so the stack is cleared.
- Iām making this a mere pop and 1WA. python
def solve(N, S):
i = 0
state = [0]
ret = N
while i < N:
# debug(i, S[i], state, msg=":i, state")
if state[-1] == 0:
if S[i] == "f":
state.append(1)
elif state[-1] == 1:
if S[i] == "o":
state[-1] = 2
elif S[i] == "f":
state.append(1)
else:
state = [0]
elif state[-1] == 2:
if S[i] == "x":
state.pop()
ret -= 3
elif S[i] == "f":
state.append(1)
else:
state = [0]
i += 1
return ret
C
- Thoughts.
- Simple graphs for consideration
- Just trace the appropriate global tree from the root and label the vertex labels with the edge labels from the parent (wrong).
- Are you sure you want to do that?
- Not good, if the same thing comes to the edge label, it will disappear because both ends of the edge are the same.
- Then, for the root and āthe point where the parent label matches the edge label to the parentā, we make the point label āthe object that does not appear in the edge label to the childā.
- 70AC 16TLE
- Official Explanation
- Appropriately labeling roots.
- If you write any number other than that label at āthe point where the parent label matches the edge label to the parent,ā that edge will not disappear.
- If there is no match, write a value equal to the edge label and the edge will not disappear
- If you read the explanation, C is the same up to the point where you can just paint the appropriate tree from the root, but I had a loop for the number of children because I was doing āthe parent should be a number not used for the edge labels to the childrenā and I couldnāt make it in time. In fact, I can make it so that the edge doesnāt disappear on the childās side, even if I decide to do it properly. I see.
- But this still takes 1 TLE.
- I submitted it in raw Python, not PyPy, and I got AC.
- So youāre saying that the slow function call in PyPy was a problematic situation.
- I thought my original method wouldnāt change the order (since each vertex must loop about its connection point), but it looks like Iām losing a constant times slower. python
- Appropriately labeling roots.
def solve(N, M, edges):
vlabel = [None] * N
def f(cur, parentEdge=None, parent=None):
if parentEdge is None:
vlabel[cur] = 1
else:
if parentEdge != parent:
vlabel[cur] = parentEdge
else:
vlabel[cur] = (parentEdge % N) + 1
for child in edges[cur]:
if vlabel[child]:
continue
c = edges[cur][child]
f(child, c, vlabel[cur])
f(0, None, None)
return vlabel
D
- Thoughts.
- Does it make sense for N to be as small as 1000?
- Consider DP
- Not very clear.
- Letās start with the smallest one.
- When AB ā AAB, the initial B remains at length 1, and A can be extended to any length greater than or equal to 2.
- When AB ā ABB, conversely, A remains length 1
- Since the two are symmetrical, consider only the former.
- AA to AAA, one street since only a row of Aās can be created.
- AA to ABA at
- If AB ā AAB and BA ā BAA, the length of inserted B does not increase, so it is always 1
- Iāll think about this calculation later.
- Otherwise, B can also be any length.
- That is, it can be any sequence of length N-3: streets
- If AB ā AAB and BA ā BAA, the length of inserted B does not increase, so it is always 1
- Counting up a sequence of N-3 1/0ās where any zero is a zero, but not a sequence of zeros.
- Combine 1 and 10 to form a column of length N-2
- Choose 0 from N-2, 1 from N-3ā¦ and make it 10.
- as
- Combine 1 and 10 to form a column of length N-2
- Official Explanation
- The sum of these binomial coefficients is the Fibonacci
- Sum of binomial coefficients and Fibonacci
- Iāll combine one forward or two forward to make N-2. python
- The sum of these binomial coefficients is the Fibonacci
- Sum of binomial coefficients and Fibonacci
def solve(N, S):
if N < 4:
return 1
MOD = 1_000_000_007
S = [x[0] - ord("A") for x in S]
AA, AB, BA, BB = 0, 1, 2, 3
A, B = 0, 1
c = Combination(N + 10, MOD)
if S[AB] == A:
# len(B) = 1
if S[AA] == A:
return 1
if S[AB] == A and S[BA] == A:
# inserted B = length 1
M = N - 2
ret = 0
for i in range(M):
if M - i < i:
break
ret += c.comb(M - i, i)
ret %= MOD
return ret
else:
return pow(2, N - 3, MOD)
else:
if S[BB] == B:
return 1
if S[BA] == B and S[AB] == B:
# inserted B = length 1
M = N - 2
ret = 0
for i in range(M):
if M - i < i:
break
ret += c.comb(M - i, i)
ret %= MOD
return ret
else:
return pow(2, N - 3, MOD)
F
- Thoughts.
- Paint the tree, if both ends of the longest path are the same color, it doesnāt matter how the rest of the tree is painted.
- What if it is different?
- Can you make the same argument about a graph with one removed?
- Not likely to make it under this policyā¦
- Cases with half painted over have the lowest scores.
This page is auto-translated from /nishio/ARC108 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.