[PYTHON] AtCoder Anfängerwettbewerb 167 Bewertung

Die Ergebnisse dieser Zeit

✳︎ AC-Prädiktor funktioniert nicht und es gibt keine Leistung, aber es war 1664.

Eindrücke dieser Zeit

Ich denke, diesmal hat es einigermaßen gut funktioniert. Es war relativ einfach, sich etwas auszudenken, da es in der Vergangenheit in D und E ähnliche Fragen gab. Es gab jedoch Zeiten, in denen die Implementierung fehlerhaft war, daher möchte ich vermeiden, mit solchen Fehlern ungeduldig zu sein. Außerdem habe ich das F-Problem ganz am Ende richtig betrachtet, daher möchte ich vorsichtig sein.

Problem A

Sie müssen nur beurteilen, ob s gleich der Zeichenfolge ohne das Ende von t ist.

A.py

s=input()
t=input()
print("Yes" if s==t[:-1] else "No")

B-Problem

Beginnen Sie mit der größten Anzahl von Karten.

B.py

a,b,c,k=map(int,input().split())
if a>=k:
    print(k)
elif a+b>=k:
    print(a)
else:
    print(a-(k-a-b))

C-Problem

Aufgrund des C-Problems ist es Zeit für eine vollständige Bit-Suche ... Es ist schwer, weil das Niveau der AtCoder-Teilnehmer steigt und mithält. Ich werde mein Bestes tun, um nicht zu verlieren.

Betrachten Sie zunächst eine vollständige Suche (** Zweifeln Sie nicht an der DP, zuerst eine vollständige Suche **). Zu diesem Zeitpunkt müssen Sie nur darüber nachdenken, welches Nachschlagewerk Sie auswählen müssen, und der zu wählende Rechenaufwand beträgt $ O (n \ times 2 ^ n) $. Wie stark sich das Verständnisniveau jedes Algorithmus bei Auswahl eines Nachschlagewerks erhöht, wird mit $ O (m) $ berechnet. Nach der Entscheidung, welches Nachschlagewerk ausgewählt werden soll, beträgt das Verständnisniveau aller Algorithmen X oder höher. Da das Urteil mit $ O (m) $ getroffen werden kann, kann es mit $ O (2 ^ n \ mal (n \ mal m + m)) = O (2 ^ n \ mal n \ mal m) $ berechnet werden. Daher können Sie ein Programm schreiben, das das Zeitlimit einhält. Selbst wenn Sie alle Nachschlagewerke kaufen, können Sie möglicherweise nicht alle Algorithmen über X verstehen. Deshalb habe ich sie mit inf (= 100000000000000000) initialisiert.

Außerdem habe ich die Zeile (✳︎) in die for-Anweisung in der nächsten Zeile eingefügt, um sie fehlerhaft zu machen. Es ist zu verrückt. Ich konnte jedoch versuchen, Fehler mit einem Beispiel zu entfernen, also ist es ein guter Punkt.

C.py

n,m,x=map(int,input().split())
ca=[list(map(int,input().split())) for i in range(n)]
ans=100000000000000000
for i in range(2**n):
    check=[0]*m
    ans_=0
    for j in range(n):
        if ((i>>j)&1):
            ans_+=ca[j][0]#(✳︎)
            for k in range(m):
                check[k]+=ca[j][k+1]
    if all([l>=x for l in check]):
        ans=min(ans,ans_)
if ans==100000000000000000:
    print(-1)
else:
    print(ans)

D Problem

Der einfachste Weg ist, alle k Züge auszuführen, dies ist jedoch aufgrund von k Einschränkungen nicht möglich. Wenn Sie n-mal umziehen, ** gibt es eine Stadt, die Sie mehr als einmal besuchen ** (dieser Beweis wird weggelassen). Da die Städte, die nach der Stadt besucht wurden, die ich mehr als einmal besucht habe, immer von der Stadt i aus verfolgt werden können, wird in den Städten nach der Stadt i bis zum zweiten Besuch der Stadt i ** eine Schleife gebildet (Eingabe). In Beispiel 1 wird eine Schleife von 1 → 3 → 4 gebildet.) Überlegen Sie sich daher zunächst, eine Schleife zu entdecken. Wenn Sie jedoch die bereits besuchten Städte speichern, können Sie die Schleife entdecken, wenn Sie eine Stadt zweimal besuchen. Außerdem möchte ich ** O (1) verwenden, um festzustellen, ob eine Stadt zu besuchen ist, also speichere ich sie als Set **. ** Speichern Sie auch die Reihenfolge der besuchten Städte **, also speichern Sie die Reihenfolge der besuchten Städte in einem Array. Wenn die Schleife dadurch bestimmt werden kann, wird der Fall vor und nach dem Eintritt in die Schleife und wo in der Schleife K (mod) entspricht, verwendet, um zu bestimmen. Dieses Urteil usw. ist nicht schwierig (die Idee), daher werde ich es nur als Kommentar in den folgenden Code schreiben.

