emballer

AB peut être résolu à la hâte, mais C ne peut pas être résolu pour le reste de sa vie. La faiblesse de "DP ne peut pas être résolue" qui avait été reportée est clairement apparue ...

Si vous visez du vert au bleu à l'avenir, je veux être sûr de résoudre ce problème C.

Pour cela, je vais résoudre l'optimisation combinée d'AOJ (https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1). !!

Takahashi essaie de s'inscrire en tant que membre d'un certain service Web. J'ai d'abord essayé d'enregistrer l'ID en tant que $ S $. Cependant, cet ID était déjà utilisé par un autre utilisateur. Par conséquent, M. Takahashi a pensé à enregistrer une chaîne de caractères avec un caractère ajouté à la fin de $ S $ en tant qu'ID. Takahashi essaie d'enregistrer un nouvel ID en tant que $ T $. Déterminez si cela remplit les conditions ci-dessus.

Vous devez juste vérifier si T [: -1] avec la lettre de fin de T supprimée correspond à S. Pour le moment, il vérifie également le nombre de caractères pour ne pas passer l'entrée dangereuse [^ 1] telle que S =" "T =" " `.

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

B Il existe des cartes $ A $ avec> 1 écrite, des cartes $ B $ avec 0 écrit et des cartes $ C $ avec -1 écrit. Lorsque vous choisissez seulement $ K $ parmi ces cartes, quelle est la valeur maximale possible en tant que somme des nombres inscrits sur les cartes que vous avez choisies?

Il existe trois valeurs maximales en fonction de la valeur de K.

Lorsque K <= A.

Les cartes ――K de "1" sont très modifiables, c'est un gaspillage. --La valeur maximale est lorsque vous prenez K cartes "1", et la valeur maximale est K.

Lorsque A <K <= A + B

Dans ce cas, même si vous prenez des cartes A "1", vous êtes obligé de prendre des cartes K-A, vous devez donc prendre des cartes "0" ou des cartes "-1" pour ce montant. Heureusement, puisque K-A <B des prérequis, vous pouvez marquer les obligations de tirage restantes sans réduire la valeur maximale en tirant une carte "0".
La valeur maximale est A pour les cartes "1" et K-A pour les cartes "0", et la valeur maximale est A.

Lorsque A + B <K ――J'ai manqué de cartes "1" et "0", donc je dois enfin gérer la carte "-1" (Ed Stafford, qui a dû manger grinçant dans une vie inexplorée) C'est un sentiment de). [^ 2] Dans ce cas, le nombre de cartes "-1" à prendre est K- (A + B).

La valeur maximale est A- (K-) pour les cartes "1", B pour les cartes "0" et K- (A + B) pour les cartes "-1". (A + B)).

Puisqu'il y a au plus 3 modèles, implémentons-le honnêtement.

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

Il y a des villes $ N $ dans le royaume de Takahashi. Les villes sont numérotées de 1 $ à $ N $. Il y a un téléporteur dans chaque ville. Le téléporteur de la ville $ i (1 ≤ i ≤ N) $ est transféré vers la ville $ A_i $. Le roi Takahashi aime l'entier positif $ K $. Le roi égoïste Takahashi veut savoir dans quelle ville il arrivera s'il part d'une ville à 1 $ et utilise le téléporteur seulement $ K $ fois. Créez un programme pour cela pour le roi Takahashi.

(Réponse WA)

Si vous regardez la ville comme un nœud et la téléportation comme un bord dirigé, vous pouvez voir le graphique dirigé d'une manière ou d'une autre. Puis, quand j'y pense un moment, j'arrive à la conclusion que "si vous répétez la téléportation dans une certaine mesure, vous finirez par faire le tour d'une boucle infinie dans le graphique?" "Vous n'avez pas à simuler cette partie." Je t'atteindrai. Cela signifie

Répétez honnêtement la téléportation pour le moment. Ajoutez et enregistrez les nœuds recherchés dans la liste.
Si le nœud recherché est touché pendant la téléportation, la téléportation suivante sera dans une boucle infinie, de sorte que la partie répétitive peut être calculée sans simulation.
Si vous atteignez K fois avant la boucle infinie, c'est très bien. Je pensais que la mise en œuvre pourrait être ... mais la réponse suivante serait non seulement TLE mais aussi WA.

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

#Index à 1 origine
A.insert(0,-1)

accessed_node = set([1])
accessed_node_list=[1]
loop_root = []
loop_madeno_size = 0
loop_size=0
t=1
#Détection de boucle
for _ in range(1,K+1):
  if not A[t] in accessed_node:
    accessed_node.add(A[t])
    accessed_node_list.append(A[t])
    #Décidez de l'endroit suivant
    t=A[t]
  else:
    #Déterminez le chemin de la boucle
    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 ... je veux le résoudre après l'entraînement. En outre, il s'agit d'un modèle légèrement plus rapide avec PyPy.

Résumé

Cliquez ici pour une réponse complète: https://github.com/Nekomo/AtCoder/tree/master/ABC/167 Optimisation combinée d'ici la semaine prochaine, je vais résoudre beaucoup de DP! !!

[^ 1]: entrée dangereuse.

[^ 2]: Roumanie | La vie inexplorée https://youtu.be/NSwOF_A0LfM

ABC167 WriteUp

emballer

Résumé