[Python] ABC175D

Since Pi! = I and P1, P2, ..., PN are all different, it is a loop that always returns to the starting point no matter where you start. From N ≤ 5000, even if the loop path is found for all the starting points, the worst is O (N ^ 2), and it seems that it will be somehow in time. Therefore, consider it as the starting point s below. For each s, follow the steps below.

Step1 1st point → 2nd point → ・ ・ ・ → For the loop of s (last point), find the cumulative sum S of points. Step2 The maximum value of the score is calculated by classifying the cases according to the magnitude of K and len (S). The cases are as follows.

Step2-Case A: When K ≤ len (S):

Since the loop is not done for one week, the maximum value of S at the reachable point is the answer.

Step2-Case B: When K> len (S):

When S [-1] ≤ 0, there is no merit for more than one week, so the maximum value up to one week, that is, the maximum value of S is the answer. When S [-1]> 0, you want to turn as much as you can, but in fact, the score may be higher if you turn one lap less, so calculate and compare the scores in both cases.

Reference: [Python] ABC175 Explanation

Sample code


N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))

ans = -float('inf')
for s in range(N):
    ### Step1
    S = []  #Cumulative sum list in loop S.However,The first term is not 0 but the score after the first move.
    #1st move
    i = P[s] - 1
    S.append(C[i])
    #Second and subsequent moves.Repeat until you return to the starting point.
    while i != s:
        i = P[i] - 1
        S.append(S[-1] + C[i])

    ### Step2:Separate cases according to the length of K and S,Find the maximum score.
    #If you can move less than one lap:
    if K <= len(S):
        score = max(S[:K])
    #It can exceed one lap,When the score decreases when one lap of the loop:
    elif S[-1] <= 0:
        score = max(S)
    #Can exceed one week,And if the score increases every week in the loop:
    else:
        #Loop(K // len(S) - 1)When turning:
        score1 = S[-1] * (K // len(S) - 1)
        score1 += max(S)
        #Loop(K // len(S))When turning:
        score2 = S[-1] * (K // len(S))
        r = K % len(S)
        if r != 0:
            score2 += max(0, max(S[:r]))
        #The larger score1 and score2 is the maximum score in this case.
        score = max(score1, score2)

    ans = max(ans, score)

print(ans)

Recommended Posts

[Python] ABC175D
[Python] DP ABC184D
[Python] UnionFind ABC177D
Solve ABC168D in Python
Solve ABC167-D in Python
Python
[Python] Cumulative sum ABC186D
[Python] Binary search ABC155D
Solve ABC159-D in Python
[Python] Dynamic programming ABC015D
[Python] Cumulative sum ABC179D
[Python] BFS (breadth-first search) ABC168D
ABC161D Lunlun Number with python3
[Python] DFS (Depth-first Search) ABC157D
kafka python
Python basics ⑤
python + lottery 6
Python Summary
Built-in python
Python technique
Studying python
Python 2.7 Countdown
Python memorandum
python tips
python function ①
Python basics
Python memo
ufo-> python (3)
[Python] How to derive nCk (ABC156-D)
install python
Python Singleton
Python basics ④
Python Memorandum 2
python memo
Python Jinja2
Python increment
atCoder 173 Python
[Python] function
Python installation
python tips
Installing Python 3.4.3.
Try python
Python iterative
Python algorithm
Python2 + word2vec
[Python] Variables
Python functions
Python sys.intern ()
Python tutorial
Python decimals
python underscore
Start python
[Python] Sort
Note: Python
python log
Python basics
[Scraping] Python scraping
Python update (2.6-> 2.7)
python memo
Python memorandum
Python # sort