answerD.py

#Speichern Sie die Reihenfolge der Städtebesuche in einem Array
visited=[0]
#Speichern Sie die Städte, die Sie als Gruppe besucht haben
visited_set=set()
visited_set.add(0)
n,k=map(int,input().split())
a=list(map(int,input().split()))
#Die Stadt, in der next1 jetzt besucht, die Stadt, in der next2 als nächstes besucht
#Verlassen Sie die while-Schleife, wenn next2 bereits besucht ist
next1=0
next2=-1
while True:
    #In die nächste Stadt
    next2=a[next1]-1
    #Machen Sie es zu der Stadt, die Sie gerade besuchen
    next1=next2
    if next2 in visited_set:
        #Weil es eine Stadt ist, die ich bereits besucht habe
        break
    else:
        #In der richtigen Reihenfolge in das Array einfügen
        visited.append(next2)
        #In ein Set einfügen, das aufzeichnet, ob Sie besucht haben
        visited_set.add(next2)

#Wenn k kleiner als die Gesamtzahl der besuchten Städte ist, geben Sie die k-te Stadt so aus, wie sie ist
if k<len(visited):
    print(visited[k]+1)
else:
    #Finden Sie die Länge der Schleife(Ich neige dazu, hier einen Fehler zu machen, also habe ich ein Diagramm geschrieben)
    loop_len=(len(visited)-visited.index(next2))
    #Bis Sie die Schleife erreichen
    k-=(len(visited)-loop_len)
    #Angesichts des Restes der Schleifenlänge ist es leicht zu erkennen, wo Sie sich in der Schleife befinden.
    print(visited[k%loop_len+visited.index(next2)]+1)

E Problem

Ich persönlich hatte das Gefühl, dass es einfacher war als das D-Problem. Es war jedoch eine neue Ausgabe, daher bin ich froh, dass ich sie während des Wettbewerbs erfunden habe (ich war überrascht, dass ich sie gefunden habe).

