AtCoder Beginner Contest 056 Revue des questions précédentes
Temps requis
Impressions
La première question jaune terminée dans le temps! !! C'est facile et il s'agit de bleu, mais je suis content! Je veux travailler plus dur et pouvoir résoudre le problème de manière stable jusqu'à ce qu'il devienne jaune.
Problème A
Je n'ai pas divisé l'entrée car c'était gênant.
answerA.py
s=input()
print("H" if s=="H H" or s=="D D" else "D")
Problème B
Considérez quelle section est sur le côté droit (sur le plan bidimensionnel).
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)
Problème C
** J'ai pu le passer sans preuve. ** Je pense que c'est la preuve que la puissance augmente. Tout d'abord, nous voulons atteindre le plus tôt possible, alors considérez les coordonnées maximales accessibles au temps $ t $. Alors vous pouvez facilement voir qu'il devient $ 1 + 2 +… + t = t \ times (t + 1) \ div 2 $. De plus, au temps $ t-1 $, vous pouvez atteindre $ (t-1) \ times t \ div 2 $, donc au temps $ t $ $ (t-1) \ times t \ div 2 + 1 $ Si vous pouvez montrer que vous pouvez atteindre toutes les coordonnées de ~ $ t \ times (t + 1) \ div 2 $ (✳︎), calculez $ t \ times (t + 1) \ div 2 $ dans l'ordre à partir du temps 1. Vous pouvez voir que le temps qu'il faut pour dépasser un x donné est la valeur minimale à calculer. Ici, si vous sélectionnez l'action de ne rien faire à tout instant k, vous atteindrez les coordonnées de $ t \ times (t + 1) \ div 2-k $, et en déplaçant k = t-1 → 1. $ (T-1) \ times t \ div 2 +1 $ → $ t \ times (t + 1) \ div 2-1 $ peuvent être représentés, donc (✳︎) est affiché.
answerC.py
x=int(input())
for i in range(1,10**5):
if x<=(i*(i+1))//2:
print(i)
break
Problème D
Comme prévu, le problème jaune était difficile, mais j'ai réussi à obtenir une réponse complète.
Tout d'abord, lorsque j'ai expérimenté avec l'échantillon, j'ai remarqué que le nombre de cartes inférieur à ** semble être inutile **, je l'ai donc trié pour le moment et le i-ème élément n'est pas nécessaire. Je me suis demandé s'il y en avait un.
Aussi, en faisant attention au cas où la carte i n'est pas inutile, ** si la carte i devient un bon ensemble lorsqu'elle est ajoutée à un mauvais ensemble ** (s'il y a même une façon de sélectionner un si mauvais ensemble), J'ai également réalisé que ce n'était pas inutile. (← Cette paraphrase semble être la plus difficile ... Cependant, je sens que j'utilise souvent l'idée que le contraire de ** est ajouté **.)
Ici, j'ai essayé de trouver un modèle qui serait un bon ensemble lorsque j'ai ajouté la carte i à un mauvais ensemble, mais cela n'a pas fonctionné. Pourquoi ne pas changer de politique ici et penser à tous les modèles de nombres qui peuvent être représentés par des cartes à l'exception de la carte i? J'ai pensé. Ensuite, vous pouvez utiliser DP. En d'autres termes, si vous pouvez enregistrer le motif total des nombres écrits sur la carte par DP et ajouter les nombres écrits sur la carte i pour créer un nombre qui dépasse k, cette carte i est inutile. On peut juger qu'il n'y a pas de **. A l'inverse, si la somme des nombres inscrits sur la carte est inférieure à k mais la valeur maximale (notez que ** 0 est inclus **) et la somme des nombres écrits sur la carte i ne sont pas supérieure ou égale à k, la je ne suis plus nécessaire.
À partir de ce qui précède, si vous voulez trouver un motif qui devient un bon ensemble lorsque vous ajoutez la carte i à un mauvais ensemble, ce sera le montant du calcul de O ($ nk
answerD_TLE.py
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
a.sort()
def check(d):#En as-tu besoin
global a,n,k
dp=[0]*(k)#k-Jusqu'à 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):#Est-ce nécessaire
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