ABC167 WriteUp

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

A

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.

  1. 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.

  1. Lorsque A <K <= A + B
  1. 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).

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

D

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

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

Recommended Posts

ABC167 WriteUp
ABC168
ABC164
ABC174
ABC175
ABC170
ABC182
ABC153
ABC146 Impressions
AtCoder ABC176
AtCoder ABC177
Débutant ABC154 (Python)
Débutant ABC156 (Python)
rapport de participation abc154
rapport de participation abc155
AtCoder ABC 174 Python
Débutant ABC155 (Python)
Débutant ABC157 (Python)
AtCoder ABC 175 Python