AtCoder Beginner Contest 151 Revue des questions précédentes

Les résultats de cette fois

スクリーンショット 2020-02-02 20.20.53.png

Impressions de cette époque

J'ai déjà résolu les questions du passé en temps réel, mais j'ai oublié tous les problèmes, alors je les ai résolus avec un bacha. Je n'ai pas pu résoudre le problème E quand je l'ai résolu en temps réel, mais je n'ai pas pu résoudre le problème E cette fois non plus ... Je n'ai pas d'autre choix que de le revoir souvent ...

Problème A

Obtient le code ASCII (ord) et renvoie l'élément suivant.

A.py


print(chr(ord(input())+1))

Problème B

Considérez les points de 0 à k qui sont nécessaires pour faire le total et la moyenne jusqu'à ce point de m points ou plus.

B.py


n,k,m=map(int,input().split())
a=sum(list(map(int,input().split())))
if n*m-a>k:
    print(-1)
else:
    print(max(n*m-a,0))

Problème C

Vous pouvez compter le nombre de ** pénalités jusqu'à ** AC. Considérez chaque cas selon qu'il s'agit ou non de courant alternatif.

C.py


n,m=map(int,input().split())
ps=[list(input().split()) for i in range(m)]
pen=[0]*n#Nombre de pena
rig=[0]*n#ACorWA

for i in range(m):
    if ps[i][1]=="AC":
        rig[int(ps[i][0])-1]=1
    else:
        if rig[int(ps[i][0])-1]==0:
            pen[int(ps[i][0])-1]+=1
cnt1,cnt2=0,0
for i in range(n):
    if rig[i]==1:
        cnt1+=rig[i]
        cnt2+=pen[i]

print(str(cnt1)+" "+str(cnt2))

Problème D

Grille de recherche Je me perds à chaque fois que j'écris du code. Pourquoi? (Il ne semble y avoir aucune raison autre que d'être inconnu). Le premier est le BFS écrit en temps réel, et le second est le WF écrit dans le bachacon. Dans le cas de BFS, l'ordre d'une recherche est O ($ HW ), et la sélection du nœud de départ est O ( HW ), donc O ( H ^ 2W ^ 2 ) suffit. (Comme il s'agit d'un BFS de base, je n'expliquerai comment le faire qu'en écrivant un commentaire dans le code. BFS est le plus basique pour parcourir la distance la plus courte.) Dans le cas de WF (il ne passe pas en Python, il passe en PyPy), il traite toutes les grilles comme des nœuds et effectue simplement la méthode WF, et enfin trouve la valeur du plus grand élément (sauf pour inf) ( O ( H ^ 3W ^ 3 $)). La grille de i et j est i * w + j dans le tableau d'enregistrement WF (j'aime personnellement BFS car les conditions de jugement sont compliquées).

answerD_BFS.py


import queue
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]

inf=100000000
ma=[]
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            x=[[inf for i_sub in range(w)] for j_sub in range(h)]
            #La grille que vous regardez
            q=queue.Queue()
            d=0
            #Première grille
            q.put([i,j])
            x[i][j]=0
            #Suivez les grilles les unes après les autres et terminez après avoir suivi toutes les grilles
            while q.qsize()!=0:
                #Ajouter une distance
                d+=1
                l=q.qsize()
                #Comptez le nombre de grilles dont vous disposez
                for t in range(l):
                    I,J=q.get()
                    #De la grille actuelle à la grille suivante
                    #Le jugement est"Y a-t-il une grille là-bas","Pouvez-vous suivre ça","Avez-vous déjà suivi"Il ya trois.
                    if I-1>=0 and s[I-1][J]=="." and x[I-1][J]==inf:
                        q.put([I-1,J])
                        #Si cette mise à jour n'est pas effectuée dans l'instruction if, la grille sera examinée davantage.
                        x[I-1][J]=d
                    if I+1<=h-1 and s[I+1][J]=="." and x[I+1][J]==inf:
                        q.put([I+1,J])
                        x[I+1][J]=d
                    if J-1>=0 and s[I][J-1]=="." and x[I][J-1]==inf:
                        q.put([I,J-1])
                        x[I][J-1]=d
                    if J+1<=w-1 and s[I][J+1]=="." and x[I][J+1]==inf:
                        q.put([I,J+1])
                        x[I][J+1]=d
            ma_sub=0
            for k in range(h):
                for l in range(w):
                    if x[k][l]!=inf:
                        ma_sub=max(ma_sub,x[k][l])
            ma.append(ma_sub)

print(max(ma))

answerD_WF.py


