AtCoder ABC 175 Python

Summary

ABC was solved. D and E have been set up as a policy, but they cannot be solved in time. This time, I was able to think about the F problem for the first time (whether or not it can be solved is another story ...) E was solved at a later date, but D couldn't crush WA and hasn't AC yet.

problem

https://atcoder.jp/contests/abc175

A. Rainy Season

Answer

S = tuple(input())

if S == ('R', 'R', 'R'):
    print(3)
elif S == ('R', 'R', 'S') or S == ('S', 'R', 'R'):
    print(2)
elif S == ('S', 'S', 'S'):
    print(0)
else:
    print(1)

I wondered if there was a good way to solve it, but I couldn't think of it. I listed them all and solved them with an if statement.

At the time of the contest, I put it in the tuple, but you can judge the character string as it is.

B. Making Triangle

Answer

from itertools import combinations

N = int(input())
L = list(map(int, input().split()))

count = 0
for C in combinations(L, 3):
    l_list = list(C)
    l_list.sort()

    if l_list[2] > l_list[1] and l_list[1] > l_list[0]:
        if l_list[2] < l_list[1] + l_list[0]:
            count += 1

print(count)

Since it is a triangular condition, it can be solved by ``` maximum side <sum of the other two sides` ``. Since the restrictions are small, I have listed them all.

C. Walking Takahashi

Answer

X, K, D = map(int, input().split())

new_X = abs(X) % D
new_K = K - abs(X) // D

if new_K <= 0:
    answer = abs(X) - K*D
else:
    if new_K % 2 == 0:
        answer = new_X
    else:
        answer = abs(new_X - D)
        
print(answer)

First of all, I definitely don't want to use the for statement because the restrictions are too tight. Since we are processing such a large number, we can expect that the process of "dividing a large number by some number" will come somewhere.

With that in mind, I want to divide the coordinates `X``` by the moving distance `Dfor the time being.x // dIf you think about the meaning of, you can see that it is "the number of movements of the distance d required to travel x distance". When it comes to "number of moves", you want to subtract from K```.

Next, experimenting with some input samples, we find that if D is well above X, it oscillates near the origin. It turns out that there are two answers to vibrating.

At this point, the policy has become quite solid.

1. Do `` `K --X // D``` and calculate the remaining number of times
2. Since it vibrates near the origin, divide the two cases and calculate the answer.
3. After that, pay attention to the handling of positive and negative, and handle exceptions when X is sufficiently larger than D.

Drop this into your code.

D. Moving Piece

Answer (This is half WA)

N, K = map(int, input().split())
P = [0] + list(map(int, input().split()))
C = [0] + list(map(int, input().split()))

answer = -float('inf')
for start_p in range(1, N+1):

    cycle_total_score = 0
    cycle_in_score = -float('inf')
    cycle_count = 0
    next_p = P[start_p]
    while True:
        cycle_total_score += C[next_p]
        cycle_in_score = max(cycle_in_score, cycle_total_score)
        cycle_count += 1

        if next_p == start_p:
            # print('start_p:', start_p, ' cycle_total_score:', cycle_total_score, 'cycle_in_score:', cycle_in_score, 'cycle_count:', cycle_count)
            break
        next_p = P[next_p]
    
    max_score = 0
    if K == cycle_count:
        max_score = cycle_in_score
    else:
        #Overflowing K% cycle_Find max to add scores for count times
        add_max_count = K % cycle_count
        add_total_score = 0
        add_score = -float('inf')
        add_count = 0
        add_next_p = P[start_p]
        while True:
            add_total_score += C[add_next_p]
            add_score = max(add_score, add_total_score)
            add_count += 1

            if add_count == add_max_count:
                break
            add_next_p = P[add_next_p]

        if K < cycle_count:
            #Maximum number of trials is cycle_K if less than count% cycle_beak at the best place up to count
            max_score = add_total_score
        else:
            if cycle_total_score >= 0:
                #If one cycle is positive, turn the cycle as much as possible and K% cycle_beak at the best place up to count
                max_score = (K // cycle_count) * cycle_total_score + add_total_score
            else:
                #If one cycle is negative, do not turn the cycle, K% cycle_break at the best place up to count
                max_score = add_total_score
    # print('max_score', max_score)
    answer = max(answer, max_score)

print(answer)

I haven't been able to get AC yet. In the above code, all the test inputs pass, but in production, half is WA. I think the idea is correct, but I haven't been able to identify the cause of WA ...

I don't know what I'm saying if it's just letters, so I draw a diagram. The following is an illustration of Input Example 1.

Given the features of this figure, we can see that one or more graphs with cycles can be created. The policy to solve is to try the whole street honestly.

1. First decide where to start => Try this in N ways
2. Take a round from the start and record the following scores 2.1. Total score for one cycle 2.2. Score at the maximum moment in one cycle 2.3. Number of moves required for one cycle
3. It is easy if K is an integral multiple of the number of movements in one cycle, but there may be halfway times, so in that case I will go to find the score below 3.1. Halfway number 3.2. Score at the maximum of the halfway numbers

Maybe this should solve it, but it hasn't been solved until the end (Isn't it possible to solve it with this?).

