[PYTHON] AtCoder Anfängerwettbewerb 155 Bewertung

Die Ergebnisse dieser Zeit

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

Eindrücke dieser Zeit

(Ich war drei Wochen lang in Skiern getränkt und hatte keine Motivation für Wettkampfprofis, aber ich möchte ab heute (26.02.) Wieder aufnehmen.) Diesmal konnte ich nicht bis C lösen. Als ich die Antwort von Ds angenommener Lösung durch Dichotomie sah, war es als Idee nicht schwierig, also fühlte ich die Wichtigkeit von Hingabe. In Bezug auf E konnten wir keine gute Unterscheidung treffen, je nachdem, ob wir tragen sollten oder nicht. Ich bin sehr enttäuscht. Ich habe das Gefühl, 200 Millionen Mal gesagt zu haben, dass ich organisierter denken möchte.

Problem A

Mit Ausnahme des Falls, in dem a, b und c alle gleich sind und in dem Fall, in dem a, b und c alle unterschiedlich sind.

A.py


a,b,c=map(int,input().split())
if (a==b and b==c) or (a!=b and b!=c and c!=a):
    print("No")
else:
    print("Yes")

B-Problem

Überprüfen Sie nur, ob es sich um eine gerade Zahl handelt, ob es sich um ein Vielfaches von 3 oder ein Vielfaches von 5 handelt. Wenn etwas nicht vorhanden ist, brechen Sie es.

B.py


n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    if a[i]%2==0:
        if a[i]%3==0 or a[i]%5==0:
            continue
        else:
            print("DENIED")
            break
else:
    print("APPROVED")

C-Problem

Ich möchte zählen, wie viele Zeichenfolgen es gibt, also verwalte ich sie in einem Wörterbuch. Wenn Sie nach dem Zählen aller Zeichenfolgen im Wörterbuch das Wörterbuch auflisten, erhalten Sie eine Liste mit dem "Schlüssel / Wert-Paar" des Wörterbuchs als Tipp. Da wir die maximale Anzahl von Zeichenketten ermitteln möchten, können wir nach dem zweiten Element des Taples sortieren. Wenn Sie mehrere Zeichenfolgen ausgeben, werden diese in alphabetischer Reihenfolge ausgegeben. Sortieren Sie sie daher zuerst nach dem ersten Element des Taples. Das Obige ist implementiert und wird wie folgt.

C.py


d=dict()
n=int(input())
for i in range(n):
    s=input()
    if s in d:
        d[s]+=1
    else:
        d[s]=1
d=list(d.items())
d.sort(key=lambda x:x[0])
d.sort(key=lambda x:x[1],reverse=True)
m=len(d)
for i in range(m):
    if d[i][1]==d[0][1]:
        print(d[i][0])
    else:
        break

D Problem

Erstens, da k maximal 10 ^ 10 ist, ist zu sehen, dass ** die Methode der Überprüfung von vorne definitiv nicht rechtzeitig ist **. Hier können Sie ** Dichotomie ** verwenden, da ** die Monotonie und der Zahlenbereich festgelegt sind **.

Wenn wir das Problem unter Berücksichtigung der Dichotomie betrachten, finden wir das Produkt so positiv für das Produkt aus positiven oder negativen Zahlen, negativ für das Produkt aus positiven und negativen Zahlen, mindestens eines Sie können sehen, dass wenn 0 ist, es 0 wird. Daher haben wir jeden Fall separat betrachtet.

Wenn die k-te Zahl negativ ist, können Sie zunächst eine aus der Menge der positiven Zahlen (b3) und der Menge der negativen Zahlen (b1) auswählen. Auch hier ist das Produkt der maximalen Anzahl von Absolutwerten das Minimum und -1 das Maximum, so dass die k-te kleinste Zahl in diesem Intervall durch Dichotomie gesucht wird. Zu diesem Zeitpunkt wird die Funktion countk1 verwendet, um die Anzahl von Zahlen zu zählen, die kleiner als eine bestimmte Anzahl von t sind. Die Funktion countk1 zählt, wie viele Zahlen kleiner oder gleich der negativen Zahl x sind, wenn eine Menge positiver Zahlen und eine Menge negativer Zahlen gegeben sind. Hier werden wir die Elemente der Menge der negativen Zahlen der Reihe nach betrachten und dann eine Dichotomie verwenden, um herauszufinden, wie viele positive Zahlen ein Produkt von x oder weniger haben ($ O (n )). log n) $).

Wenn als nächstes die k-te Zahl 0 wird, wird 0 so berechnet, wie sie ist.