h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
inf=1000000000
wf=[[inf]*(h*w) for i in range(h*w)]
for i in range(h*w):
    k,l=i//w,i%w
    #print(l)
    if s[k][l]=="#":
        continue
    if k!=0:
        if s[k-1][l]==".":
            wf[i][i-w]=1
    if k!=h-1:
        if s[k+1][l]==".":
            wf[i][i+w]=1
    if l!=0:
        if s[k][l-1]==".":
            wf[i][i-1]=1
    if l!=w-1:
        if s[k][l+1]==".":
            wf[i][i+1]=1
    wf[i][i]=0
for i in range(h*w):
    for j in range(h*w):
        for k in range(h*w):
            wf[j][k]=min(wf[j][k],wf[j][i]+wf[i][k])
ans=0
for i in range(h*w):
    for j in range(h*w):
        if wf[i][j]!=inf:
            ans=max(ans,wf[i][j])
print(ans)

E problème

Je me demandais pourquoi O ($ N ^ 2 $) passerait même si N = 10 $ ^ 5 $. C'est devenu TLE sans passer.

Dans la méthode de résolution qui devient O ($ N ^ 2 $), max et min sont déterminés et seul le nombre requis d'éléments (k-2) est sélectionné entre eux, donc ** max et min sont définis en même temps. Si vous ne décidez pas, vous remarquerez que vous pouvez le résoudre avec O (N) **. En d'autres termes, il peut être facilement résolu en trouvant la somme de max et la somme de min, et enfin en considérant la différence entre les sommes **.

En ce qui concerne la résolution de la bonne réponse, le modèle TLE et le calcul lui-même sont presque les mêmes. Tout d'abord, préparez le tableau A en tant que tableau qui reçoit l'entrée et triez-le par ordre croissant. Ensuite, lors de la recherche de max, considérez combien de cas chaque élément $ A_i $ devient max. Dans ce cas, sélectionnez $ A_i $ puis sélectionnez k-1 parmi le plus petit $ A_1 $ ~ $ A_ {i-1} $, donc COM (i, k-1) ) * a [i] . Tout d'abord, ajoutez ceci à ans (n'oubliez pas d'en faire le reste du MOD). Ensuite, lors de la recherche de min, vous pouvez sélectionner k-1 à partir de $ A_ {i + 1} $ ~ $ A_ {n-1} $ `COM (ni-1, k-1) Vous pouvez écrire le code sous la forme * a [i] , alors passons à ans. Cependant, si ans est-, vous devez être trop prudent avec le MOD pour considérer la division négative, et l'éviter avec ans = MOD-abs (ans)% MOD.

answerE_TLE.cc


#include<algorithm>//sort,Recherche de bisection,Tel
#include<bitset>//Jeu de bits de longueur fixe
#include<cmath>//pow,journal etc.
#include<complex>//Nombre complexe
#include<deque>//File d'attente d'accès double
#include<functional>//trier plus
#include<iomanip>//setprecision(Erreur de sortie en virgule flottante)
#include<iostream>//Entrée sortie
#include<map>//map(dictionnaire)
#include<numeric>//iota(Génération d'une chaîne entière),pgcd et lcm(c++17)
#include<queue>//queue
#include<set>//ensemble
#include<stack>//empiler
#include<string>//Chaîne
#include<unordered_map>//Carte avec itérateur mais sans ordre
#include<unordered_set>//Il y a un itérateur mais l'ordre n'est pas maintenu défini
#include<utility>//pair
#include<vector>//Tableau de longueur variable

using namespace std;
typedef long long ll;

//macro
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //Je souhaite omettre des arguments tels que le tri
#define SIZE(x) ((ll)(x).size()) //taille à la taille_Changement de t à ll
#define INF 1000000000000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second
const ll MAX=200000;

ll fac[MAX], finv[MAX], inv[MAX];

//Prétraitement pour faire une table
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        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 binaire
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(){
    COMinit();
    ll n,k;cin >> n >> k;
    vector<ll> a(n);REP(i,n) cin >> a[i];
    sort(ALL(a));
    ll ans=0;
    if(k==1){
        cout << 0 << endl;
        return 0;
    }
    REP(i,n){
        FOR(j,i+1,n-1){
            ans+=((COM(j-i-1,k-2)*((a[j]-a[i])%MOD))%MOD);
            ans%=MOD;
        }
    }
    cout << ans << endl;
}

answerE.cc


//Référence: http://ehafib.hatenablog.com/entry/2015/12/23/164517
//Comprendre
#include<algorithm>//sort,Recherche de bisection,Tel
#include<bitset>//Jeu de bits de longueur fixe
#include<cmath>//pow,journal etc.
#include<complex>//Nombre complexe
#include<deque>//File d'attente d'accès double
#include<functional>//trier plus
#include<iomanip>//setprecision(Erreur de sortie en virgule flottante)
#include<iostream>//Entrée sortie
#include<map>//map(dictionnaire)
#include<numeric>//iota(Génération d'une chaîne entière),pgcd et lcm(c++17)
#include<queue>//queue
#include<set>//ensemble
#include<stack>//empiler
#include<string>//Chaîne
#include<unordered_map>//Carte avec itérateur mais sans ordre
#include<unordered_set>//Il y a un itérateur mais l'ordre n'est pas maintenu défini
#include<utility>//pair
#include<vector>//Tableau de longueur variable

