[PYTHON] AtCoder Anfängerwettbewerb 155 Bewertung
Die Ergebnisse dieser Zeit
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