Wenn die k-te Zahl positiv ist, können Sie zwei Zahlen aus einer Reihe positiver Zahlen oder einer Reihe negativer Zahlen auswählen, was etwas komplizierter ist. Erstens kann die minimale Anzahl 1 sein, aber die maximale Anzahl ist das größere der Produkte der beiden Sätze mit den größten absoluten Werten jedes Satzes, und die Anzahl der Elemente in jedem Satz beträgt zwei. Beachten Sie, dass es mehr als eine geben muss. Darunter kann die k-te Zahl (der Fall, in dem sie negativ wird und der Fall, in dem sie 0 wird, kann im Voraus subtrahiert werden) durch eine dichotome Suche auf die gleiche Weise gesucht werden, wie wenn die k-te Zahl negativ ist. Hier funktioniert die countk1-Funktion Verwenden Sie die Funktion countk2, um sie zu finden. Wie bei der countk1-Funktion kann eine festgelegt und eine Dichotomie durchgeführt werden, es muss jedoch eine Dichotomie für jeden der negativen und positiven Sätze innerhalb desselben Satzes durchgeführt werden. Es ist zu beachten, dass der Index, der nach der Dichotomie durchsucht werden soll, i + 1 anstelle von 0 sein muss, um zwei Zahlen ohne Duplizierung auszuwählen.

Wenn Sie die obigen Fälle teilen und den Dichotomiecode sorgfältig schreiben, lautet der Code wie folgt. (Es war schwierig zu implementieren ... Ich habe das Gefühl, eine vollwertige Person zu werden, wenn ich so viel Code schnell schreiben kann ...)

answerD.cc


#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<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
#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() //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 INF 1000000000000
#define MOD 10000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

ll l1,l2,l3;

ll countk1(ll x,vector<ll> b11,vector<ll> b13){
    ll ret=0;
    REP(i,l1){
        #Teil der Bisektionssuche(Erfüllt es x oder weniger?)
        ll lx=0;ll rx=l3-1;
        while(lx+1<rx){
            ll t=(lx+rx)/2;
            if(b13[t]*b11[i]<=x){lx=t;}else{rx=t;}
        }
        #Sei vorsichtig, wie du hier schreibst
        if(b13[rx]*b11[i]<=x){
            ret+=(rx+1);
        }else if(b13[lx]*b11[i]<=x){
            ret+=(lx+1);
        }
    }
    return ret;
}

ll countk2(ll x,vector<ll> b21,vector<ll> b23){
    ll ret=0;
    REP(i,l1-1){
        #Der Beginn der Dichotomie ist i anstelle von 0+1(Keine Vervielfältigung zulassen)
        ll lx=i+1;ll rx=l1-1;
        while(lx+1<rx){
            ll t=(lx+rx)/2;
            if(b21[t]*b21[i]<=x){lx=t;}else{rx=t;}
        }
        if(b21[rx]*b21[i]<=x){
            ret+=(rx-i);
        }else if(b21[lx]*b21[i]<=x){
            ret+=(lx-i);
        }
    }
    REP(i,l3-1){
        #Der Beginn der Dichotomie ist i anstelle von 0+1(Keine Vervielfältigung zulassen)
        ll lx=i+1;ll rx=l3-1;
        while(lx+1<rx){
            ll t=(lx+rx)/2;
            if(b23[t]*b23[i]<=x){lx=t;}else{rx=t;}
        }
        if(b23[rx]*b23[i]<=x){
            ret+=(rx-i);
        }else if(b23[lx]*b23[i]<=x){
            ret+=(lx-i);
        }
    }
    return ret;
}

signed main(){
    ll n,k;cin >> n >> k;
    vector<ll> b1,b2,b3;
    REP(i,n){
        ll x;cin >> x;
        if(x<0){b1.PB(x);}else if(x==0){b2.PB(x);}else{b3.PB(x);}
    }
    l1=b1.size();l2=b2.size();l3=b3.size();
    sort(ALL(b1));sort(ALL(b3),greater<ll>());
    if(k<=l1*l3){
        ll l=b1[0]*b3[0];ll r=-1;
        while(l+1<r){
            ll t=(l+r)/2;
            if(countk1(t,b1,b3)>=k){r=t;}else{l=t;}
        }
        if(countk1(l,b1,b3)==k){
            cout << l << endl;
        }else{
            cout << r << endl;
        }
    }else if(k<=l1*l3+l2*(l1+l3)+(l2*(l2-1))/2){
        cout << 0 << endl;
    }else{
        k-=(l1*l3+l2*(l1+l3)+(l2*(l2-1))/2);
        ll l=1;ll r;
        if(l1>=2 and l3<2){
            r=b1[0]*b1[1];
        }else if(l1<2 and l3>=2){
            r=b3[0]*b3[1];
        }else{
            r=max(b1[0]*b1[1],b3[0]*b3[1]);
        }
        sort(ALL(b3));sort(ALL(b1),greater<ll>());

        while(l+1<r){
            ll t=(l+r)/2;
            if(countk2(t,b1,b3)>=k){r=t;}else{l=t;}
        }
        
        if(countk2(l,b1,b3)==k){
            cout << l << endl;
        }else{
            cout << r << endl;
        }
    }
}

E Problem