using namespace std;
typedef long long ll;

//macro
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //Je souhaite omettre des arguments tels que le tri
#define SIZE(x) ((ll)(x).size()) //taille à la taille_Changement de t à ll
#define INF 1000000000000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second
const ll MAX=200000;

ll fac[MAX], finv[MAX], inv[MAX];

//Prétraitement pour faire une table
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        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 binaire
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(){
    COMinit();
    ll n,k;cin >> n >> k;
    vector<ll> a(n);REP(i,n) cin >> a[i];
    sort(ALL(a));
    ll ans=0;
    if(k==1){cout << 0 << endl;return 0;}
    //Pensez d'abord à MAX
    REP(i,n){
        ans+=(COM(i,k-1)*a[i]);
        ans%=MOD;
    }
    REP(i,n){
        ans-=(COM(n-i-1,k-1)*a[i]);
        if(ans<0){
            ans=MOD-abs(ans)%MOD;
        }else{
            ans%=MOD;
        }
    }
    cout << ans << endl;
}

Problème F

Je ne l'ai pas encore résolu, je suis désolé. Résolvez quand vous avez le temps! La géométrie n'a pas encore résolu une grande partie du problème, et je ne suis pas très douée pour cela ...

Recommended Posts

AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 072 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
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 070 Revue des questions précédentes
AtCoder Beginner Contest 105 Revue des questions précédentes
AtCoder Beginner Contest 112 Revue des questions précédentes
AtCoder Beginner Contest 076 Revue des questions précédentes
AtCoder Beginner Contest 089 Revue des questions précédentes
AtCoder Beginner Contest 069 Revue des questions précédentes
AtCoder Beginner Contest 079 Revue des questions précédentes
AtCoder Beginner Contest 056 Revue des questions précédentes
AtCoder Beginner Contest 087 Revue des questions précédentes
AtCoder Beginner Contest 067 Revue des questions précédentes
AtCoder Beginner Contest 093 Revue des questions précédentes
AtCoder Beginner Contest 046 Revue des questions précédentes
AtCoder Beginner Contest 123 Revue des questions précédentes
AtCoder Beginner Contest 049 Revue des questions précédentes
AtCoder Beginner Contest 078 Revue des questions précédentes
AtCoder Beginner Contest 081 Revue des questions précédentes
AtCoder Beginner Contest 047 Revue des questions précédentes
AtCoder Beginner Contest 060 Revue des questions précédentes
AtCoder Beginner Contest 104 Revue des questions précédentes
AtCoder Beginner Contest 057 Revue des questions précédentes
AtCoder Beginner Contest 121 Revue des questions précédentes
AtCoder Beginner Contest 126 Revue des questions précédentes
AtCoder Beginner Contest 090 Revue des questions précédentes
AtCoder Beginner Contest 103 Revue des questions précédentes
AtCoder Beginner Contest 061 Revue des questions précédentes
AtCoder Beginner Contest 059 Revue des questions précédentes
AtCoder Beginner Contest 044 Revue des questions précédentes
AtCoder Beginner Contest 083 Revue des questions précédentes
AtCoder Beginner Contest 048 Revue des questions précédentes
AtCoder Beginner Contest 124 Revue des questions précédentes
AtCoder Beginner Contest 116 Revue des questions précédentes
AtCoder Beginner Contest 097 Revue des questions précédentes
AtCoder Beginner Contest 088 Revue des questions précédentes
AtCoder Beginner Contest 092 Revue des questions précédentes
AtCoder Beginner Contest 099 Revue des questions précédentes
AtCoder Beginner Contest 065 Revue des questions précédentes
AtCoder Beginner Contest 053 Revue des questions précédentes
AtCoder Beginner Contest 094 Revue des questions précédentes
AtCoder Beginner Contest 063 Revue des questions précédentes
AtCoder Beginner Contest 107 Revue des questions précédentes
AtCoder Beginner Contest 071 Revue des questions précédentes
AtCoder Beginner Contest 064 Revue des questions précédentes
AtCoder Beginner Contest 082 Revue des questions précédentes
AtCoder Beginner Contest 084 Revue des questions précédentes
AtCoder Beginner Contest 068 Revue des questions précédentes
AtCoder Beginner Contest 058 Revue des questions précédentes
AtCoder Beginner Contest 043 Revue des questions précédentes
AtCoder Beginner Contest 098 Revue des questions précédentes