[PYTHON] Critique du concours AtCoder Débutant 178
Les résultats de cette fois
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 points
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