[PYTHON] Yukicoder-Wettbewerb 261 Bewertung

Ergebnis

Impressionen

Ich habe mich immer wieder mit dem C-Problem beschäftigt, das ich für einfach hielt, es ist schmerzhaft ... Obwohl ich bei einer großen Explosion gestorben bin, konnte ich das C-Problem in letzter Minute lösen, und wenn ich ruhig war, konnte ich vier Fragen lösen, sodass ich meine Bemühungen so fortsetzen werde, wie sie sind.

Problem A

Es wird nicht so groß sein, also kannst du es 100 Mal machen.

A.py

def calc(n):
    ret=0
    while n!=0:
        ret+=(n%10)
        n//=10
    return ret
N=int(input())
for i in range(100):
    N=calc(N)
print(N)

B-Problem

Ich dachte, es wäre schwierig, wenn $ N $ gerade wäre, und als ich nach dem Wettbewerb zurückblickte, war $ N $ nur seltsam. Es ist sehr enttäuschend, das seltsame Muster in ungefähr 5 Minuten zu kennen ...

Im Falle einer solchen Konstruktion ist es schwierig, sich für die dunklen Wolken zu entscheiden, also ** denke ich, dass ich die Regeln zuerst selbst entscheide **. Dieses Mal ** entscheiden Sie, dass die Zahlen in jeder Zeile fortlaufend sind. Wenn $ N = 5 $ ist, habe ich die folgenden zwei Muster berücksichtigt, aber im ersten Muster erfüllen die Zeilen- und Diagonalkomponenten die Bedingung, aber die Spalte erfüllt die Bedingung nicht, also das zweite Muster Ist die richtige Antwort.

(Kontinuierlich von links nach rechts)
12345
12345
12345
12345
12345

(Kontinuierlich von rechts nach links)
15432
32154
54321
21543
43215

Außerdem habe ich die obige Matrix implementiert, indem ich festgestellt habe, dass das letzte Element jeweils +2 ist.

B.py

n=int(input())
ans=[]
st=2
if n==1:exit(print(1))
for i in range(n):
    now=[(st+i)%n if st+i!=n else n for i in range(n)][::-1]
    st+=2
    st%=n
    if st==0:st=n
    print(" ".join(map(str,now)))

C-Problem

Es ist relativ einfach zu sehen, was Sie tun, aber Sie müssen darauf achten, nicht ** mehrmals gesucht ** zu suchen. Im Folgenden wird die Station als oben umschrieben.

Überprüfen Sie zunächst das folgende Beispiel am Anfang.

5 4 6
0 2 5 7 8

Unter Berücksichtigung der oben beschriebenen Teilmengen, die durch Kanten verbunden sind, sollte im Fall eines Index, der in einer bestimmten Teilmenge $ X $ enthalten ist, die Größe von $ X $ berechnet werden. Darüber hinaus können Sie eine Sammlung von gegenseitig elementaren Teilmengen, die nicht durch Kanten ** verbunden sind, als elementare Mengenfamilie betrachten und diese mithilfe des ** Union Find-Baums ** einfach verwalten.

Hier werden die zu vereinigenden Scheitelpunkte im Union Find-Baum in der Reihenfolge aus den Scheitelpunkten mit den kleinsten Koordinaten ausgewählt. Da jedoch Scheitelpunkte mit einem Abstand von A oder mehr und B oder weniger verbunden werden können, sind die Koordinaten der jetzt ausgewählten Scheitelpunkte $ C $, $ CB Sie können die Eckpunkte von $ oder mehr und $ CA $ oder weniger oder $ C + A $ oder mehr und $ C + B $ oder weniger auswählen. Wählen Sie außerdem die zu verbindende Seite ** aus den Scheitelpunkten mit kleinen Koordinaten aus. Da diese Seite bidirektional ist, können Sie die Scheitelpunkte auswählen, die $ C + A $ oder mehr und $ C + B $ oder weniger sind.

