[PYTHON] Codeforces Runde # 669 (Div. 2) Bacha Review (9/9)

Die Ergebnisse dieser Zeit

スクリーンショット 2020-09-13 0.07.19.png

Eindrücke dieser Zeit

Während des Wettbewerbs nervte ich für den Rest meines Lebens, ohne ** A's Gag ** zu bemerken. Dann hatte ich weniger Zeit zu D. Es war ein Teufelskreis.

Nachdem ich für den Rest meines Lebens einen Fehler in D gemacht habe, hätte ich nach dem Wettbewerb insgesamt ungefähr 4 Stunden verbracht, wenn ich das D-Problem richtig gelöst hätte, ohne das Problem zu berücksichtigen. Es ist mental nicht gut, also sollte diese Art von Problem sofort vorbei sein.

Ich konnte ** D nicht lösen, aber ich mag es wirklich **, also würde ich es gerne lösen können, wenn in Zukunft ähnliche Probleme auftauchen.

Problem A

Zuerst dachte ich darüber nach, den Unterschied zwischen 0 und 1 mit DP zu verwalten, aber ich fand es problematisch und konnte es nicht implementieren. Als ich es mir auf Twitter angesehen habe, gab es einige Leute, die es mit DP lösen konnten, also denke ich, dass dieser Bereich ** nicht genug Geist ** ist. Ich werde mich widmen.

Es ist einfach, wenn Sie den Knebel bemerken.

Am Ende sind noch mehr als $ \ frac {n} {2} $ übrig. Wählen Sie also ** bequem mehr als $ \ frac {n} {2} $ **. Eine einfache Idee ist es, ** alle ausgewählten Elemente auf 0 zu setzen **. Dies ist jedoch möglich, wenn mehr als $ \ frac {n} {2} $ 0s enthalten sind. Wenn 0 kleiner als $ \ frac {n} {2} $ ist, ist 1 $ \ frac {n} {2} + 1 $ oder mehr, aber wenn es eine gerade Zahl von ** 1 gibt, ist die Summe 0 **. Sie können $ \ frac {n} {2} $ oder $ \ frac {n} {2} + 1 $ 1s durch die Gleichmäßigkeit von $ \ frac {n} {2} $ ausgeben.

A.py


