Solve ABC175 D in Python

Introduction

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 ~~

D - Moving Piece

** 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)

at the end

Thank you to Ryuki for sharing the test case. It was a fun problem. See you again, good night.

Recommended Posts

Solve ABC175 D in Python
Solve ABC169 in Python
ABC 157 D --Solve Friend Suggestions in Python!
Solve ABC165 A, B, D in Python
Solve ABC176 E in Python
Solve ABC036 A ~ C in Python
Solve ABC037 A ~ C in Python
Solve ABC175 A, B, C in Python
Solve ABC168D in Python
Solve ABC167-D in Python
Solve ABC146-C in Python
Solve ABC098-C in Python
Solve ABC159-D in Python
I wanted to solve ABC159 in Python
Solve AtCoder ABC168 with python (A ~ D)
Solve ABC160-E in Python
Solve AtCoder ABC166 with python
Atcoder ABC164 A-C in Python
Atcoder ABC167 A-D in Python
Solve Wooldridge exercises in Python
Atcoder ABC165 A-D in Python
Atcoder ABC166 A-E in Python
AtCoder ABC 182 Python (A ~ D)
Solve optimization problems in Python
Solve AtCoder ABC 186 with Python
Atcoder ABC169 A-E in Python
AtCoder ABC177 A-D in python
Solve addition (equivalent to paiza rank D) in Python
Solve multiplication (equivalent to paiza rank D) in Python
Solve Atcoder ABC176 (A, B, C, E) in Python
Solve ABC163 A ~ C with Python
ABC166 in Python A ~ C problem
Solve ABC168 A ~ C with Python
Solve ABC162 A ~ C with Python
Solve ABC167 A ~ C with Python
Solve ABC158 A ~ C with Python
Solve ordinary differential equations in Python
Solve number sorting (equivalent to paiza rank D) in Python
Solve with Ruby and Python AtCoder ABC133 D Cumulative sum
Solve character matches (equivalent to paiza rank D) in Python
AtCoder ABC151 Problem D Speed comparison in C ++ / Python / PyPy
Beginner ABC154 (Python)
Quadtree in Python --2
Python in optimization
CURL in python
[Python, Julia] 3D display in Jupyter-Mayavi library
Beginner ABC156 (Python)
Metaprogramming in Python
Python 3.3 in Anaconda
Geocoding in python
SendKeys in Python
Meta-analysis in Python
Unittest in python
AtCoder ABC 174 Python
Algorithm in Python (ABC 146 C Binary Search
AtCoder ABC187 Python
Epoch in Python
Sudoku in Python
DCI in Python
quicksort in python
nCr in python