Nach ein paar Experimenten ist leicht zu erkennen, dass ich mich aufgrund des Einflusses anderer Ziffern ** nicht für Gier entscheiden kann ** (ich bin gierig, sobald ich den Wettbewerbsprofi verlasse. Es ist nicht gut.) Ich werde. Experimente zeigen auch, dass es 2 $ Möglichkeiten gibt, mehr zu zahlen oder nur, wenn man auf eine bestimmte Ziffer achtet. (Es ist leicht zu verstehen, wenn Sie an n = 1 ~ 9 denken.) Mit anderen Worten, wenn Sie für jede Ziffer 1 mehr bezahlen (um mehr für die untere Ziffer zu zahlen) und wenn Sie nur ** $ 2 $ bezahlen Wenn Sie ein Array für DP vorbereiten, das den Status ** enthält, können Sie es finden, indem Sie die Reihenfolge anhand der oberen Ziffer festlegen. DP funktioniert in der Regel gut mit dieser Verallgemeinerung, daher möchte ich mein Bestes geben, um während des Wettbewerbs ** ohne Eile ** denken zu können.

answerE.py


n=[int(x) for x in list(input())]
k=len(n)
dp=[[-1,-1] for _ in range(k)]
dp[0]=[min(1+(10-n[0]),n[0]),min(1+(10-n[0]-1),n[0]+1)]
for i in range(1,k):
    dp[i]=[min(dp[i-1][1]+(10-n[i]),dp[i-1][0]+n[i]),min(dp[i-1][1]+(10-n[i]-1),dp[i-1][0]+n[i]+1)]
print(dp[k-1][0])

F Problem

Ich denke, es ist noch nicht für das Level geeignet, also werde ich es dieses Mal überspringen.

Recommended Posts

AtCoder Anfängerwettbewerb 152 Rückblick
AtCoder Beginner Contest 160 Bewertung
AtCoder Anfängerwettbewerb 178 Bewertung
AtCoder Anfängerwettbewerb 166 Bewertung
AtCoder Anfängerwettbewerb 167 Bewertung
AtCoder Beginner Contest 164 Bewertung
AtCoder Beginner Contest 169 Bewertung
AtCoder Beginner Contest 171 Bewertung
AtCoder Beginner Contest 182 Bewertung
AtCoder Beginner Contest 180 Bewertung
AtCoder Anfängerwettbewerb 177 Rückblick
AtCoder Anfängerwettbewerb 168 Bewertung
AtCoder Beginner Contest 179 Bewertung
AtCoder Beginner Contest 172 Bewertung
AtCoder Anfängerwettbewerb 176 Bewertung
AtCoder Anfängerwettbewerb 175 Bewertung
AtCoder Anfängerwettbewerb 174 Bewertung
AtCoder Beginner Contest 153 Bewertung
AtCoder Anfängerwettbewerb 156 Bewertung
AtCoder Beginner Contest 161 Bewertung
AtCoder Beginner Contest 170 Bewertung
AtCoder Beginner Contest 165 Bewertung
AtCoder Beginner Contest 173 Bewertung
AtCoder Anfängerwettbewerb 155 Bewertung
AtCoder Beginner Contest 162 Bewertung
AtCoder Anfängerwettbewerb 177
AtCoder Anfängerwettbewerb 172
AtCoder Anfängerwettbewerb 173
AtCoder Beginner Contest 066 Überprüfen Sie frühere Fragen
AtCoder Anfängerwettbewerb 181 Hinweis
AtCoder Regular Contest 105 Bewertung
AtCoder Anfängerwettbewerb 180 Hinweis
AtCoder Anfängerwettbewerb 182 Hinweis
AtCoder Grand Contest 048 Bewertung
AtCoder Anfängerwettbewerb 156 WriteUp
AtCoder Grand Contest 045 Bewertung
AtCoder Grand Contest 044 Bewertung
AtCoder Beginner Contest 167 Memorandum
AtCoder Anfängerwettbewerb 183 Hinweis
AtCoder Regular Contest 106 Bewertung
AtCoder Anfängerwettbewerb 184 Hinweis
AtCoder Grand Contest 046 Bewertung
AtCoder Beginner Contest 102 Rückblick auf frühere Fragen
AtCoder Beginner Contest 072 Rückblick auf frühere Fragen
AtCoder Beginner Contest 085 Rückblick auf frühere Fragen
AtCoder Beginner Contest 062 Rückblick auf frühere Fragen
AtCoder Beginner Contest 113 Rückblick auf frühere Fragen
AtCoder Beginner Contest 074 Rückblick auf frühere Fragen
AtCoder Beginner Contest 051 Rückblick auf frühere Fragen
AtCoder Beginner Contest 127 Rückblick auf frühere Fragen
AtCoder Beginner Contest 119 Rückblick auf frühere Fragen
AtCoder Beginner Contest 151 Rückblick auf frühere Fragen
AtCoder Beginner Contest 075 Rückblick auf frühere Fragen
AtCoder Beginner Contest 054 Rückblick auf frühere Fragen
AtCoder Beginner Contest 110 Rückblick auf frühere Fragen
AtCoder Beginner Contest 117 Rückblick auf frühere Fragen
AtCoder Beginner Contest 070 Rückblick auf frühere Fragen
AtCoder Beginner Contest 105 Rückblick auf frühere Fragen