[PYTHON] Revue du concours régulier AtCoder 104
Les résultats de cette fois
Impressions de cette époque
Cela s'est terminé par un résultat décevant. Le problème C n'a pas pu être résolu en raison d'un manque de puissance typique, et le problème D n'a pas pu être résolu en raison d'un manque de puissance de poussée. Il est difficile de résoudre le problème D pendant le concours, mais je pense que le problème C devrait être résolu sans faute, donc je veillerai à le résoudre la prochaine fois que je sortirai.
Problème A
La résolution des équations simultanées donne $ x = \ frac {a + b} {2}, y = \ frac {a-b} {2} $. Je ne voulais pas le rendre bogue par positif ou négatif, alors j'ai divisé les cas.
A.py
a,b=map(int,input().split())
if a>b:
print((a+b)//2,(a-b)//2)
else:
print((a+b)//2,-((b-a)//2))
Problème B
Même si c'était si facile qu'il ne serait pas étrange de sortir avec C de ABC, je l'ai mal lu et l'ai utilisé pendant environ 15 minutes. En conséquence, j'aurais dû résoudre ce problème rapidement, mais je ne pense pas qu'il y ait un point dans le taux qui puisse être résolu rapidement, donc l'un ou l'autre va bien.
Tout d'abord, recherchez toutes les sous-colonnes continues. Il suffit de dire que le nombre de $ a, t $ et le nombre de $ g, c $ correspondent à la sous-chaîne continue, et que la quantité de calcul est linéaire par rapport à la sous-chaîne continue, et $ O (n ^ 2) dans son ensemble C'est $.
B.py
n,s=input().split()
s=list(s)
n=int(n)
ans=0
for i in range(n):
at,gc=0,0
for j in range(i,n):
if s[j]=="A":
at+=1
elif s[j]=="T":
at-=1
elif s[j]=="G":
gc+=1
else:
gc-=1
if at==0 and gc==0:
ans+=1
print(ans)
Problème C
Post-scriptum (10/8)
La solution décrite ci-dessous (publication du deuxième code) s'est avérée être une fausse solution. </ font> Il n'y a aucun doute si c'est la solution du premier code.
Plus précisément, bien que Non doive être émis dans les cas suivants, Oui est émis dans le cas du deuxième code.
2
2 3
-1 -1
La raison pour laquelle cela s'est produit est que je n'ai pas considéré le nombre de paires où $ (A \ _i, B \ _i) = (-1, -1) $ était stocké dans la variable ** $ ot $ . (Voir ci-dessous pour $ ot $). Pour prendre cela en compte, $ dp [l] [r] au lieu de $ dp [l] [r]: = $ (si $ [l, r] $ se compose de plusieurs intervalles qui satisfont le sujet) : = $ ( $ (A \ _i, B \ _i) = (-1, -1) $ in $ [l, r] $, le nombre minimum de personnes **). Et s'il devient finalement $ dp [0] [n-1] = ot $, Yes est sorti, sinon No est sorti. Dans le cas ci-dessus, $ ot = 1 $ et $ dp [0] [n-1] = 2 $, ce qui ne convient pas.
Impressions
Je ne pouvais pas y penser pendant le concours, mais j'ai pu le résoudre en le révisant. La mise en œuvre était lourde et WA a été publié, mais en conséquence j'étais heureux d'avoir pu le résoudre moi-même. De plus, ce qui suit n'est pas la politique lors de la résolution ascendante immédiatement après le concours, mais la politique après avoir bien compris la section DP. La deuxième partie du code est la suivante. De plus, l'intervalle DP est un DP ** qui a des informations sur l'intervalle $ [l, r] $ comme ** $ dp [l] [r] $. Pour plus de détails, veuillez consulter cet article.
politique
Premièrement, dans la première expérience, j'ai pensé qu'il pouvait être divisé en sections où des personnes ayant le même ** $ c \ _i $ étaient combinées **. De plus, étant donné ** $ c \ _i $, cette valeur détermine de manière unique la longueur de l'intervalle ** (je ne l'ai pas remarqué pendant le concours). Par conséquent, inversement, lorsque la section $ [l, r] $ est donnée, les étages sur lesquels les personnes incluses dans la section roulent et les étages sur lesquels ils descendent sont déterminés de manière unique comme suit ($ (r-l + 1) \ % \ 2 = 0 $ est requis). De plus, dans la figure ci-dessous, $ k = \ frac {r-k + 1} {2} $ tient.
De plus, quand ** $ [l, r] $ est donné, il semble que $ O (n) $ montrera si la section tient comme indiqué dans la figure ci-dessus **. Par conséquent, tout $ l, r $ peut indiquer l'établissement de cet intervalle, et $ dp [l] [r]: = $ ($ [l, r] $ devient un intervalle qui satisfait le thème **. Vous pouvez préparer un tableau avec si oui ou non **).
De plus, ce que nous voulons finalement trouver est $ dp [l] [r]: = $ (si $ [l, r] $ est composé de plusieurs intervalles qui satisfont le thème **), donc * * Il est nécessaire de porter un jugement en fusionnant chaque section **.
À partir de ce qui précède, vous pouvez écrire un programme $ O (n ^ 3) $, ce qui est assez rapide.
la mise en oeuvre
Maintenant que nous avons une politique de base, nous allons envisager de la mettre en œuvre.
** (1) Préparation **
Reçoit les informations de la personne donnée (étages d'embarquement et de descente) et les enregistre dans la structure de données. Si vous connaissez à la fois l'étage d'embarquement et l'étage descendant, enregistrez les informations dans le tableau $ lr $ sous "$ lr $ [plancher d'embarquement] = étage descendant". Si seul le sol à parcourir est connu, les informations sont enregistrées dans le tableau $ lx $ sous le nom "$ lx $ [board] = True". Si seul le plancher descendant est connu, enregistrez les informations dans le tableau $ rx $ sous "$ rx $ [plancher descendant] = True". Si vous ne savez pas à quel étage monter ou descendre, vous voudrez l'utiliser pour les ajustements, alors enregistrez ce nombre dans une variable appelée $ ot $.
Sauf lorsque cela n'est pas possible en premier lieu lors de la lecture d'informations comme préparation. En d'autres termes, ** quand il devient "étage d'embarquement > étage descendant" ** et ** quand il y a plusieurs mêmes étages ** ne satisfont clairement pas le sujet, donc dans ce cas, sortez d'abord Non et exécutez le programme. J'ai fini.
** (2) Trouvez $ dp [l] [r]: = $ (si $ [l, r] $ est une section qui satisfait le thème) **
Tout d'abord, déterminez si $ [l, r] $ est un intervalle pour tout $ l, r $. Si ** $ (r-l) \% \ 2 = 0 $, cela ne tient pas **, alors regardez la section suivante. De plus, la différence entre l'étage où les gens descendent et l'étage où les gens accèdent à cette section est $ seglen = \ frac {r-l + 1} {2} $. Ici, pour tout $ l \ leqq i \ leqq r-seglen $, il est jugé si $ i, i + seglen $ est approprié comme ensemble de l'étage où l'ascenseur monte et de l'étage où l'ascenseur descend dans les 6 cas suivants.
[1] $ lr [i]! = -1 $ et $ lr [i]! = I + seglen $
** Il ne convient pas car vous descendez à un autre étage **.
[2] Lorsque $ lx [i + seglen] $ est vrai ou $ rx [i] $ est vrai
Il ne convient pas car le sol pour descendre et le sol pour monter sont en face.
[3] Quand $ lr [i] = i + seglen $
La paire de planchers pour monter et descendre est appropriée.
[4] Lorsque $ lx [i] $ est vrai et $ rx [i + seglen] $ est vrai
Cela ne convient pas car $ i, i + seglen $ à appairer est ** sur le sol où différentes personnes montent et sur le sol où elles descendent **.
[5] Lorsque $ lx [i] $ est vrai ou $ rx [i + seglen] $ est vrai
Il est approprié car vous pouvez décider correctement à quel étage descendre ou monter.
[6] Lorsque $ lx [i] $ est False et $ rx [i + seglen] $ est False
C'est approprié car vous pouvez utiliser la paire stockée dans $ ot $.
** (3) Trouvez $ dp [l] [r]: = $ (si $ [l, r] $ se compose de plusieurs sections qui satisfont le sujet) **
Fusionnez le $ dp [l] [r] $ trouvé précédemment et voyez si $ dp [0] [2n-1] $ est vrai.
À ce moment, si ** $ dp [l] [i] $ est Vrai et $ dp [i + 1] [r] $ est Vrai, alors $ dp [l] [r] $ est Vrai ** et est arbitraire. Essayez $ l, r, i $. Vous pouvez fusionner correctement en tournant la boucle comme $ l, r, i $ de l'extérieur.
C.py
n=int(input())
#B contre A
#C'est lent à gérer ici avec un dictionnaire
lr,lx,rx,ot=[-1]*(2*n),[0]*(2*n),[0]*(2*n),0
ab=[[j-1 for j in list(map(int,input().split()))] for i in range(n)]
check=[0]*(2*n)
for i in range(n):
if ab[i][0]!=-2:
check[ab[i][0]]+=1
if ab[i][1]!=-2:
check[ab[i][1]]+=1
#S'il est inversé
if ab[i][0]!=-2 and ab[i][1]!=-2:
if ab[i][0]>ab[i][1]:
print("No")
exit()
#Lorsque 2 ou plus sont inclus
if any(i>1 for i in check):
print("No")
exit()
for i in range(n):
if ab[i][0]==-2 and ab[i][1]==-2:
ot+=1
elif ab[i][0]==-2:
rx[ab[i][1]]=1
elif ab[i][1]==-2:
lx[ab[i][0]]=1
else:
lr[ab[i][0]]=ab[i][1]
#dp[l][r]=([l,r]Minimum à utiliser dans)
#Sera-ce une position?
inf=10**12
dp=[[inf]*(2*n) for i in range(2*n)]
for l in range(2*n):
#r est supérieur à l
for r in range(l+1,2*n):
dp_sub=0
#Cette section existe-t-elle certainement?(S'il n'existe pas, modifiez-le pour qu'il se brise immédiatement(Branche))
seglen=(r-l+1)//2
#La longueur de la section est bizarre(2x+1)
#À ce moment-là, la section qui y est incluse est x+1 longueur
if (r-l)%2==1:
for i in range(l,r-seglen+1):
#Je et je+paire de seglen
if lr[i]!=-1:
if lr[i]!=i+seglen:
break
elif lx[i]:
if not rx[i+seglen]:
dp_sub+=0
else:
break
elif rx[i]:
break
else:
#i+Aussi le modèle où seglen est dans rx
if not rx[i+seglen]:
#Seulement à ce moment(-1,-1)
dp_sub+=1
#Si cette section remplit les conditions
else:
dp[l][r]=dp_sub
#Découvrez s'il y a des candidats dans DFS d'ici
#Quitter si même un est trouvé
#Sinon, non
#Vérifiez si ot convient
def dfs(i,otc):
if otc>ot:
return
if i==2*n:
if otc==ot:
print("Yes")
exit()
else:
return
for j in range(i+1,2*n):
if dp[i][j]!=inf:
dfs(j+1,otc+dp[i][j])
dfs(0,0)
print("No")
C2.py
n=int(input())
#B contre A
#C'est lent à gérer ici avec un dictionnaire
lr,lx,rx,ot=[-1]*(2*n),[0]*(2*n),[0]*(2*n),0
ab=[[j-1 for j in list(map(int,input().split()))] for i in range(n)]
check=[0]*(2*n)
for i in range(n):
if ab[i][0]!=-2:
check[ab[i][0]]+=1
if ab[i][1]!=-2:
check[ab[i][1]]+=1
#S'il est inversé
if ab[i][0]!=-2 and ab[i][1]!=-2:
if ab[i][0]>ab[i][1]:
print("No")
exit()
#Lorsque 2 ou plus sont inclus
if any(i>1 for i in check):
print("No")
exit()
for i in range(n):
if ab[i][0]==-2 and ab[i][1]==-2:
ot+=1
elif ab[i][0]==-2:
rx[ab[i][1]]=1
elif ab[i][1]==-2:
lx[ab[i][0]]=1
else:
lr[ab[i][0]]=ab[i][1]
#dp[l][r]=Sera-ce une position?
dp=[[False]*(2*n) for i in range(2*n)]
for l in range(2*n):
#r est supérieur à l
for r in range(l+1,2*n):
#Cette section existe-t-elle certainement?(S'il n'existe pas, modifiez-le pour qu'il se brise immédiatement(Branche))
seglen=(r-l+1)//2
#La longueur de la section est bizarre(2x+1)
#À ce moment-là, la section qui y est incluse est x+1 longueur
if (r-l)%2==1:
for i in range(l,r-seglen+1):
#Est-ce que lr est différent,l,Est-il mal saisi dans r?
if (lr[i]!=-1 and lr[i]!=i+seglen) or lx[i+seglen] or rx[i]:
#print(l,r,1)
break
if lr[i]==i+seglen:
continue
#Peut-il être inclus en même temps?
if [lx[i],rx[i+seglen]].count(True)==2:
#print(l,r,2)
break
elif [lx[i],rx[i+seglen]].count(True)==1:
continue
#Si cette section remplit les conditions
else:
dp[l][r]=True
#De là, c'est OK si vous pouvez fusionner la section DP et enfin fusionner
#dp[l][i],dp[i+1][r]Vrai si les deux sont vrais
for l in range(2*n):
for r in range(l+1,2*n):
for i in range(l+1,r):
if dp[l][r]==False:
if dp[l][i] and dp[i+1][r]:
dp[l][r]=True
break
#print(dp)
if dp[0][2*n-1]:
print("Yes")
else:
print("No")
Problème D
Je ne comprends pas comment résoudre la bonne réponse, mais je vais l'expliquer car elle a été passée par une accélération multiple constante (✳︎1).
(Le nombre premier pour lequel vous voulez trouver le reste donné divisé est indiqué ci-dessous comme $ mod $.)
Considération de base
Tout d'abord, lorsque la moyenne est de $ x $, il est typique que ** de $ -x $ le tout, l'information numérique disparaisse et le montant du calcul diminue **. Par conséquent, considérons le cas où la somme des nombres suivants est 0 lorsque la moyenne est $ x $.
À ce stade, considérez le côté gauche et le côté droit de 0 séparément (✳︎2). Ensuite, le côté gauche est tout négatif et le côté droit est positif. Par conséquent, si les deux sont alignés positivement, ** la somme à gauche et la somme à droite sont égales **. De plus, le côté gauche est la somme lors de la sélection de $ 1,2,…, x-1 $, et le côté droit est la somme lors de la sélection de $ 1,2,…, nx $, donc $ dp [i] [j]: Si = $ (le nombre lorsque la somme de 1 à $ i + 1 $ est $ j $) est calculé à l'avance, la sortie de la solution finale est $ x = $ 1 ~ $ n $. Il peut être calculé par le montant du calcul de $ O (n ^ 3k) $ en comparant avec $ j $.
Partie DP
Ici, ** à propos du DP précalculé **, mais comme chaque nombre peut être sélectionné de 0 à $ k $ $ k + 1 $, il y a des transitions $ k + 1 $. En d'autres termes, le montant du calcul est $ O (n ^ 3k ^ 2) $ et le maximum est $ n ^ 3k ^ 2 = 10 ^ {10} $. Ici, dans la réponse, je l'ai laissé tomber à $ O (n ^ 3k) $ par la technique de la valeur minimale de la diapositive, mais je l'ai passé en augmentant la vitesse d'un multiple constant (✳︎1).
Si vous mettez le DP comme avant, la transition de $ dp [i-1] [j] $ sera la suivante. Supposons également que vous ne sélectionniez que $ l $ pour $ i + 1 $.
Ici, la réponse doit être sortie avec le reste de $ mod $, et en même temps je veux définir $ dp [i] [j + l * (i + 1)] % = mod $, mais ** $ % $ Puisque le calcul prend du temps et que seule l'addition est effectuée ici **, il n'est nécessaire de soustraire $ mod $ que lorsque $ dp [i] [j + l * (i + 1)] $ dépasse $ mod $. est.
Partie de sortie
En calculant DP, $ dp [i] [j] $ peut être obtenu pour tout $ i, j $, alors considérez la sortie.
Premièrement, quand $ x = 1, n $, il y a 1 à $ k $ $ k $, et sinon il y a $ dp [n-2] [0] = 1 $. , Multipliez et divisez par $ mod $ pour trouver le reste.
Dans d'autres cas, lorsque la valeur à obtenir comme réponse est initialisée comme $ ans = 0 $ et que seul ** $ x $ est sélectionné, ** est identique à $ k $, et autre que ** $ x $ est également sélectionné. ** vaut $ dp [x-2] [j] \ * dp [nx-1] [j] $ si la somme de gauche et de droite est égale à $ j $. Pour tout $ j (\ geqq 1) $, ajoutez-le à $ ans $ et trouvez enfin le reste divisé par $ mod $. Aussi, pour éviter tout débordement **, prenez $ mod $ à chaque fois que vous multipliez **. Et comme il existe $ k + 1 $ façons de sélectionner $ x $, vous pouvez enfin afficher $ ans \ * (k + 1) + k $.
(✳︎1)… J'ai utilisé «$ % $ calcul par $ mod
(✳︎2)… ** 0 Il est facile de penser qu'il augmentera (ou diminuera) de 1 au début **. Je n'ai pas pensé à un bug dans ma tête pendant le concours ...
D.cc
//Options de débogage:-fsanitize=undefined,address
//Optimisation du compilateur
#pragma GCC optimize("Ofast")
//Inclure etc.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//macro
//pour boucle
//L'argument est(Variables dans la boucle,Amplitude de mouvement)Ou(Variables dans la boucle,Premier numéro,Nombre d'extrémités)、のどちらOu
//Les variables de boucle sans D sont incrémentées de 1 et les variables de boucle avec D sont décrémentées de 1.
//FORA est une gamme de déclaration(Si c'est difficile à utiliser, effacez-le)
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//x est un conteneur tel que vector
#define ALL(x) x.begin(),x.end()
#define SIZE(x) ll(x.size())
//constant
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Droit commun
#define MAXR 100000 //10^5:Portée maximale de la baie
//Abréviation
#define PB push_back //Insérer
#define MP make_pair //constructeur de paires
#define F first //Le premier élément de paire
#define S second //Le deuxième élément de paire
signed main(){
//Code pour accélérer la saisie
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll n,k,mod;cin>>n>>k>>mod;
if(n==1){
cout<<k<<endl;
return 0;
}else if(n==2){
cout<<k<<endl;
cout<<k<<endl;
return 0;
}
ll ran=k*n*(n+1)/2;
vector<vector<ll>> dp(n,vector<ll>(ran+1,0));
REP(j,k+1){
dp[0][j]=1;
}
FOR(i,1,n-1){
REP(j,k*i*(i+1)/2+1){
ll ran2=min(k+1,(ran-j)/(i+1)+1);
REP(l,ran2){
dp[i][j+l*(i+1)]+=dp[i-1][j];
if(dp[i][j+l*(i+1)]>=mod)dp[i][j+l*(i+1)]-=mod;
}
}
}
cout<<k*dp[n-2][0]%mod<<endl;
FOR(i,2,n-1){
ll ans=0;
FOR(j,1,ran){
ans+=(dp[i-2][j]*dp[n-i-1][j]);
ans%=mod;
}
cout<<((k+1)*ans+k)%mod<<endl;
}
cout<<k*dp[n-2][0]%mod<<endl;
}
Après le problème E
Je ne résoudrai pas cette fois.
Recommended Posts