Critique du concours AtCoder Débutant 178

Les résultats de cette fois

スクリーンショット 2020-09-14 8.36.47.png

Impressions de cette époque

Cette fois aussi, le résultat est décevant. Le problème E a pris du temps sans être particulier sur ma politique.

Je regrette le problème F car il a fallu beaucoup de temps pour le mettre en œuvre en essayant de faire de la cupidité mensonge en utilisant set même si j'avais un peu de temps. ** Ne faites pas la cupidité avec des sentiments appropriés **. En outre, ce problème était ** en fait un problème de bâillon **, et la bonne réponse était ce que je pensais ne pas être la solution. Je regrette trop ...

Ce fut un résultat décevant cette fois aussi, mais je sens que le sol gagne progressivement en force, alors j'aimerais faire de mon mieux sans renoncer. Je serai probablement capable de surfer sur la vague si je peux faire des performances jaunes, alors je vais me consacrer.

Problème A

J'ai essayé de l'écrire facilement et j'ai échoué.

A.py


print(1 if int(input())==0 else 0)

Problème B

** Puisqu'il peut être montré que la valeur est plus grande lorsque la fin est sélectionnée que lorsque la partie sans fin est sélectionnée, ** la valeur maximale des quatre types de multiplication d'arêtes est calculée.

B.py


a,b,c,d=map(int,input().split())
print(max(a*c,a*d,b*c,b*d))

Problème C

** La condition d'existence est de considérer le refus et de considérer l'ensemble complémentaire **. Autrement dit, sauf lorsque seulement 1 ~ 9 est sélectionné dans l'ensemble (10 $ ^ n $) (9 $ ^ n $) et lorsque 0 ~ 8 est sélectionné (9 $ ^ n $). De plus, lorsque 1 à 8 sont sélectionnés (8 $ ^ n $), ils sont dupliqués et sont donc exclus. Donc, $ 10 ^ n-9 ^ n-9 ^ n + 8 ^ n $ est la réponse. Vous devez également répondre avec $ mod \ 10 ^ 9 + 7 $, mais en Python, vous devez utiliser la fonction ** intégrée ** pow.

C.py


n=int(input())
mod=10**9+7
print((pow(10,n,mod)-2*pow(9,n,mod)+pow(8,n,mod)+2*mod)%mod)

Problème D

** Si vous connaissez la longueur de la séquence, il semble que vous puissiez décider en superposant des combinaisons **. Ici, la longueur de la séquence est au plus $ [\ frac {n} {3}] $ **, à condition que tous les termes soient 3 ou plus. De plus, ** Je veux créer des combinaisons en double de 0 ou plus **, donc soustrayez 3 de tous les termes. Par conséquent, si la longueur de la colonne numérique est $ x $, considérez le cas où le total est $ s-3x $ et tous les nombres sont 0 ou plus. À ce stade, il peut être reformulé comme le problème de l'organisation des ** $ s-3x $ sphères et $ x-1 $ partitions **, et le nombre total de combinaisons est $ _ {s-3x + x-1} C _ { Cela devient s-3x} $. Aussi, comme je veux trouver le reste de 10 $ ^ 9 + 7 $, j'ai utilisé Calcul du coefficient binomial par élément inverse.

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

ll fac[MAXR+1],finv[MAXR+1],inv[MAXR+1];

//Créer une table
void COMinit() {
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    FOR(i,2,MAXR){
        fac[i]=fac[i-1]*i%MOD;
        inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
        finv[i]=finv[i-1]*inv[i]%MOD;
    }
}

//Calcul du coefficient binomial
ll COM(ll n,ll k){
    if(n<k)return 0;
    if(n<0 || k<0)return 0;
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}

signed main(){
    //Code pour accélérer la saisie
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    COMinit();
    ll s;cin>>s;
    ll ans=0;
    FOR(x,1,ll(s/3)){
        ll k=s-3*x;
        ans+=COM(k+x-1,k);
        ans%=MOD;
    }
    cout<<ans<<endl;
}

E problème

** Cela m'a paru difficile et j'ai perdu ma concentration **. Bien que ce soit une théorie conséquente, si je peux passer ce problème à grande vitesse, je peux résoudre le problème F, donc j'aimerais m'entraîner avec un bacha pour pouvoir maintenir ma concentration.

Aussi, pendant le concours, j'ai pu le résoudre car j'ai trouvé cet article par google. Cette question n'est pas facile, je pense donc que de nombreuses personnes ont cherché sur Google la bonne réponse.

Premier,Ou corrigez l'un des deux pointsxCoordonnées etyOu fixez les coordonnéesJ'ai pensé essayer, mais je ne pouvais pas le dire. Par conséquent, la prochaine chose à considérerPour supprimer la valeur absolueest. ici,Comme modèle typique lors de la suppression de la valeur absolue|x|=max(x,-x)Il y aIl semble. Selon cela, entre deux points(x\_1,y\_1),(x\_2,y\_2)Distance de Manhattanmax((x\_1+y_1)-(x\_2+y\_2),(x\_1-y_1)-(x\_2-y\_2),(-x\_1+y_1)-(-x\_2+y\_2),(-x\_1-y_1)-(-x\_2-y\_2))Ce sera. Donc,Entre deux points quelconquesSi vous pensez à chaque point(x,y)surx+y,x-y,-x+y,-x-yÀ chaque fois(Valeur maximum)-(valeur minimum)を求めてそのValeur maximumが答えとなります。

E.py


