[PYTHON] Journal de dévotion professionnel compétitif 20e au 22e jour (7/14 au 7/16)

<! - Modèle de dévotion professionnelle compétitive->

Impressions

Récemment, j'ai l'impression qu'il existe de nombreuses méthodes gourmandes. Je ne suis pas doué pour ça, alors je veux m'y habituer. Ce serait formidable si nous pouvions voir le taux augmenter bientôt ...

20ème jour

ABC141-E Who Says a Pun?

Temps pris

50 minutes Je pensais que cela passerait si je poussais $ O (N ^ 3) $, mais je ne pouvais pas le faire et je l'ai fondu pendant 20 minutes supplémentaires.

Considération

Pour penser à une chaîne de caractères qui apparaît plus d'une fois, il suffit qu'une certaine chaîne de caractères apparaisse au moins deux fois, alors mettez ces deux chaînes de caractères dans $ s_1 $, $ s_2 $ et ci-dessous.

Tout d'abord, je doute de DP car il s'agit d'une sous-chaîne. Cependant, je me suis perdu en essayant de traiter les deux choses que les chaînes de caractères ne se chevauchent pas ** et ** pensent dans la même chaîne de caractères ** en même temps, et de les diviser en avant le caractère $ i $ et après le caractère $ i + 1 $ J'ai pensé, mais c'était une mauvaise décision.

Au cours de mon examen, je me suis concentré sur la ** continuité ** et j'ai pensé qu'elle pouvait être résolue par une méthode simple similaire à la méthode de l'échelle **. Autrement dit, le premier caractère de $ s_1 $ est le caractère $ i $ ($ N $ street), et le premier caractère de $ s_2 $ est le caractère $ j (i + 1 \ leqq j \ leqq N) $ ($ Ni $). Considérez la chaîne la plus longue dans laquelle $ s_1 $ et $ s_2 $ correspondent (jusqu'à $ N $). Dans ce cas, ce sera $ O (N ^ 3) $, donc ce ne sera pas à temps. (Il n'est pas bon que la discussion ait duré jusqu'à présent près de 30 minutes.)

Par conséquent, afin de calculer efficacement cette méthode, ** examinez s'il y a une enquête inutile **. Ensuite, vous pouvez voir que ** la même partie est calculée à plusieurs reprises dans la partie qui détermine si les parties continues correspondent **. Par conséquent, ** vous pouvez améliorer l'efficacité en calculant d'abord la partie arrière **, afin de pouvoir préparer la matrice suivante et effectuer DP.

$ dp [i] [j]: = $ (Le plus long préfixe commun lorsque $ s_1 $ commence par le caractère $ i $ et $ s_2 $ commence par le caractère $ j $, mais lorsque $ i = 0 $ Et $ s_1 $ et $ s_2 $ ne se chevauchent pas, y compris lorsque $ j = 0 $)

Ici, la classification des cas de la transition DP lors du calcul à partir de la dernière partie est la suivante, et la valeur maximale en dp est la réponse en implémentant cela.

(1) Quand ($ i $ caractère de $ s $) $ = $ ($ j $ caractère de $ s $) 　　dp[i][j]=dp[i+1][j+1]+1

(2) Quand ($ i $ caractère de $ s $) $ \ neq $ ($ j $ caractère de $ s $) 　　dp[i][j]=0

(✳︎) $ dp [i] [j] $ ne peut être que $ j-i $ au plus S'il dépasse cela, $ dp [i] [j] = 0 $ peut être défini.

(1), (2), (✳︎) peuvent être représentés respectivement, mais ils sont omis ici.

Postscript

・ Quel est le préfixe commun le plus long? Il s'agit du plus long préfixe commun des chaînes s et t. Le préfixe commun le plus long lorsque s = ABCBC, t = ABD est AB et le préfixe commun le plus long lorsque s = ABC, t = BCD est une chaîne de caractères vide.

・ Connaissance obtenue cette fois Le problème du modèle de réduction de $ N $ d'environ $ O (N ^ 3) $ → $ O (N ^ 2) $ est ** Si vous faites attention à savoir s'il y a un endroit où vous calculez de manière répétée et inutile Je peux réduire le montant **, j'ai donc décidé de le commander. En outre, il semble que ce problème puisse être résolu de différentes manières en utilisant divers algorithmes de chaîne.

<détails>

n=int(input())
s=input()
dp=[[0]*(n+1) for i in range(n+1)]
for i in range(n-1,-1,-1):
    for j in range(n-1,i,-1):
        if s[j]==s[i] and dp[i+1][j+1]+1<=j-i:
            dp[i][j]=dp[i+1][j+1]+1
ans=0
for i in range(n):
    for j in range(n):
        ans=max(ans,dp[i][j])
print(ans)

n=int(input())
red=sorted([list(map(int,input().split())) for i in range(n)],key=lambda x:x[1],reverse=True)
blue=sorted([list(map(int,input().split())) for i in range(n)])
ans=0
for bx,by in blue:
    for rx,ry in red:
        if rx<bx and ry<by:
            ans+=1
            red.remove([rx,ry])
            break
print(ans)

n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
#Je ne peux pas changer ça
f=sorted(list(map(int,input().split())),reverse=True)
l,r=0,10**12
def cal(x):
    global n,f,a,k
    ret=0
    for i in range(n):
        ret+=max(0,a[i]-(x//f[i]))
    return ret
while l+1<r:
    x=l+(r-l)//2
    if cal(x)<=k:
        r=x
    else:
        l=x
if cal(l)<=k:
    print(l)
else:
    print(r)