wrap up

AB can be solved with haste, but C cannot be solved for the rest of his life. The weakness of "DP cannot be solved", which was postponed, has come out clearly ...

If you aim for green to blue in the future, I want to make sure that this C problem can be solved.

To that end, we will solve the combinatorial optimization of AOJ (https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1)! !!

Takahashi is trying to register as a member of a certain Web service. First I tried to register the ID as $ S $. However, this ID was already in use by another user. Therefore, Mr. Takahashi considered registering a character string with one character added to the end of $ S $ as an ID. Takahashi is trying to register a new ID as $ T $. Determine if this meets the above conditions.

You just have to check if T [: -1] with the trailing character of T removed matches S. For the time being, it also checks the number of characters so that it does not pass the dangerous input [^ 1] such as S =" "T =" " `.

s = input()
t = input()
if len(s) + 1 == len(t) and s == t[:-1]:
  print("Yes")
else:
  print("No")

B There are $ A $ cards with> 1 written, $ B $ cards with 0 written, and $ C $ cards with -1 written. When you pick just $ K $ from these cards, what is the maximum possible value as the sum of the numbers written on the cards you picked?

There are three maximum values depending on the value of K.

When K <= A.

――K cards of "1" are very changeable, it's a waste. --The maximum value is when you take K "1" cards, and the maximum value is K.

When A <K <= A + B

--In this case, even if you take A "1" cards, you are obliged to take K-A cards, so you must take "0" cards or "-1" cards for that amount. Fortunately, since K-A <B from the prerequisites, you can score the remaining draw obligations without reducing the maximum value by drawing a "0" card. --The maximum value is A for "1" cards and K-A for "0" cards, and the maximum value is A.

When A + B <K --- I've run out of "1" and "0" cards, so I finally have to deal with the "-1" card (Ed Stafford, who had to eat squeaky in an unexplored life) It's a feeling of). [^ 2] In this case, the number of "-1" cards that must be taken is K- (A + B). --The maximum value is taken when A is a "1" card, B is a "0" card, and K- (A + B) is a "-1" card, and the maximum value is A- (K-). (A + B)).

Since there are at most 3 patterns, let's implement it honestly.

a,b,c,k=[int(i)for i in input().split()]
if k <= a:
  print(k)
elif k<=a + b:
  print(a)
else:
  print(a-(k-a-b))

There are $ N $ towns in the Kingdom of Takahashi. Towns are numbered from $ 1 $ to $ N $. There is one teleporter in each town. The teleporter for town $ i (1 ≤ i ≤ N) $ is forwarded to town $ A_i $. King Takahashi likes the positive integer $ K $. Selfish King Takahashi wants to know which town he will arrive at if he starts from town $ 1 $ and uses the teleporter just $ K $ times. Create a program that asks for this for King Takahashi.

(WA answer)

If you look at the city as a node and the teleport as a directed edge, you can see the directed graph somehow. Then, when I think about it for a moment, I come to the conclusion that "if you repeat teleporting to some extent, you will end up going around an infinite loop in the graph?" "You don't have to simulate that part." I will reach you. That means --Repeat the teleport honestly for the time being. Append and record the searched nodes in the list. --If the searched node is hit during teleportation, the subsequent teleport will be in an infinite loop, so the repeating part can be calculated without simulation. --If you achieve K times before the infinite loop, that's fine. Finish. I thought that the implementation could be ... but the following answer would not only be TLE but also WA.

N,K=[int(i)for i in input().split()]
A = [int(i) for i in input().split()]

#Index to 1 origin
A.insert(0,-1)

accessed_node = set([1])
accessed_node_list=[1]
loop_root = []
loop_madeno_size = 0
loop_size=0
t=1
#Loop detection
for _ in range(1,K+1):
  if not A[t] in accessed_node:
    accessed_node.add(A[t])
    accessed_node_list.append(A[t])
    #Decide the next place
    t=A[t]
  else:
    #Determine the loop path
    loop_start_index=accessed_node_list.index(A[t])
    loop_root = accessed_node_list[loop_start_index:]
    loop_madeno_size = loop_start_index
    loop_size=len(loop_root)
    break
#print(accessed_node)
#print(loop_madeno_size)
if loop_madeno_size <= K:
  print(t)
  exit()
K -= loop_madeno_size
print(loop_root[K%loop_size])

Woo ... I want to solve it after training. Also, this is a slightly faster pattern with PyPy.

Summary

Click here for full answer: https://github.com/Nekomo/AtCoder/tree/master/ABC/167 Combinatorial optimization and DP will be solved by next week! !!

[^ 1]: Dangerous input.

[^ 2]: Romania | The Unexplored Life https://youtu.be/NSwOF_A0LfM

ABC167 WriteUp

wrap up

Summary