The title says Python, but I can't make it in time without using PyPy. ** It's a title scam by all means. I'm really thankful to you. ** ** ~~ Uruse, use PyPy ~~
** Thoughts ** A similar problem appeared in ABC recently. The big difference between the past question and this question is whether the shape of the graph is like 6 or a circle. Since the past question was like 6, it was necessary to record the timing of entering the cycle. However, the problem this time is that the shape of the graph is a circle.
Why a given graph has a cycle (cycle): If a given graph has no cycles, then the graph becomes a tree, and there are nodes that have no child nodes (nodes that have no destination). However, since $ P $ is a permutation of $ N $ according to the condition, there is no child node ($ P_i $ is empty). So the graph given has a cycle
Why the given graph shape is a circle: Suppose the shape of the given graph is not a circle. The graph given above has a cycle. The starting point of a non-circular cycle is connected to two nodes (the destination is the same ⇔ $ P_i = P_j (i \ neq j) $ exists). However, according to the condition, the elements of $ P $ are permutations of $ N $, so the elements of $ P $ are not compounded. Therefore, since there is no point connected to two or more points, the given graph is a circle.
When examining the cycle, I think it is easy to create and update the searched list that is used in DFS etc.
All you have to do is process the score. At first, I thought that I should update it with (when I go around as many times as I can + when I move the maximum mass with the remaining number of times, when there is only one lap). I melted it for about 2 hours without noticing this lie. If this is the case, it will fail in the following test case.
3 6
2 3 1
5 5 -9
The graph loops 1 → 2 → 3 → 1. The first idea is 3 → 2 → 1 and the answer is 10. This is wrong and the correct answer is 11. The correct answer for this case is 3 → 1 → 2 → 3 → 1 → 2. The first idea is to choose between 2 laps + 1 square or 2 squares. In the case of 2 laps + 1 square, it will be 7, and in the case of 2 squares, it will be 10 as above. The correct answer is 1 lap + 2 squares.
Therefore, the correct update is (when you go around as many times as you can + the maximum number of squares moves, when you only make one lap, ** you go around as many times as you can -1 + the maximum number of times you move ** When). All you have to do is implement it.
The initial value of ans is -inf because 0 moves will be the answer when the answer is negative.
n, k = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
ans = -float('inf')
for i in range(n):
score = []
check = [0] * n
now = i
cycle = 0
for _ in range(k):
go = p[now] - 1
if check[go] == 1:
break
now = go
if len(score) == 0:
score.append(c[now])
else:
score.append(score[-1] + c[now])
check[now] = 1
cycle += 1
t = k // cycle
m = k % cycle
sum_cycle = score[-1]
if m == 0:
ans = max(sum_cycle * t, sum_cycle * (t - 1) + max(score), max(score), ans)
else:
ans = max(sum_cycle * t + max(score[:m]), sum_cycle * (t - 1) + max(score), max(score), ans)
print(ans)
Thank you to Ryuki for sharing the test case. It was a fun problem. See you again, good night.
3 7
— Ryuki (@e145755) August 16, 2020
2 3 1
5 5 -9
Recommended Posts