einpacken

AB kann mit Eile gelöst werden, aber C kann für den Rest seines Lebens nicht gelöst werden.

Wenn Sie in Zukunft Grün bis Blau anstreben, möchte ich dieses C-Problem unbedingt lösen.

Zu diesem Zweck werde ich die Kombinationsoptimierung von AOJ lösen (https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1)! !!

Takahashi versucht, sich als Mitglied eines bestimmten Webdienstes zu registrieren. Zuerst habe ich versucht, die ID als $ S $ zu registrieren. Diese ID wurde jedoch bereits von einem anderen Benutzer verwendet. Daher dachte Herr Takahashi darüber nach, eine Zeichenkette mit einem Zeichen am Ende von $ S $ als ID zu registrieren. Takahashi versucht, eine neue ID als $ T $ zu registrieren. Stellen Sie fest, ob dies die oben genannten Bedingungen erfüllt.

Sie müssen nur überprüfen, ob T [: -1] mit dem entfernten nachgestellten Buchstaben von T mit S übereinstimmt. Derzeit wird auch die Anzahl der Zeichen überprüft, damit die gefährliche Eingabe [^ 1] wie "S =" "T =" "` nicht weitergegeben wird.

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

B Es gibt $ A $ Karten mit> 1 geschrieben, $ B $ Karten mit 0 geschrieben und $ C $ Karten mit -1 geschrieben. Wenn Sie nur $ K $ von diesen Karten auswählen, was ist der maximal mögliche Wert als Summe der Zahlen, die auf den von Ihnen ausgewählten Karten geschrieben sind?

Abhängig vom Wert von K gibt es drei Maximalwerte.

Wenn K <= A.

――K-Karten mit "1" sind sehr austauschbar, es ist eine Verschwendung.

Der Maximalwert ist, wenn Sie K "1" -Karten nehmen, und der Maximalwert ist K.

Wenn A <K <= A + B.

In diesem Fall müssen Sie, selbst wenn Sie A "1" -Karten nehmen, K-A-Karten nehmen, daher müssen Sie "0" -Karten oder "-1" -Karten für diesen Betrag nehmen. Glücklicherweise können Sie, da K-A <B aus den Voraussetzungen hervorgeht, die verbleibenden Ziehungsverpflichtungen erzielen, ohne den Maximalwert durch Ziehen einer "0" -Karte zu verringern.
Der Maximalwert ist A für "1" -Karten und K-A für "0" -Karten, und der Maximalwert ist A.

Wenn A + B <K --- Ich habe keine "1" - und "0" -Karten mehr, also muss ich mich endlich mit der "-1" -Karte auseinandersetzen (Ed Stafford, der in einem unerforschten Leben quietschend essen musste) Es ist ein Gefühl von). [^ 2] In diesem Fall ist die Anzahl der "-1" -Karten, die genommen werden müssen, "K- (A + B)".

Der Maximalwert ist A- (K-) für "1" -Karten, B für "0" -Karten und K- (A + B) für "-1" -Karten. (A + B)).

Da es höchstens 3 Muster gibt, lassen Sie es uns ehrlich implementieren.

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

Es gibt $ N $ Städte im Königreich Takahashi. Die Städte sind von $ 1 $ bis $ N $ nummeriert. In jeder Stadt gibt es einen Teleporter. Der Teleporter für die Stadt $ i (1 ≤ i ≤ N) $ wird an die Stadt $ A_i $ weitergeleitet. König Takahashi mag die positive ganze Zahl $ K $. Der egoistische König Takahashi möchte wissen, in welcher Stadt er ankommen wird, wenn er aus einer Stadt mit einem Wert von 1 USD startet und den Teleporter nur K $ mal benutzt. Erstellen Sie hierfür ein Programm für König Takahashi.

(WA Antwort)

Wenn Sie die Stadt als Knoten und den Teleport als gerichtete Kante betrachten, können Sie die gerichtete Grafik irgendwie sehen. Wenn ich dann einen Moment darüber nachdenke, komme ich zu dem Schluss, dass "wenn Sie das Teleportieren bis zu einem gewissen Grad wiederholen, Sie am Ende eine Endlosschleife in der Grafik durchlaufen?" "Sie müssen diesen Teil nicht simulieren." Ich werde dich erreichen. Das bedeutet

Wiederholen Sie den Teleport vorerst ehrlich. Fügen Sie die gesuchten Knoten hinzu und notieren Sie sie in der Liste.
Wenn der gesuchte Knoten während der Teleportation getroffen wird, befindet sich der nachfolgende Teleport in einer Endlosschleife, sodass der sich wiederholende Teil ohne Simulation berechnet werden kann.
Wenn Sie K-mal vor der Endlosschleife erreichen, ist das in Ordnung. Beenden Sie. Ich dachte, dass die Implementierung sein könnte ... aber die folgende Antwort wäre nicht nur TLE, sondern auch WA.

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

#Index zu 1 Ursprung
A.insert(0,-1)

accessed_node = set([1])
accessed_node_list=[1]
loop_root = []
loop_madeno_size = 0
loop_size=0
t=1
#Schleifenerkennung
for _ in range(1,K+1):
  if not A[t] in accessed_node:
    accessed_node.add(A[t])
    accessed_node_list.append(A[t])
    #Entscheide dich für den nächsten Ort
    t=A[t]
  else:
    #Bestimmen Sie den Schleifenpfad
    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 ... ich möchte es nach dem Training lösen. Dies ist auch ein etwas schnelleres Muster mit PyPy.

Zusammenfassung

Klicken Sie hier für die vollständige Antwort: https://github.com/Nekomo/AtCoder/tree/master/ABC/167 Kombinierte Optimierung bis nächste Woche, ich werde eine Menge DP lösen! !!

[^ 1]: Gefährlicher Eingang.

[^ 2]: Rumänien | Das unerforschte Leben https://youtu.be/NSwOF_A0LfM

[PYTHON] ABC167 WriteUp

einpacken

Zusammenfassung