Darüber hinaus ist dieses Gerät allein in Bezug auf den Berechnungsbetrag nicht gut. Dies liegt daran, dass der schlechteste Rechenaufwand durch Auswahl eines Scheitelpunkts zwischen $ C + A $ und $ C + B $ $ O (N ^ 2 \ alpha (n)) $ ist. $ \ Alpha (n) $ ist die Umkehrung der Ackermann-Funktion $ A (n, n) $ und scheint kleiner als $ \ log {n} $ zu sein (diese Folie Siehe / union-find-49066733)).

Um die gesuchten Scheitelpunkte zu berücksichtigen: Wenn die Koordinaten der Scheitelpunkte, die Sie betrachten, $ C $ und die Koordinaten der Scheitelpunkte, die Sie unmittelbar zuvor betrachten, $ C '$ sind, ist das Ergebnis wie in der folgenden Abbildung dargestellt (**) Zeichne ein Diagramm !! **).

Folgen Sie in der obigen Abbildung den Scheitelpunkten in Richtung abnehmender Koordinaten in der Reihenfolge des größten Scheitelpunkts unter $ C + B $ und verbinden Sie die Seiten. Sie können die Suche mithilfe der Beendigungsmethode ** optimieren. Infolgedessen wird der Suchbereich nicht abgedeckt, sodass er zu $ O (N \ alpha (n)) $ wird und ein Hochgeschwindigkeitsprogramm geschrieben werden kann. Zusätzlich kann die Größe der Menge, die in der endgültig zu erhaltenden Elementarmengenfamilie enthalten ist, durch die Größenfunktion mit $ O (1) $ berechnet werden.

C.cc

//Debug-Optionen:-fsanitize=undefined,address

//Compileroptimierung
#pragma GCC optimize("Ofast")

//Einschließen usw.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//Makro
//für Schleife
//Das Argument ist(Variablen in der Schleife,Bewegungsumfang)Oder(Variablen in der Schleife,Erste Nummer,Anzahl der Enden)、のどちら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.
//FORA ist ein Bereich für Aussagen(Wenn es schwer zu bedienen ist, löschen Sie es)
#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 ist ein Container wie ein Vektor
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//Konstante
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Gemeinsames Recht
#define MAXR 100000 //10^5:Maximale Reichweite des Arrays
//Abkürzung
#define PB push_back //Einfügen
#define MP make_pair //Paarkonstruktor
#define F first //Das erste Element des Paares
#define S second //Das zweite Element des Paares

//Unten repräsentieren die Primzahl und der Baum dasselbe.
class UnionFind {
public:
    vector<ll> parent; //parent[i]Ist der Elternteil von i
    vector<ll> siz; //Ein Array, das die Größe der Primzahl darstellt(Initialisieren Sie mit 1)
    map<ll,vector<ll>> group;//Assoziatives Array, das für jeden Primsatz verwaltet wird(Schlüssel ist das übergeordnete Element jeder Primzahl, Wert ist ein Array von Elementen dieser Primzahl)

    //Vom Konstruktor:Initialisieren Sie Mitgliedsvariablen nach
    UnionFind(ll n):parent(n),siz(n,1){ 
        //Zunächst wird als Wurzel aller Elemente selbst initialisiert
        for(ll i=0;i<n;i++){parent[i]=i;}
    }

    ll root(ll x){ //Holen Sie sich die Wurzel des Baums, zu dem Daten x gehören
        if(parent[x]==x) return x;
        return parent[x]=root(parent[x]);
        //Der Wert des Zuweisungsausdrucks ist der Wert der zugewiesenen Variablen
        //Pfadkomprimierung(Optimieren Sie Berechnungen, indem Sie Elemente direkt mit der Wurzel verbinden)Es wird durchgeführt
    }

    void unite(ll x,ll y){ //X- und y-Bäume zusammenführen
        ll rx=root(x);//Die Wurzel von x ist rx
        ll ry=root(y);//y root ry
        if(rx==ry) return; //Wenn im selben Baum
        //Kleine Menge zu großer Menge zusammenführen(Zusammengeführt von ry zu rx)
        if(siz[rx]<siz[ry]) swap(rx,ry);
        siz[rx]+=siz[ry];
        parent[ry]=rx; //Wenn sich x und y nicht im selben Baum befinden, hängen Sie y root ry an x root rx an
    }