E. Picking Goods

Answer (normal version TLE)

R, C, K = map(int, input().split())
scores = [[0] * (C + 1) for _ in range(R+1)]
for _ in range(K):
    r, c, v = map(int, input().split())
    scores[r][c] = v
dp = [[[0] *4 for _ in range(C+1)] for _ in range(R+1)]

for i in range(1, R+1):
    for j in range(1, C+1):
        for k in range(4):
            dp[i][j][k] = max(dp[i][j-1][k],
                              dp[i-1][j][3])
        for k in range(3, 0, -1):
            dp[i][j][k] = max(dp[i][j][k],
                              dp[i][j][k-1] + scores[i][j])

answer = dp[R][C][3]
print(answer)

Answer (speed up ver AC)

from numba import jit
import numpy as np

@jit
def main():
    R, C, K = map(int, input().split())
    scores = np.zeros((R,C), np.int64)
    for _ in range(K):
        r, c, v = map(int, input().split())
        scores[r-1][c-1] = v
    dp = np.zeros((R+1,C+1,4), np.int64)

    for i in range(1, R+1):
        for j in range(1, C+1):
            for k in range(4):
                dp[i][j][k] = max(dp[i][j-1][k],
                                  dp[i-1][j][3])
            for k in range(3, 0, -1):
                dp[i][j][k] = max(dp[i][j][k],
                                  dp[i][j][k-1] + scores[i-1][j-1])

    return dp[R][C][3]

print(main())

I wanted to solve this in time. If you build it normally with Python, the time will not be in time, but if you improve the original code with `numpy``` and `@ jit```, it will pass.

First of all, I read the problem and found out that it was DP. However, I can only solve 2D DP ... For the time being, I will write the DP ignoring the constraint of "up to 3 on the same line". Then it will be as follows. (When visualizing a 2D DP table, using pandas makes it easier to see the vertical and horizontal directions, so pandas and numpy are included for debugging.)

R, C, K = map(int, input().split())
scores = [[0] * (C + 1) for _ in range(R+1)]
for _ in range(K):
    r, c, v = map(int, input().split())
    scores[r][c] = v
dp = [[0] *(C+1) for _ in range(R+1)]

for i in range(1, R+1):
    for j in range(1, C+1):
            dp[i][j] = max(dp[i-1][j] + scores[i][j],
                           dp[i][j-1] + scores[i][j])

print(dp[R][C])

# import numpy as np
# import pandas as pd
# show_dp = np.array(dp)
# show_dp = pd.DataFrame(show_dp)
# print(show_dp)

So far it's easy. (While saying that, it was impossible for me a week ago to come this far, but here in the past week >> [Guidelines for improving competition pros and AtCoder taught by Red Coder [Intermediate Edition: Aim for Light Blue Coder! ]](Https://qiita.com/e869120/items/eb50fdaece12be418faa#2-3-%E5%88%86%E9%87%8E%E5%88%A5%E5%88%9D%E4%B8% AD% E7% B4% 9A% E8% 80% 85% E3% 81% 8C% E8% A7% A3% E3% 81% 8F% E3% 81% B9% E3% 81% 8D% E9% 81% 8E% I can say that because I was solving the DP problem of E5% 8E% BB% E5% 95% 8F% E7% B2% BE% E9% 81% B8-100-% E5% 95% 8F). )

At the time of the contest, it was not possible to incorporate the "up to 3 on the same line" constraint from here. I knew that I should increase the dimension of the dp table by one and do "something", but I couldn't think of this "something".

I will write "When going sideways, add score up to the third time, and do not add anything else" as it is. When I solve dp, I have to actually write the dp table on paper and visualize it, so I can't get an image well, so the 3D dp table doesn't quite fit. Is it a place to get used to rather than learning?

By the way, in python, if you code with dp normally, it will be TLE. As a policy, I think whether to use numpy to calculate the part written in the for statement at once, use pypy, or use jit. It seems that strong people naturally calculate well with numpy, but I can't write that much yet. In this code, even pypy did not pass, so I made it a function and used @jit.

Then, as shown below, "a small amount of calculation is much slower, and a large amount of calculation is much faster", and I managed to pass AC. I don't know why this happens, but if you can't get through with dp for the time being, try jit in the same way.

[For ordinary code]

[For code using @jit]