for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    if a.count(0)>=n/2:
        print(n//2)
        print(" ".join("0"*(n//2)))
    else:
        #Zu diesem Zeitpunkt ist 1 n//2+1 oder mehr
        if (n//2)%2==0:
            print(n//2)
            print(" ".join("1"*(n//2)))
        else:
            print(n//2+1)
            print(" ".join("1"*(n//2+1)))

B-Problem

Da die Problemstellung zusammenfassend etwas kompliziert ist, wird die Zahlenspalte $ c $ neu zur Zahlenspalte $ b $ hinzugefügt, indem die Reihenfolge $ a $ c \ _i = GCD (b \ _1, b \ _2,…, b ) neu angeordnet wird _i) Das Problem besteht darin, $ b $ zu finden, wenn $ c $ das Maximum in lexikalischer Reihenfolge ist, wenn es als $ definiert ist. Außerdem können Sie für $ b $ eine geeignete finden, die die Bedingungen erfüllt.

** Da es in lexikalischer Reihenfolge vorliegt, sollten Sie es ab dem ersten Element gierig erhöhen **. Wie Sie sehen können, ist das erste Element von $ b $ das größte Element von $ a $. Wenn Sie für das zweite und nachfolgende $ i $ -te Element nach der GCD ("jetzt") der ersten bis $ i-1 $ -ten Elemente fragen, ist dies die größte unter den "Jetzt" - und GCD-Elementen. Sie können das Element als nächstes Element auswählen. Darüber hinaus können Sie die Richtlinie ** $ O (N ^ 2) $ ** verwenden. Bereiten Sie daher ein Array check vor, um zu speichern, welches Element Sie ausgewählt haben, und das Element check [i] = False. Sie finden das Element, das die GCD maximiert, in der richtigen Reihenfolge.

B.py


from math import gcd
for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    check=[False]*n
    b=[0]*n
    b[0]=max(a)
    check[a.index(max(a))]=True
    now=b[0]
    for i in range(1,n):
        #Wert,Index
        max1=[-1,-1]
        for j in range(n):
            if not check[j]:
                if max1[0]<gcd(a[j],now):
                    max1=[gcd(a[j],now),j]
        check[max1[1]]=True
        b[i]=a[max1[1]]
        now=max1[0]
    print(" ".join(map(str,b)))

C-Problem

Ich habe zum ersten Mal ein interaktives Problem gelöst. Dieses Problem war nicht schwierig, aber ich möchte in der Lage sein, interaktive Probleme ohne Widerstand zu lösen.

Um diese Frage zusammenzufassen: "Wenn Sie für eine unbekannte Sequenz $ p $ aus 1 ~ $ n $ $ i, j $ übergeben, erhalten Sie $ p \ _i \ mod \ \ _ {p \ _ j} $. Wiederholen Sie es höchstens $ 2n $ mal, um $ p $ wiederherzustellen. "

Hier dachte ich, dass es in der Reihenfolge vom größten oder vom kleinsten Element entschieden werden würde. Zum Beispiel ist $ p \ _i \ mod \ \ _ {p \ _ j} = n-1 $ nur dann eindeutig, wenn $ (p \ _ i, p \ _j) = (n-1, n) $ Wenn Sie $ mod \ _ {n} $ verwenden, werden andere Elemente eindeutig bestimmt. Es ist jedoch schwierig, die Elemente ** $ n-1 $ und $ n $ zu finden, da es sich um $ O (n ^ 2) $ ** handelt. Ich habe das kleinste Element aufgegeben, weil es schwierig erscheint, es überhaupt eindeutig zu bestimmen.

Wenn Sie hier auf $ p \ _i \ mod \ \ _ {p \ _j} $ achten, wird $ p \ _i $ eindeutig bestimmt **, wenn ** $ p \ _j> p \ _i $. Mir ist aufgefallen. Die Größe kann jedoch nicht nur aus dem Wert von $ p \ _i \ mod \ \ _ {p \ _j} $ eindeutig bestimmt werden. Kombinieren Sie also ** $ p \ _ j \ mod \ \ _ {p \ _i} $. Ich dachte darüber nach, die Größe zu bestimmen **.

Angenommen, $ p \ _j > p \ _i $, $ p \ _i \ mod \ \ _ {p \ _j} = p \ _i $, $ p \ _j \ mod \ \ _ {p \ _i Die beiden Gleichungen von} \ <p \ _i $ gelten. Daher wird es zu $ p \ _i \ mod \ \ _ {p \ _j} > p \ _j \ mod \ \ _ {p \ _i} $. Im Gegenteil, wenn $ p \ _i \ mod \ \ _ {p \ _j} > p \ _j \ mod \ \ _ {p \ _i} $, $ p \ _j > p \ _i $ und $ p \ Da _i \ mod \ \ _ {p \ _j} = p \ _i $ gilt, können Sie $ p \ _i $ entscheiden.

Daher kann das kleinere Element bestimmt werden, indem ** $ p \ _i \ mod \ \ _ {p \ _ j} $ und $ p \ _ j \ mod \ \ _ {p \ _i} $ ** gefragt werden. Ich verstehe. Auf diese Weise können Sie für jedes Element $ n-1 $ Elemente in $ 2 (n-1) $ Zeiten von Fragen definieren. Außerdem ist das letzte verbleibende Element das größte Element, sodass es $ n $ ist.

Um ** sofort ausgeben ** zu können, muss in Python $ flush = True $ als Argument für die Druckfunktion angegeben werden. Ich benutze es immer für interaktive Probleme, deshalb möchte ich mich daran erinnern.

C.py


for _ in range(int(input())):
    n,k=map(int,input().split())
    s=input()
    t=[[] for i in range(k)]
    for i in range(n):
        t[i%k].append(s[i])
    #Wenn es etwas anderes gibt, nein zu diesem Zeitpunkt
    ans0,ans1=0,0
    ex=0
    for i in range(k):
        if t[i].count("0")>0 and t[i].count("1")>0:
            print("NO")
            break
        elif t[i].count("0")>0:
            ans0+=1
        elif t[i].count("1")>0:
            ans1+=1
        else:
            ex+=1
    else:
        if ex==0:
            if ans0==ans1:
                print("YES")
            else:
                print("NO")
        else:
            if ans0+ex>=k//2 and ans1+ex>=k//2:
                print("YES")
            else:
                print("NO")

D Problem

Obwohl ich nach dem Wettbewerb die richtige Antwort gefunden habe, ** habe ich viel Zeit verbracht, weil ich nicht berücksichtigt habe **. Ich möchte vor der Implementierung etwas Zeit haben, um zu überprüfen, ob die Lösung wirklich korrekt ist.

Die Diskussionen während des Wettbewerbs waren ziemlich schmutzig, daher würde ich gerne diejenigen in Betracht ziehen, die gut aussehen.

Erstens gibt es kein bestes Muster, um von rechts nach links zu springen. Wenn Sie also alle Möglichkeiten zum Springen von links nach rechts erfassen können, ist es einfach, den Sprung als ** DP-Übergang ** zu erfassen. Sie können fragen.

Als Sprung auch die zweite ($ max (h \ _ {i + 1},…, h_ {j-1}) \ <min (h \ _ i, h \ _ j) ) und die dritte () Alles was Sie tun müssen, ist herauszufinden, was min (h \ _ {i + 1},…, h_ {j-1}) > max (h \ _ i, h \ _ j) $). Aufgrund dieser Sprungbeschränkung ist die Anzahl der Sprünge wahrscheinlich begrenzt **.

Betrachten Sie den zweiten Sprung. Einfach für $ h \ _i \ leqq h \ _j $, springen Sie von $ i $ zu dem kleinsten $ j $ **, das ** $ j> i $ und $ h \ _j \ geqq h \ _i $ entspricht können. Wenn $ h \ _i \ geqq h \ _j $, können Sie von dem Maximum $ i $ **, das ** $ i <j $ und $ h \ _i \ geqq h \ _j $ erfüllt, zu $ j $ springen. Ich kann es schaffen

Wenn man den dritten Sprung auf die gleiche Weise betrachtet, gibt es die folgenden vier Übergänge. Es gilt auch, wenn $ i <j $ willkürlich ist.

(1) Springe von $ i $ zum kleinsten $ j $, das $ h \ _i \ leqq h \ _j $ erfüllt

(2) Springe vom Maximum $ i $, das $ h \ _i \ geqq h \ _j $ erfüllt, zu $ j $

(3) Springe von $ i $ zum kleinsten $ j $, das $ h \ _i \ geqq h \ _j $ erfüllt

(4) Springe vom Maximum $ i $, das $ h \ _i \ leqq h \ _j $ erfüllt, zu $ j $

Wenn es $ O (N ^ 2) $ ist, kann es leicht erhalten werden, aber es ist schwierig, es sei denn, es handelt sich aufgrund von Einschränkungen um $ O (N \ log {N}) $, sodass ** die Informationen des Übergangsziels (oder der Übergangsquelle) effizient sind. Erwägen Sie, gut zu sparen . Die festgelegte Struktur, in der Elemente in aufsteigender Reihenfolge gespeichert werden können, wird unten verwendet. ( Das Einfügen ungelöster Informationen in Set oder Multiset ** scheint typisch zu sein.)

Zunächst werden im Fall von (1) die Informationen von (Höhe, Index) im Satz gespeichert. Außerdem enthält diese Menge ** Elemente **, deren Übergangsziel beim Betrachten der 0. bis $ i $ th nicht bestimmt wird. Wenn Sie sich hier das $ i + 1 $ -te Element $ h [i + 1] $ für die Elemente ansehen, die kleiner als $ h [i + 1] $ in der Menge sind, ** Übergangsziel Es kann als $ i + 1 $ ** definiert werden. Sie können den Übergang definieren, indem Sie dies für jedes $ i $ tun. Im Fall von (3) kann der Übergang auch einfach durch Umformulieren des Elements, das kleiner als $ h [i + 1] $ ist, mit dem Element, das mehr als $ h [i +] $ ist, bestimmt werden.

Im Fall von (2) werden die Informationen von (Höhe, Index) im Satz gespeichert. Diese Menge enthält ** $ i $ ~ $ n $ -te Elemente **, deren Übergangsquelle nicht festgelegt ist. Wenn Sie sich das $ i-1 $ -te Element $ h [i-1] $ ansehen, für die in der Menge enthaltenen Elemente, die $ h [i-1] $ oder mehr sind, ** die Übergangsquelle Es kann als $ i-1 $ ** definiert werden. Sie können den Übergang definieren, indem Sie dies für jedes $ i $ tun. Im Fall von (4) kann der Übergang auch einfach durch Umformulieren des Elements, das größer oder gleich $ h [i] $ ist, mit dem Element, das größer oder gleich $ h [i] $ ist, bestimmt werden.

Im Fall von (1) und (3) besteht die Möglichkeit, dass sich die Übergangsziele überlappen **, und im Fall von (2) und (4) besteht die Möglichkeit, dass sich die Übergangsquellen überlappen. Seien Sie im letzteren Fall vorsichtig.

Da wir alle Übergänge des zweiten und dritten Musters mit $ O (N \ log {N}) $ aufzählen konnten, sollten wir DP zusammen mit dem Übergang des ersten Musters berücksichtigen.

D.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
//Schleifenvariablen ohne D werden um 1 erhöht, und Schleifenvariablen mit D werden 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 MOD 1000000007 //10^9+7:Gemeinsames Recht
#define INF 1000000000000 //10^12
#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


signed main(){
    //Code zur Beschleunigung der Eingabe
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n;cin>>n;
    vector<ll> h(n);REP(i,n)cin>>h[i];
    vector<ll> move1(n);
    vector<ll> move2(n);
    vector<vector<ll>> move3(n);
    vector<vector<ll>> move4(n);
    //Anders als nur nach rechts zu gehen

    //Erste min
    set<pair<ll,ll>> minm;
    minm.insert(MP(h[0],0));
    FOR(i,1,n-1){
        if(SIZE(minm)==0){
            minm.insert(MP(h[i],i));
            continue;
        }
        //upper_Gebunden und gefährlich nebenan! !!(Ich habe es für den Rest meines Lebens zum Bug gemacht)
        auto x=minm.begin();
        while(x!=minm.end() and *x<=MP(h[i],n)){
            move1[x->S]=i;
            x=minm.erase(x);
        }
        minm.insert(MP(h[i],i));
    }

    //Dann max
    set<pair<ll,ll>> maxm;
    maxm.insert(MP(h[0],0));
    FOR(i,1,n-1){
        if(SIZE(maxm)==0){
            maxm.insert(MP(h[i],i));
            continue;
        }
        auto x=maxm.lower_bound(MP(h[i],0));
        while(x!=maxm.end()){
            move2[x->S]=i;
            x=maxm.erase(x);
        }
        maxm.insert(MP(h[i],i));
    }


    //Von der anderen Seite(Dieses Muster!)

    //Erste min
    set<pair<ll,ll>> mint;
    mint.insert(MP(h[n-1],n-1));
    FORD(i,n-2,0){
        if(SIZE(mint)==0){
            mint.insert(MP(h[i],i));
            continue;
        }
        //upper_Gebunden und gefährlich nebenan! !!(Ich habe es für den Rest meines Lebens zum Bug gemacht)
        auto x=mint.begin();
        while(x!=mint.end() and *x<=MP(h[i],n)){
            move3[i].PB(x->S);
            x=mint.erase(x);
        }
        mint.insert(MP(h[i],i));
    }
    //Dann max
    set<pair<ll,ll>> maxt;
    maxt.insert(MP(h[n-1],n-1));
    FORD(i,n-2,0){
        if(SIZE(maxt)==0){
            maxt.insert(MP(h[i],i));
            continue;
        }
        auto x=maxt.lower_bound(MP(h[i],0));
        while(x!=maxt.end()){
            move4[i].PB(x->S);
            x=maxt.erase(x);
        }
        maxt.insert(MP(h[i],i));
    }

    vector<ll> dp(n,INF);
    dp[0]=0;
    REP(i,n-1){
        dp[i+1]=min(dp[i+1],dp[i]+1);
        dp[move1[i]]=min(dp[move1[i]],dp[i]+1);
        dp[move2[i]]=min(dp[move2[i]],dp[i]+1);
        FORA(j,move3[i])dp[j]=min(dp[j],dp[i]+1);
        FORA(j,move4[i])dp[j]=min(dp[j],dp[i]+1);
    } 
    cout<<dp[n-1]<<endl;
}

Nach dem E-Problem

Ich werde diesmal überspringen

Recommended Posts

Codeforces Round # 654 (Div. 2) Bacha Review (8/18)
Codeforces Round # 594 (Div. 2) Bacha Review (29.10.)
Codeforces Runde # 609 (Div. 2) Bacha Review (10/8)
Codeforces Round # 597 (Div. 2) Bacha Review (27.10.)
Codeforces Runde # 666 (Div. 2) Bacha Review (9/2)
Codeforces Runde # 651 (Div. 2) Bacha Review (8/20)
Codeforces Runde # 659 (Div. 2) Bacha Review (8/5)
Codeforces Runde # 610 (Div. 2) Bacha Review (10/5)
Codeforces Runde # 603 (Div. 2) Bacha Review (10/15)
Codeforces Runde # 600 (Div. 2) Bacha Review (10/21)
Codeforces Runde # 481 (Div. 3) Bacha Review (9/24)
Codeforces Runde # 612 (Div. 2) Bacha Review (10/2)
Codeforces Runde # 521 (Div. 3) Bacha Review (10/9)
Codeforces Runde # 652 (Div. 2) Bacha Review (8/24)
Codeforces Runde # 673 (Div. 2) Bacha Review (10/22)
Codeforces Runde # 613 (Div. 2) Bacha Review (10/1)
Codeforces Runde # 662 (Div. 2) Bacha Review (8/8)
Codeforces Round # 618 (Div. 2) Bacha Review (9/26)
Codeforces Runde # 648 (Div. 2) Bacha Review (9/5)
Codeforces Runde # 676 (Div. 2) Bacha Review (10/31)
Codeforces Round # 675 (Div. 2) Bacha Review (30.10.)
Codeforces Runde # 486 (Div. 3) Bacha Review (9/23)
Codeforces Round # 671 (Div. 2) Bacha Review (9/22)
Codeforces Runde # 669 (Div. 2) Bacha Review (9/9)
Codeforces Runde # 672 (Div. 2) Bacha Review (10/16)
Codeforces Round # 638 (Div. 2) Bacha Review (9/16)
Codeforces Runde # 663 (Div. 2) Bacha Review (8/13)
Codeforces Runde # 668 (Div. 2) Bacha Review (9/7)
Codeforces Runde # 663 (Div. 2) Bacha Review (8/16)
Codeforces Runde # 609 (Div. 2) Bacha Review (10/6)
Codeforces Round # 645 (Div. 2) Bacha Review (9/10)
Codeforces Runde # 664 (Div. 2) Bacha Review (8/13)
Codeforces Round # 660 (Div. 2) Bacha Review (8/4)
Codeforces Round # 643 (Div. 2) Review
Codeforces Round # 679 (Div. 2) Review (10/25)
Codeforces Round # 657 (Div. 2) Review
Educational Codeforces Round 93 Bacha Review (8/17)
Educational Codeforces Round 94 Bacha Review (9/3)
Educational Codeforces Round 91 Bacha Review (7/28)
Bildungs-Codeforces-Runde 88 Bacha Review (8/4)
Educational Codeforces Round 86 Bacha Review (9/17)
Educational Codeforces Round 89 Bacha Review (9/8)
Educational Codeforces Round 92 Bacha Review (30.07.)
Educational Codeforces Round 90 Bacha Review (8/19)
Codeforces Runde # 609 (Div. 2) (bis B)
Bildungs-Codeforces-Runde 87
Codeforces Beta-Runde # 13
Codeforces Beta Runde 1
Codeforces Beta Runde 2
DP100 Frage Bacha Review 1 ~ 10 (8 / 26,27)
Codeforces Round # 626 B. Unterrechtecke zählen