Da n Blöcke nebeneinander angeordnet sind und die Methode des Malens mit m Farbe durch O (1) erhalten zu werden scheint, nahm ich an, dass es $ l $ Paare benachbarter Blöcke gibt. Wenn Sie die Farbe der Blöcke hier ganz links festlegen und die Farben der benachbarten Blöcke nicht unterschiedlich sind, $ m \ times (m-1) \ times (m-1) \ times (m-1) \ times … Es wird $ sein. Wenn andererseits der zweite Block derselbe ist, können wir sehen, dass es $ m \ times (m-1) \ times 1 \ times (m-1) \ times… $ ist. Daher dachte ich, dass es in Ordnung wäre, die Teile mit der gleichen Farbe in diesen benachbarten Blöcken zu ignorieren, also entschied ich mich, die Blöcke zu verbinden und sie als einen Block zu betrachten. Wenn es also $ l $ Paare benachbarter Blöcke gibt, können Sie ** eine Blocksequenz von $ n-l $ Länge in Betracht ziehen, die alle unterschiedliche Farben haben **. Außerdem gibt es $ _ {n-1} C _ {l} $, je nachdem, welcher Block dieselbe Farbe hat. Wenn also $ l $ Paare benachbarter Blöcke vorhanden sind, lautet die Farbmalmethode $ m . times (m-1) ^ {nl-1} \ times _ {n-1} C _ {l} $ Es wird dasselbe sein, und Sie können dies mit $ l = 0 ~ k $ berechnen. Die Antwort kann auch sehr groß sein, daher müssen Sie [Kombinationsberechnung durch Inverse von mod (= 998244353)] durchführen (https://qiita.com/DaikiSuyama/items/32706bc87c748edc301d). Wenn Sie es hier implementieren, während Sie ** beachten, dass die Berechnung der Leistung auch unter mod (= 998244353) ** durchgeführt werden muss, ist dies wie folgt.

✳︎ Ich habe übrigens eine Modint-Bibliothek, daher werde ich sie bald als Artikel veröffentlichen.

answerE.cc

//Referenz: http://ehafib.hatenablog.com/entry/2015/12/23/164517
//Einschließen(Alphabetischer Reihenfolge,bits/stdc++.Eine Fraktion, die h nicht benutzt)
#include<algorithm>//sort,Halbierungssuche,Eine solche
#include<bitset>//Bit mit fester Länge gesetzt
#include<cmath>//pow,Protokoll usw.
#include<complex>//Komplexe Zahl
#include<deque>//Double-Ended-Zugriffswarteschlange
#include<functional>//größer sortieren
#include<iomanip>//setprecision(Gleitkomma-Ausgabefehler)
#include<iostream>//Input-Output
#include<iterator>//Betrieb einstellen(Produktset,Summensatz,Differenzsatz etc.)
#include<map>//map(Wörterbuch)
#include<numeric>//iota(Generierung einer Ganzzahlzeichenfolge),gcd und lcm(c++17)
#include<queue>//Warteschlange
#include<set>//einstellen
#include<stack>//Stapel
#include<string>//String
#include<unordered_map>//Karte mit Iterator, aber ohne Ordnung
#include<unordered_set>//Es gibt einen Iterator, aber die Reihenfolge wird nicht festgelegt
#include<utility>//pair
#include<vector>//Array mit variabler Länge

using namespace std;
typedef long long ll;

//Makro
//für Schleifenbeziehung
//Das Argument ist(Variablen in der Schleife,Bewegungsumfang)Oder(Variablen in der Schleife,Erste Nummer,Anzahl der Endungen)、のどちらOder
//Wenn es kein D gibt, wird die Schleifenvariable um 1 erhöht, und wenn es ein D gibt, wird die Schleifenvariable um 1 dekrementiert.
#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--)
//x ist ein Container wie ein Vektor
#define ALL(x) (x).begin(),(x).end() //Ich möchte Argumente wie sort weglassen
#define SIZE(x) ((ll)(x).size()) //Größe zu Größe_Wechseln Sie von t nach ll
#define MAX(x) *max_element(ALL(x)) //Finden Sie den Maximalwert
#define MIN(x) *min_element(ALL(x)) //Finden Sie den Mindestwert
//Konstante
#define INF 1000000000000 //10^12:Extrem großer Wert,∞
#define MOD 998244353 //10^9+7:Gemeinsames Recht
#define MAXR 300000 //10^5:Maximale Reichweite des Arrays(Wird für die Aufzählung von Primzahlen usw. verwendet.)
//Abkürzung
#define PB push_back //In Vektor einfügen
#define MP make_pair //Paarkonstruktor
#define F first //Das erste Element des Paares
#define S second //Das zweite Element des Paares

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

//Eine Tabelle erstellen
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;
    }
}

//Berechnung des Binomialkoeffizienten
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;
}

