Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Ab heute möchte ich vorerst mit ABC (6 Fragen) nach 126 fortfahren. Persönlich denke ich, dass das Problem heutzutage komplexer geworden ist. Tragen Sie es also unbedingt. Ich würde es gerne anhängen. Auch diesmal konnte ich es komplett fertigstellen. Ich habe das F-Problem ohne viele Beweise bestanden und möchte es daher unbedingt überprüfen.

Problem A

Ich habe die Funktion zum Konvertieren in Kleinbuchstaben vergessen und die Groß- und Kleinschreibung durch A, B oder C geteilt. Es ist auch die Kleinfunktion, die in Kleinbuchstaben konvertiert wird, mit der Sie schönen Code schreiben können (den zweiten Code). Ist es nicht schwierig für ein Problem?

`A.py`


n,k=map(int,input().split())
s=input()
if s[k-1]=="A":
    print(s[:k-1]+"a"+s[k:])
elif s[k-1]=="B":
    print(s[:k-1]+"b"+s[k:])
else:
    print(s[:k-1]+"c"+s[k:])

`A_shorter.py`


n,k=map(int,input().split())
s=input()
print(s[:k-1]+s[k-1].lower()+s[k:])

B-Problem

Der mögliche Monat (MM) ist 00-12. Behalten Sie diesen also als Kandidaten für den Monat (cand) bei und verwenden Sie ihn als Kandidaten für den Monat.

`B.py`


s=input()
cand={"0"+str(i) if i<10 else str(i) for i in range(1,13)}
if s[:2] in cand and s[2:] in cand:
    print("AMBIGUOUS")
elif s[:2] in cand:
    print("MMYY")
elif s[2:] in cand:
    print("YYMM")
else:
    print("NA")

C-Problem

Ich habe darüber nachgedacht, die Obergrenze des Protokolls zu übernehmen, aber diesmal habe ich es vermieden, weil der Bruch einen Fehler enthält. Die einzige Möglichkeit für Sunuke, zu gewinnen, besteht darin, sich zu zeigen, bis es ** K oder höher ** ist (denn wenn Sie $ \ weil $ umdrehen, ist es 0 und Sie verlieren). Daher ist es ausreichend, die Anzahl der Male zu zählen, bis es K oder mehr wird, aber da der Wert der ersten Würfel 1 bis N sein kann, kann die Lösung durch $ O (N \ log N) $ gefunden werden.

`C.py`


n,k=map(int,input().split())
ans=0
for i in range(1,n+1):
    j,now=0,i
    while now<k:
        j+=1
        now*=2
    ans+=(2**(-j))
print(ans/n)

D Problem

Nur weil es ein Baum ist, heißt das nicht, dass Sie bereit sein sollten, also müssen Sie ruhig sein. Unter den Bedingungen dieses Problems gibt es immer eine Möglichkeit zu malen, die dem Motiv entspricht. Konzentrieren wir uns nun auf einen bestimmten Höhepunkt. Zu diesem Zeitpunkt kann gesagt werden, dass die mit den Scheitelpunkten verbundenen Scheitelpunkte ** dieselbe Farbe haben, wenn die Länge der Seite, die die beiden Scheitelpunkte verbindet, gerade ist, und unterschiedliche Farben **, wenn die Länge ungerade ist. Dies kann an jedem Scheitelpunkt gesagt werden. Wenn Sie also den Startpunkt entsprechend festlegen und ihm eine Suche mit Tiefenpriorität folgen, können Sie die Lösung mit $ O (M + N) $ finden.

(Der Punkt ist, es in die einfache Frage zu stellen, was an einem bestimmten Höhepunkt passiert.)

`answerD.py`


import sys
sys.setrecursionlimit(10**6)
n=int(input())
path=[[] for i in range(n)]
for i in range(n-1):
    u,v,w=map(int,input().split())
    path[u-1].append((v-1,w%2))
    path[v-1].append((u-1,w%2))
ans=[0]+[-1]*(n-1)
def dfs(i):
    global n,path,ans
    for j in path[i]:
        if ans[j[0]]==-1:
            if j[1]:
                ans[j[0]]=1-ans[i]
                dfs(j[0])
            else:
                ans[j[0]]=ans[i]
                dfs(j[0])
dfs(0)
print("\n".join(map(str,ans)))

E Problem

Es ist viel einfacher zu lösen, weil es besagt, dass es unter den gegebenen Bedingungen keinen Widerspruch gibt. Da es nur zwei Arten jeder Karte gibt, werde ich zuerst die ** vollständige Suche ** in Betracht ziehen, aber ich werde diese Richtlinie ablehnen, da dies offensichtlich unmöglich ist.