n=int(input())
xy=[list(map(int,input().split())) for i in range(n)]
ans=[]
cand=[xy[i][0]+xy[i][1] for i in range(n)]
ans.append(max(cand)-min(cand))
cand=[-xy[i][0]+xy[i][1]for i in range(n)]
ans.append(max(cand)-min(cand))
cand=[-xy[i][0]-xy[i][1] for i in range(n)]
ans.append(max(cand)-min(cand))
cand=[xy[i][0]-xy[i][1] for i in range(n)]
ans.append(max(cand)-min(cand))
print(max(ans))

Problème F

Tout d'abord, j'ai pensé à une méthode gourmande de swapping pour que les éléments précédents ne correspondent pas dans l'ordre, mais je l'ai rejetée car elle semble injustifiée. Ensuite, si je profite du fait qu'ils ne doivent pas correspondre et qu'ils sont tous triés, j'ai pensé que ** en inversant, seul le milieu ** correspondrait (✳︎). Cependant, j'ai rejeté cette méthode parce que je pensais que c'était trop facile. Après cela, la méthode que j'ai proposée a été de décider dans l'ordre du plus. J'ai implémenté cette méthode même si je ne pouvais pas la justifier. De plus, la mise en œuvre était un peu lourde et ne s'est pas terminée pendant le concours.

En regardant les réponses d'autres personnes sur Twitter après le concours, j'ai remarqué ** la douceur de ma considération ** pendant le concours. ** C'est tellement facile que je l'ai rejeté **. J'ai l'habitude d'arrêter de penser ** si la solution à un problème est trop difficile ou trop facile **, alors j'aimerais m'arrêter. Quoi qu'il en soit, si vous continuez à considérer (✳︎), ce problème peut être résolu comme suit.

Tout d'abord, considérez combien de 1 ~ $ n $ chacun de $ A $ et $ B $ il y a au total, et s'il y a plus d'éléments que $ n $, il n'est pas possible de créer une séquence de nombres qui satisfasse le thème. Comme il ressort clairement du principe, Non est une sortie.

En vertu de cela, inversez d'abord B selon la politique précédente. Pour le moment, il n'y a qu'un seul ** $ p $ qui devient $ (\ forall x \ in [l, r]) (A \ _x = B \ _x = p) $. Au contraire, s'il n'existe pas, il satisfera le but s'il est sorti tel quel. A ce moment, $ (\ forall x \ notin [l, r]) (A \ _x \ neq B \ _x) $ est également valable. (La preuve est omise)

Maintenant, échangez ** pour n'importe quel élément de ** $ x \ dans [l, r] $. Ce swap est compris entre $ x (\ in [l, r]) $ et $ y (\ notin [l, r]) $. De plus, ce swap peut être fait pour $ y (\ notin [l, r]) $ si c'est $ A \ _y \ neq p $ et $ B \ _y \ neq p $. Deux éléments ne correspondent jamais à leurs index respectifs **. De plus, puisque $ p $ apparaissant dans $ A $ et $ B $ est inférieur à $ n $, il est possible d'échanger pour n'importe quel $ x (\ in [l, r]) $ (*). * Il est bon de penser que vous pouvez swap pour que $ p $ existe dans tous les index lorsque vous échangez au maximum **.).

D'après ce qui précède, la validité du procédé de répétition de l'échange entre la partie chevauchante et la pièce non chevauchante dans l'ordre inverse a été montrée, donc ceci est mis en œuvre comme suit.

F.py


n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
from collections import Counter,deque
x,y=Counter(a),Counter(b)
for i in range(1,n+1):
    if x[i]+y[i]>n:
        print("No")
        exit()
ans=b[::-1]
change=deque()
num=-1
now=deque()
for i in range(n):
    if a[i]==ans[i]:
        change.append(i)
        num=ans[i]
    else:
        now.append(i)
if change==[]:
    print("Yes")
    print(" ".join(map(str,ans)))
    exit()
while len(change):
    q=now.popleft()
    p=change.popleft()
    if a[q]!=num and ans[q]!=num:
        ans[q],ans[p]=ans[p],ans[q]
    else:
        change.appendleft(p)

print("Yes")
print(" ".join(map(str,ans)))

Recommended Posts

Critique du concours AtCoder Débutant 178
Critique du concours AtCoder pour débutant 166
AtCoder Débutant Contest 167 Évaluation
Critique du concours AtCoder
AtCoder Débutant Contest 169 Évaluation
Critique du concours AtCoder Débutant 181
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
Critique du concours AtCoder
Critique du concours AtCoder pour débutant 172
Critique du concours AtCoder
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
Concours AtCoder Débutant 179
Concours AtCoder Débutant 172
Concours AtCoder Débutant 180
Concours AtCoder Débutant 173
Concours Atcoder Débutant 153
AtCoder Beginner Contest 066 Revoir les questions précédentes
Concours AtCoder Débutant 181 Remarque
AtCoder Grand Contest 041 Critique
Revue du concours régulier AtCoder 105
Concours AtCoder Débutant 180 Remarque
Concours AtCoder Débutant 182 Remarque
AtCoder Grand Contest 048 Critique
Concours AtCoder pour débutants 156 WriteUp
AtCoder Grand Contest 045 Critique
AtCoder Grand Contest 044 Critique
Concours AtCoder pour débutants 167
Concours AtCoder Débutant 183 Remarque
AtCoder Regular Contest 106 Évaluation
Concours AtCoder Débutant 184 Remarque
AtCoder Grand Contest 046 Critique
Revue du concours régulier AtCoder 104
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 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
AtCoder Beginner Contest 117 Revue des questions précédentes