ll modpow(ll a,ll n,ll mod){
    ll res = 1;
    while(n > 0){
        if(n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

signed main(){
    COMinit();
    ll n,m,k;cin >> n >> m >> k;
    ll ans=0;
    REP(l,k+1){
        ll ansx=1;
        ansx*=COM(n-1,l);
        ansx*=modpow(m-1,n-l-1,MOD);
        ansx%=MOD;
        ansx*=modpow(m,1,MOD);
        ansx%=MOD;
        ans+=ansx;
        ans%=MOD;
    }
    cout << ans << endl;
}

F Problem

Es ist ein Problem von Klammern, das oft auftritt, aber ich denke, es war ziemlich schwierig. Ich denke jedoch, dass ich es schon auf den ersten Blick lösen muss, also möchte ich mein Bestes geben. Erstens, wenn es eine Klammerzeichenfolge gibt, wenn ** (ist +1,) auf -1 gesetzt ist und die kumulative Summe von zuvor berücksichtigt wird, ist die Summe, wenn alle Elemente 0 oder mehr sind und am Ende hinzugefügt werden, 0 Alles was Sie brauchen ist **. Dieses Problem ist auch schwierig, da diese Bedingung auch in der Zeichenfolge erfüllt sein muss. Hier habe ich vorerst darüber nachgedacht, die Reihenfolge mit der größten kumulativen Summe jeder Zeichenkette in der Reihenfolge zu verketten, aber so wie es ist, besteht die Möglichkeit, dass sie in jeder Zeichenkette kleiner als 0 ist Sie müssen sicherstellen, dass die kumulative Summe innerhalb dieser Zeichenfolge immer positiv ist. Wenn beispielsweise der Mindestwert der kumulativen Summe einer bestimmten Zeichenfolge 0 oder mehr beträgt, ist die kumulative Summe aller Elemente unabhängig von der Reihenfolge, in der sie verbunden sind, immer 0 oder mehr. Daher ist das Problem ** für diejenigen, deren minimale kumulative Summe von Zeichenfolgen kleiner als 0 ** ist. Wenn Sie auf dieser Grundlage auf den Fall achten, dass die endgültige kumulative Summe einer bestimmten Zeichenfolge 0 oder mehr beträgt **, wenn Sie diese Zeichenfolge hinzufügen können, wird die kumulative Summe nicht reduziert und der Mindestwert zu diesem Zeitpunkt liegt unter 0. Je größer der Wert, desto besser. Daher ist es am besten, die Reihenfolge mit dem größten ** Mindestwert der kumulierten Summe der Zeichenfolgen ** gierig zu verketten. Auf der anderen Seite ist es nicht einfach, sich gierig zu entscheiden, wenn die endgültige kumulative Summe eines Strings kleiner als 0 ist. Ich habe darüber nachgedacht, was passieren würde, wenn ich es gierig tun würde, aber ich kann es lösen, indem ich mir [kmjps Blog] ansehe (https://kmjp.hatenablog.jp/entry/2020/05/10/0930). Ist fertig. Invertieren Sie einfach die Zeichenfolge und denken Sie darüber nach.

Ich habe es bisher geschrieben, aber wenn ich später darauf zurückblicke, verstehe ich es nicht so wie es ist, daher werde ich unten fast die gleiche Erklärung anhand von ** Diagrammen geben. Es tut mir leid, dass es viele überlappende Teile gibt. </ font>

import sys
n=int(input())
s=[input() for i in range(n)]
t=[2*(i.count("("))-len(i) for i in s]
if sum(t)!=0:
    print("No")
    sys.exit()
st=[[t[i]] for i in range(n)]

for i in range(n):
    now,mi=0,0
    for j in s[i]:
        if j=="(":
            now+=1
        else:
            now-=1
        mi=min(mi,now)
    st[i].append(mi)
#st.sort(reverse=True,key=lambda z:z[1])
u,v,w=list(filter(lambda x:x[1]>=0,st)),list(filter(lambda x:x[1]<0 and x[0]>=0,st)),list(filter(lambda x:x[1]<0 and x[0]<0,st))
v.sort(reverse=True)
v.sort(reverse=True,key=lambda z:z[1])
w.sort(key=lambda z:z[0]-z[1],reverse=True)
lu=len(u)
lv=len(v)
now2=0
for i in range(n):
    if i<lu:
        now2+=u[i][0]
    elif i<lu+lv:
        if now2+v[i-lu][1]<0:
            print("No")
            break
        now2+=v[i-lu][0]
    else:
        #Nein, hier ist es falsch.
        if now2+w[i-lu-lv][1]<0:
            print("No")
            break
        now2+=w[i-lu-lv][0]
else:
    print("Yes")

from itertools import accumulate,chain
n,*s=open(0).read().split()
u=[[min(accumulate(chain([0],t),lambda a,b: a+(1 if b=="(" else -1))),2*t.count("(")-len(t)] for t in s]
m=0
for c,d in chain(sorted([x for x in u if x[1]>=0])[::-1],sorted([x for x in u if x[1]<0],key=lambda z:z[0]-z[1])):
    if m+c<0:print("No");break
    m+=d
else:print("No" if m else "Yes")