Hier muss nur bestimmt werden, ob $ A_ {x_i} + A_ {y_i} + Z_i $ gerade ist, und da $ Z_i $ bekannt ist, ist einer von ** $ A_ {x_i} $ und $ A_ {y_i} $ Wenn Sie es wissen, wird der andere definitiv entschieden **. Daher ist ersichtlich, dass die Anzahl jeder Karte ** in einer Kette durch die bekannten Informationen $ A_ {x_i} + A_ {y_i} + Z_i $ ** bestimmt wird, so dass ** die in einer Kette bestimmten Karten dieselbe Menge sind. Sie können Union Find Tree (Elementary Set Forest) verwenden, um als ** zu verwalten. Natürlich können Sie sich $ A_ {x_i} + A_ {y_i} + Z_i $ als Vereinigung von $ A_ {x_i} $ und $ A_ {y_i} $ vorstellen.

Außerdem möchte ich herausfinden, wie viele Primmengen sich in der ** Primmengenmenge ** befinden, also nach Verwendung der Gruppierungsfunktion in Union Find Library die Mitgliedsvariablen Finden Sie einfach die Größe der Gruppe, die ist.

Die Implementierung sieht folgendermaßen aus:

Außerdem ist ** wie viele Elementarsätze sich in der Gesamtstruktur befinden ** im Allgemeinen ** die verkettete Komponente (die größte der Teilgraphen, bei denen ein Pfad zwischen zwei beliebigen Scheitelpunkten besteht). Es ist der gleiche Wert wie die Zahl ** und wird in dieser Lösung wie in der letzteren geschrieben.

`E.cc`


//Einschließen(Alphabetischer Reihenfolge)
#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 Enden)、のどちらOder
//Schleifenvariablen ohne D werden um 1 erhöht, und Schleifenvariablen mit D werden 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 1000000007 //10^9+7:Gemeinsames Recht
#define MAXR 100000 //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

//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 Primmenge 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);//Empfangswurzel von x
        ll ry=root(y);//y root ry
        if(rx==ry) return; //Wenn im selben Baum
        //Kleinen Satz zu großem Satz 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,m;cin >> n >> m;
    UnionFind uf(n);
    REP(i,m){
        ll x,y,z;cin >> x >> y >> z;
        uf.unite(x-1,y-1);
    }
    REP(i,n)uf.root(i);
    uf.grouping(n);
    cout << SIZE(uf.group) << endl;
}

F Problem

