Revue du concours régulier AtCoder 104

Les résultats de cette fois

スクリーンショット 2020-10-06 13.34.57.png

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.

IMG_0675.jpg

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

IMG_F6622D33AF36-1.jpeg

À 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 $.

dp[i][j+l*(i+1)]+=dp[i-1][j]

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 » et «** Ne regardez pas la somme ( j $) que vous n'avez pas besoin de voir **» comme une accélération multiple constante.

(✳︎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

Revue du concours régulier AtCoder 105
AtCoder Regular Contest 106 Évaluation
Revue du concours régulier AtCoder 104
Critique du concours AtCoder Beginner Contest 152
Critique du concours AtCoder Débutant 160
Critique du concours AtCoder Débutant 178
Critique du concours AtCoder pour débutant 166
AtCoder Débutant Contest 167 Évaluation
Concours régulier AtCoder 106 Remarque
Critique du concours AtCoder
AtCoder Débutant Contest 169 Évaluation
AtCoder Grand Contest 048 Critique
AtCoder Débutant Contest 171 Critique
Critique du concours AtCoder pour débutant 182
Critique du concours AtCoder Débutant 180
Critique du concours AtCoder pour débutant 177
AtCoder Débutant Contest 168 Critique
Concours régulier AtCoder 105 Remarque
AtCoder Grand Contest 045 Critique
AtCoder Grand Contest 044 Critique
Critique du concours AtCoder
Critique du concours AtCoder pour débutant 172
Critique du concours AtCoder
AtCoder Grand Contest 046 Critique
AtCoder Débutant Contest 175 Critique
Critique du concours AtCoder
Critique du concours AtCoder Beginner Contest 153
Critique du concours AtCoder pour débutant 156
AtCoder Débutant Contest 161 Critique
AtCoder Débutant Contest 170 Critique
Critique du concours AtCoder
AtCoder Débutant Contest 173 Critique
AtCoder Débutant Contest 155 Critique
AtCoder Débutant Contest 162 Évaluation
AtCoder Regular Contest # 002 Problème C
Rapport de participation au concours régulier AtCoder 105
AtCoder Regular Contest 104 Rapport de participation
AtCoder Beginner Contest 066 Revoir les questions précédentes
Concours AtCoder Débutant 177
concours yukicoder 259 avis
concours yukicoder 264 avis
Concours AtCoder Débutant 172
concours yukicoder 261 avis
concours yukicoder 267 avis
Concours AtCoder Débutant 173
concours yukicoder 266 avis
concours yukicoder 263 avis
yukicoder contest 268 avis
AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 072 Revue des questions précédentes
AtCoder Beginner Contest 085 Revue des questions précédentes
AtCoder Beginner Contest 062 Revue des questions précédentes
AtCoder Beginner Contest 113 Revue des questions précédentes
AtCoder Beginner Contest 074 Revue des questions précédentes
AtCoder Beginner Contest 051 Revue des questions précédentes
AtCoder Beginner Contest 127 Revue des questions précédentes
AtCoder Beginner Contest 119 Revue des questions précédentes
AtCoder Beginner Contest 151 Revue des questions précédentes
AtCoder Beginner Contest 075 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 110 Revue des questions précédentes