AtCoder Beginner Contest 056 Revue des questions précédentes

Temps requis

スクリーンショット 2020-01-30 16.32.01.png

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 ), mais si vous vérifiez dans l'ordre si la carte i est inutile, O ( n ^) Il sera de 2k ) et ne se terminera pas dans le délai imparti. Cependant, si vous profitez de la monotonie selon laquelle "lorsque la carte i n'est pas nécessaire, la carte j (j <= i) avec un nombre plus petit est également inutile", la dichotomie peut être utilisée, et O ( nk ) Puisque $ nk \ log {n} $ représente environ 10 $ ^ 8 $ dans le montant du calcul de log {n} $), vous pouvez écrire un programme juste à temps. De plus, l'estimation du montant du calcul était lâche (je pensais que c'était environ 10 $ ^ 7 ), et je l'ai publiée en Python et j'ai émis TLE. Aussi, il semble que le montant total du calcul puisse être réduit à O ( nk $), et je pense que ce sera à temps s'il est réduit à ce niveau même en Python. A part ça, j'ai oublié que ** le tableau n'est pas trié même s'il s'agit d'une dichotomie **, ** l'élément est toujours requis si le nombre écrit sur la carte est k ou plus **, et ainsi de suite. Soyez prudent car vous ne pouvez rien faire si cet ** algorithme de base est erroné **.

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

AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 072 Revue des questions précédentes
AtCoder Beginner Contest 085 Revue des questions précédentes
AtCoder Beginner Contest 062 Revue des questions précédentes
AtCoder Beginner Contest 113 Revue des questions précédentes
AtCoder Beginner Contest 074 Revue des questions précédentes
AtCoder Beginner Contest 051 Revue des questions précédentes
AtCoder Beginner Contest 127 Revue des questions précédentes
AtCoder Beginner Contest 119 Revue des questions précédentes
AtCoder Beginner Contest 151 Revue des questions précédentes
AtCoder Beginner Contest 075 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 110 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 070 Revue des questions précédentes
AtCoder Beginner Contest 112 Revue des questions précédentes
AtCoder Beginner Contest 076 Revue des questions précédentes
AtCoder Beginner Contest 089 Revue des questions précédentes
AtCoder Beginner Contest 069 Revue des questions précédentes
AtCoder Beginner Contest 079 Revue des questions précédentes
AtCoder Beginner Contest 056 Revue des questions précédentes
AtCoder Beginner Contest 087 Revue des questions précédentes
AtCoder Beginner Contest 067 Revue des questions précédentes
AtCoder Beginner Contest 093 Revue des questions précédentes
AtCoder Beginner Contest 046 Revue des questions précédentes
AtCoder Beginner Contest 123 Revue des questions précédentes
AtCoder Beginner Contest 049 Revue des questions précédentes
AtCoder Beginner Contest 078 Revue des questions précédentes
AtCoder Beginner Contest 081 Revue des questions précédentes
AtCoder Beginner Contest 047 Revue des questions précédentes
AtCoder Beginner Contest 060 Revue des questions précédentes
AtCoder Beginner Contest 104 Revue des questions précédentes
AtCoder Beginner Contest 057 Revue des questions précédentes
AtCoder Beginner Contest 121 Revue des questions précédentes
AtCoder Beginner Contest 126 Revue des questions précédentes
AtCoder Beginner Contest 090 Revue des questions précédentes
AtCoder Beginner Contest 103 Revue des questions précédentes
AtCoder Beginner Contest 061 Revue des questions précédentes
AtCoder Beginner Contest 059 Revue des questions précédentes
AtCoder Beginner Contest 044 Revue des questions précédentes
AtCoder Beginner Contest 083 Revue des questions précédentes
AtCoder Beginner Contest 048 Revue des questions précédentes
AtCoder Beginner Contest 124 Revue des questions précédentes
AtCoder Beginner Contest 116 Revue des questions précédentes
AtCoder Beginner Contest 097 Revue des questions précédentes
AtCoder Beginner Contest 088 Revue des questions précédentes
AtCoder Beginner Contest 092 Revue des questions précédentes
AtCoder Beginner Contest 099 Revue des questions précédentes
AtCoder Beginner Contest 065 Revue des questions précédentes
AtCoder Beginner Contest 053 Revue des questions précédentes
AtCoder Beginner Contest 094 Revue des questions précédentes
AtCoder Beginner Contest 063 Revue des questions précédentes
AtCoder Beginner Contest 107 Revue des questions précédentes
AtCoder Beginner Contest 071 Revue des questions précédentes
AtCoder Beginner Contest 064 Revue des questions précédentes
AtCoder Beginner Contest 082 Revue des questions précédentes
AtCoder Beginner Contest 084 Revue des questions précédentes
AtCoder Beginner Contest 068 Revue des questions précédentes
AtCoder Beginner Contest 058 Revue des questions précédentes
AtCoder Beginner Contest 043 Revue des questions précédentes
AtCoder Beginner Contest 098 Revue des questions précédentes