Ich habe ein bequemes Muster erstellt und eine entsprechende Antwort gegeben, also Antwort und [ARMERIAs Blog](https: // betrue12). Ich habe es unter Bezugnahme auf Hassblo.jp/entry/2019/05/20/213302) überprüft. (Ich denke jedoch, dass es nicht viele Leute gibt, die während des Wettbewerbs AC beweisen ...?)

Zuallererst war es ein Problem von $ xor $, also entschied ich mich, eines für jedes Bit zu entscheiden, aber ** Ich bemerkte, dass es zu viele Muster gab und gab auf ** (Wenn das nicht möglich ist, gib einmal auf !!).

Als nächstes entschied ich mich, mich auf zwei gleiche ganze Zahlen zu konzentrieren. Hier wird ** $ xor $ zwischen denselben ganzen Zahlen zu $ 0 $ **. Wenn Sie sie also so anordnen, dass sie wie in der folgenden Abbildung gezeigt miteinander gepaart sind, ändert sich $ xor $ von $ a_i $ zu $ a_j $. Ich dachte, es wäre praktisch, weil es gleich $ xor $ von $ a_ {i + 1} $ bis $ a_ {j-1} $ ist.

Wenn $ j-i + 1 $ gerade hier ist, können alle ganzen Zahlen zusammengefasst werden, um das gesamte $ xor $ 0 $ zu bilden. Wenn also $ K $ $ 0 $ ist, Erstellen Sie wie oben gezeigt mit $ i = 1, j = 2 ^ {M + 1} $.

Ich habe es eingereicht, weil ich dachte, dass es nur dieses Muster gibt, also wurde es WA, aber als ich ** wechselte und weiter überlegte **, stellte ich fest, dass es auch ein Muster gibt, bei dem $ j-i + 1 $ ungerade wird, wie in der folgenden Abbildung gezeigt. Ich tat.

Zu diesem Zeitpunkt ist es durch Einfügen von $ K $ dazwischen, wie in der obigen Abbildung gezeigt, möglich, ein Paar zu erstellen, das die Bedingungen für andere Ganzzahlen als $ K $ erfüllt (da es zwischen ihnen liegt, ist ** $ K $ $ 0 $ oder mehr. Muss kleiner als $ 2 ^ M $ ** sein.). Dieses Muster existiert auch, wenn das XOR aller anderen Ganzzahlen als $ K $, die in dem Teil zwischen $ K $ enthalten sind, berechnet wird und zu $ K $ wird.

Außerdem war es schwer zu glauben, dass es ein anderes als dieses Muster mit hoher Symmetrie gab (** ← zu rau **), so dass ich AC konnte, wenn ich es auf -1 setzte, mit Ausnahme der beiden oben genannten Muster. Tatsächlich kann nachgewiesen werden, dass es kein anderes Muster gibt, so dass es unten gezeigt wird.

Beweis

Bis oben haben wir gezeigt, dass es eine Zahlenfolge gibt, die die Bedingung erfüllt, wenn $ k = 0 $ ((1)) ist (das Muster in der ersten Abbildung).

Hier wird "Wenn $ 0 \ leqq K <2 ^ M $, $ xor $, erhalten durch Subtrahieren von $ K $ von der Zahl von $ 0 $ oder mehr und weniger als $ 2 ^ M $, zu $ K $. "Exists" (②) wird zuerst angezeigt (das Muster in der zweiten Abbildung), und dann gibt es keine Zahlenfolge, die die Bedingung erfüllt, wenn $ k \ geqq 2 ^ M $ (③).

Wenn hier ** $ xoder $ von zwei aufeinanderfolgenden ganzen Zahlen $ 2a, 2a + 1 $ ($ a $ ist eine ganze Zahl) verwendet wird, wird 1, ** die Gesamtzahl der Zahlen größer oder gleich $ 0 $ und kleiner als $ 2 ^ M $ Für $ xor $ von $ M \ geqq 2 $ können Sie eine gerade Anzahl von Paaren zweier aufeinanderfolgender Ganzzahlen $ 2a, 2a + 1 $ bilden ($ a $ ist eine Ganzzahl) **. Daher ist die Summe $ xor $ $ 0 $, weil es eine gerade Anzahl von Paaren gibt, bei denen $ xor $ $ 1 $ ist ($ \ weil $$ xor $ Additionssatz).

Wenn die Summe $ xor $ der Anzahl von $ 0 $ oder mehr und weniger als $ 2 ^ M $ $ 0 $ beträgt, wird $ xor $ ohne $ K $ zu $ K $ ** ($ \ weil $$) Es wird gezeigt, dass das obige Muster für K \ xor \ K = 0 $) und $ M \ geqq 2 $ gilt.

Wenn $ M = 0 $ und $ M = 1 $ ist, ist die Anzahl von ** insgesamt $ xor $, die größer oder gleich $ 0 $ und kleiner als $ 2 ^ M $ ist, nicht $ 0 $, also ist $ xor $ ohne $ K $ Es wird nicht zu $ K $, und selbst wenn Sie mögliche Fälle aufschreiben, können Sie keine Zahlenfolge erstellen, die die Bedingungen erfüllt.

Daher wurde ② gezeigt.

Darüber hinaus gibt es im Fall von $ k \ geqq 2 ^ m $ einige Bits, die $ M $ oder höher sind und 1 werden, aber die Anzahl von $ 0 $ oder mehr und weniger als $ 2 ^ M $ ist $ M $ oder höher. Es gibt nichts, was zu 1 wird, also existiert es auch in diesem Fall nicht. Daher wurde ③ gezeigt.

Aus (1), (2) und (3) oben können Sie zeigen, dass Ihre Lösung notwendig und ausreichend ist.

`F.py`


from itertools import chain
m,k=map(int,input().split())
if k==0:
    print(" ".join([str(i) for i in chain(range(0,2**m),range(2**m-1,-1,-1))]))
elif 0<k<2**m:
    s=0
    for i in range(0,2**m):
        if i!=k:
            s^=i
    if s==k:
        print(" ".join([str(i) for i in chain(range(0,k),range(k+1,2**m),[k],range(2**m-1,k,-1),range(k-1,-1,-1),[k])]))
    else:
        print(-1)
else:
    print(-1)

`F_shortest.py`


m,k=map(int,input().split());x=list(range(2**m));print(*x[::-1]+x if k<1 else x[:k:-1]+x[k-1::-1]+[k]+x[:k]+x[k+1:]+[k]if(k<2**m)&(m>1)else[-1])

[PYTHON] AtCoder Beginner Contest 126 Rückblick auf frühere Fragen

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Problem A

A.py

A_shorter.py

B-Problem

B.py