    bool same(ll x,ll y){//Bestimmen Sie, ob der Baum, zu dem x und y gehören, identisch ist
        ll rx=root(x);
        ll ry=root(y);
        return rx==ry;
    }

    ll size(ll x){ //Ermitteln Sie die Größe der Primzahl von x
        return siz[root(x)];
    }

    //↓ Funktionen, die sich nicht in den Bibliotheken anderer Personen befinden, aber nützlich sind
    //O(n)Beachten Sie, dass
    void grouping(ll n){//Elementarsätze gruppieren
        REP(i,n){
            if(group.find(parent[i])==group.end()){
                group[parent[i]]={i};
            }else{
                group[parent[i]].PB(i);
            }
        }
    }
};

signed main(){
    //Code zur Beschleunigung der Eingabe
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n,a,b;cin>>n>>a>>b;
    vector<ll> x(n);
    REP(i,n)cin>>x[i];
    UnionFind u(n);
    //Überprüfe nicht zu viel
    REP(i,n){
        ll now=upper_bound(ALL(x),x[i]+b)-x.begin();now--;
        //Ist es hier?
        //Von oben
        while(now>=0){
            if(x[now]<x[i]+a)break;
            if(u.same(i,now))break;
            u.unite(i,now);
            now--;
        }
    }
    REP(i,n)cout<<u.size(i)<<endl;
}

D Problem

Es war ein einfaches, aber interessantes Problem.

Wenn sich die Zeichen vor und nach ** bei Auswahl einer Unterspalte unterscheiden, erhöht sich die Anzahl der Läufe um eins. Daher dachte ich, es wäre gut, ** das letzte Zeichen ** zu speichern, wenn die Zeichenfolge $ S $ von vorne gescannt wird. Darüber hinaus gibt es am Ende höchstens 26 Zeichentypen (** Status **), und es scheint, dass der Übergang beim Scannen leicht definiert werden kann. Deshalb habe ich beschlossen, ihn mit DP zu lösen.

Daher haben wir DP zunächst wie folgt definiert:

$ dp [i] [j]: = $ (Anzahl der Läufe, wenn das letzte Alphabet $ j $ ist (= 0 ~ 25), wenn das Zeichen $ i $ festgelegt wird)

Mit dieser Definition funktioniert die Addition jedoch nicht, wenn der Übergang von $ dp [i-1] $ zu $ dp [i] $ berücksichtigt wird. Wenn Sie die erforderlichen Informationen hier überprüfen, werden Sie feststellen, dass die Anzahl der Zeichenfolgen **, wenn Sie sich für das Zeichen ** $ i $ entscheiden, für die Berechnung der Anzahl der Läufe erforderlich ist. Mit anderen Worten sollte DP wie folgt definiert werden.

$ dp [i] [j]: = $ (wenn das letzte Alphabet $ j $ ist (= 0 ~ 25), wenn das $ i $ -Zeichen festgelegt wird (Anzahl der Zeichenketten, Anzahl der Läufe))

Mit dieser Definition kann der Übergang implementiert werden, indem das Zeichen $ i $ in drei Fälle unterteilt wird: (1) Auswählen des ersten Zeichens der Teilzeichenfolge, (2) Einschließen in die Teilzeichenfolge und (3) Nichteinschließen in die Teilzeichenfolge. Ich kann es schaffen Nehmen Sie außerdem an, dass das Alphabet des Zeichens $ i $ $ d $ ist und das dp-Array 0-initialisiert ist.

(1) Bei Auswahl des Zeichens $ i $ als erstes Zeichen in der Teilzeichenfolge dp[i][d][0]+=1 dp[i][d][1]+=1

(2) Wenn das Zeichen $ i $ nicht in der Unterspalte enthalten ist dp[i][j][0]+=dp[i-1][j][0] dp[i][j][1]+=dp[i-1][j][1]

