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.
https://atcoder.jp/contests/abc175
A. Rainy Season
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
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
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.
Drop this into your code.
D. Moving Piece
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.
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
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)
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]
Recommended Posts