[PYTHON] AtCoder Beginner Contest 056 Rückblick auf frühere Fragen
Benötigte Zeit
Impressionen
Die erste gelbe Frage wurde innerhalb der Zeit erledigt! !! Es ist einfach und es geht um Blau, aber ich bin glücklich! Ich möchte härter arbeiten und das Problem stabil lösen können, bis es gelb ist.
Problem A
Ich habe die Eingabe nicht aufgeteilt, weil sie problematisch war.
answerA.py
s=input()
print("H" if s=="H H" or s=="D D" else "D")
B-Problem
Überlegen Sie, welcher Abschnitt sich auf der rechten Seite befindet (in der zweidimensionalen Ebene).
answerB.py
w,a,b=map(int,input().split())
if a<=b<=a+w or a<=b+w<=a+w:
print(0)
elif b>a+w:
print(b-a-w)
else:
print(a-b-w)
C-Problem
** Ich konnte es ohne Beweis bestehen. ** Ich denke, es ist ein Beweis dafür, dass die Macht zunimmt. Zunächst möchten wir so schnell wie möglich erreichen. Berücksichtigen Sie daher die maximal erreichbaren Koordinaten zum Zeitpunkt $ t $. Dann können Sie leicht sehen, dass es $ 1 + 2 +… + t = t \ times (t + 1) \ div 2 $ wird. Außerdem können Sie zum Zeitpunkt $ t-1 $ $ (t-1) \ mal t \ div 2 $ erreichen, also zum Zeitpunkt $ t $ $ (t-1) \ mal t \ div 2 + 1 $ Wenn Sie zeigen können, dass Sie alle Koordinaten von ~ $ t \ times (t + 1) \ div 2 $ (✳︎) erreichen können, berechnen Sie $ t \ times (t + 1) \ div 2 $ in der Reihenfolge ab Zeitpunkt 1. Sie können sehen, dass die Zeit, die benötigt wird, um ein bestimmtes x zu überschreiten, der zu berechnende Mindestwert ist. Wenn Sie hier die Aktion auswählen, zu keinem Zeitpunkt k etwas zu tun, erreichen Sie die Koordinaten von $ t \ times (t + 1) \ div 2-k $ und indem Sie k = t-1 → 1 bewegen. Da $ (t-1) \ mal t \ div 2 +1 $ → $ t \ mal (t + 1) \ div 2-1 $ alle dargestellt werden können, wird (✳︎) angezeigt.
answerC.py
x=int(input())
for i in range(1,10**5):
if x<=(i*(i+1))//2:
print(i)
break
D Problem
Wie erwartet war das gelbe Problem schwierig, aber ich konnte eine vollständige Antwort erhalten.
Als ich mit der Stichprobe experimentierte, bemerkte ich zunächst, dass die Anzahl der Karten kleiner als ** unnötig zu sein scheint **, also habe ich sie vorerst sortiert und das i-te Element ist unnötig. Ich fragte mich, ob es einen gab.
Achten Sie auch auf den Fall, dass Karte i nicht unnötig ist, ** wenn Karte i ein guter Satz wird, wenn sie zu einem schlechten Satz hinzugefügt wird ** (wenn es überhaupt eine Möglichkeit gibt, einen solchen schlechten Satz auszuwählen), Mir wurde auch klar, dass es nicht unnötig war. (← Diese Paraphrase scheint die schwierigste zu sein ... Ich habe jedoch das Gefühl, dass ich oft die Idee verwende, dass das Gegenteil von ** hinzugefügt wird **.)
Hier habe ich versucht, ein Muster zu finden, das ein guter Satz wäre, wenn ich Karte i zu einem schlechten Satz hinzufügte, aber es hat nicht funktioniert. Warum nicht hier die Richtlinie wechseln und über alle Zahlenmuster nachdenken, die mit Ausnahme von Karte i durch Karten dargestellt werden können? Ich dachte. Dann können Sie DP verwenden. Mit anderen Worten, wenn Sie das Gesamtmuster der von DP auf die Karte geschriebenen Zahlen aufzeichnen und die auf die Karte i geschriebenen Zahlen hinzufügen können, um eine Zahl zu erstellen, die k überschreitet, ist diese Karte i nicht erforderlich. Es kann beurteilt werden, dass es keine ** gibt. Wenn umgekehrt die Summe der auf die Karte geschriebenen Zahlen kleiner als k ist, aber der Maximalwert (beachten Sie, dass ** 0 enthalten ist **) und die Summe der auf die Karte geschriebenen Zahlen i k nicht überschreitet, die Karte Ich werde nicht mehr gebraucht.
Wenn Sie ein Muster finden möchten, das zu einem guten Satz wird, wenn Sie Karte i zu einem schlechten Satz hinzufügen, ist dies der Berechnungsbetrag von O ($ nk
answerD_TLE.py
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
a.sort()
def check(d):#Brauchst du es
global a,n,k
dp=[0]*(k)#k-Bis zu 1
if a[d]>=k:
return True
for i in range(n):
if i!=d:
dp_sub=[0]*(k)
for j in range(k-1):
if j==0 or dp[j]!=0:
if j+a[i]<k:
dp_sub[j+a[i]]=1
else:
break
for j in range(k):
if dp_sub[j]==1:
dp[j]=1
if j+a[d]>=k:
return True
return False
l,r=0,n-1
while l+1<r:
d=(l+r)//2
if check(d):#Ist es nötig
r=d
else:
l=d
if check(l):
print(l)
else:
if check(r):
print(r)
else:
print(r+1)
answerD.cc
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
ll n,k;
vector<ll> a;
bool check(ll d){
vector<ll> dp(k,0);
if(a[d]>=k) return true;
for(ll i=0;i<n;i++){
if(i!=d){
vector<ll> dp_sub(k,0);
for(ll j=0;j<k-1;j++){
if(j==0 or dp[j]!=0){
if(j+a[i]<k){
dp_sub[j+a[i]]=1;
}else{
break;
}
}
}
for(ll j=0;j<k;j++){
if(dp_sub[j]==1){
dp[j]=1;
if(j+a[d]>=k) return true;
}
}
}
}
return false;
}
signed main(){
cin >> n >> k;
a.resize(n);
for(ll i=0;i<n;i++){cin >> a[i];}
sort(a.begin(),a.end());
ll l=0;ll r=n-1;
while(l+1<r){
ll d=floor(l+r)/2;
if(check(d)){
r=d;
}else{
l=d;
}
}
if(check(l)){
cout << l << endl;
}else if(check(r)){
cout << r << endl;
}else{
cout << r+1 << endl;
}
}
Recommended Posts