(3) Wenn das Zeichen $ i $ in der Unterspalte enthalten ist [1] Wenn $ j = d $ dp[i][d][0]+=dp[i-1][j][0] dp[i][d][1]+=dp[i-1][j][1] [2] Wenn $ j \ neq d $ (Lauf erhöht sich um den Betrag der Zeichenfolge) dp[i][d][0]+=dp[i-1][j][0] dp[i][d][1]+=(dp[i-1][j][0]+dp[i-1][j][1])

(Das Problem der Teilmenge ist, dass der Übergang leicht zu verstehen ist, wenn Sie darauf achten, ob Sie das Element auswählen oder nicht. Es ist also einer der DPs, an die Sie sich gewöhnen möchten.)

Dies wird auch die Summe der Läufe von $ dp [n-1] $ finden, aber wenn es so bleibt, wie es ist, wird es MLE sein. Da der Übergang nur $ i-1 \ rightarrow i $ ist, können Sie ** den Umfang der räumlichen Berechnung reduzieren, indem Sie nur diese beiden ** speichern.

D_MLE.py

s=input()
n=len(s)
#dp[i][j]:=Wenn das i-te Zeichen festgelegt ist, wird es zum Alphabet j(Anzahl der Zeichenketten,Anzahl der Läufe)
#Es ist selten, ein Paar zu bilden, aber wenn Sie es auch nicht wissen, können Sie sich nicht entscheiden.
#Wurde MLE
dp=[[[0,0] for i in range(26)] for i in range(n)]
mod=10**9+7
for i in range(n):
    d=ord(s[i])-97
    #Neu hinzugefügt
    dp[i][d]=[1,1]
    if i==0:continue
    #Wenn Sie nicht wählen(Wird nicht zunehmen)
    for j in range(26):
        dp[i][j][0]+=dp[i-1][j][0]
        dp[i][j][0]%=mod
        dp[i][j][1]+=dp[i-1][j][1]
        dp[i][j][1]%=mod
    #Bei der Wahl(Wenn es anders ist, erhöht es sich um die Nummer der Zeichenkette)
    for j in range(26):
        if j==d:
            dp[i][j][0]+=dp[i-1][j][0]
            dp[i][j][0]%=mod
            dp[i][j][1]+=dp[i-1][j][1]
            dp[i][j][1]%=mod
        else:
            dp[i][d][0]+=dp[i-1][j][0]
            dp[i][d][0]%=mod
            dp[i][d][1]+=(dp[i-1][j][0]+dp[i-1][j][1])
            dp[i][d][1]%=mod
ans=0
for j in range(26):
    ans+=dp[n-1][j][1]
    ans%=mod
print(ans)

D_AC.py

s=input()
n=len(s)
#dp[i][j]:=Wenn das i-te Zeichen festgelegt ist, wird es zum Alphabet j(Anzahl der Zeichenketten,Anzahl der Läufe)
#Es ist selten, ein Paar zu bilden, aber wenn Sie es auch nicht wissen, können Sie sich nicht entscheiden.
#Wurde MLE
#Machen Sie dp nicht zu einem Array
x,y=[[0,0] for i in range(26)],[[0,0] for i in range(26)]
mod=10**9+7
for i in range(n):
    d=ord(s[i])-97
    #Neu hinzugefügt
    if i==0:
        x[d]=[1,1]
        continue
    #Wenn Sie nicht wählen(Wird nicht zunehmen)
    for j in range(26):
        y[j][0]=x[j][0]
        y[j][0]%=mod
        y[j][1]=x[j][1]
        y[j][1]%=mod
    y[d][0]+=1
    y[d][1]+=1
    #Bei der Wahl(Wenn es anders ist, erhöht es sich um die Nummer der Zeichenkette)
    for j in range(26):
        if j==d:
            y[j][0]+=x[j][0]
            y[j][0]%=mod
            y[j][1]+=x[j][1]
            y[j][1]%=mod
        else:
            y[d][0]+=x[j][0]
            y[d][0]%=mod
            y[d][1]+=(x[j][0]+x[j][1])
            y[d][1]%=mod
    x,y=y,x
ans=0
for j in range(26):
    ans+=x[j][1]
    ans%=mod
print(ans)

Nach dem E-Problem

Ich werde diesmal nicht lösen.