Critique du concours de programmation Tokio Marine & Nichido 2020

Les résultats de cette fois

スクリーンショット 2020-06-18 21.23.33.png

La représentation était vers 1270.

Impressions de cette époque

L'ABC du lendemain était trop mauvais et j'ai tout pris, mais je pensais que je pourrais me battre un peu plus cette fois aussi. Cependant, en conséquence, j'ai pu résoudre les problèmes de diff jaune et orange dans la revue, donc je pense que c'était bien. Une difficulté élevée peut être obtenue si vous prenez le temps calmement (environ 3 heures), je voudrais donc faire un effort pour augmenter progressivement cette vitesse. La performance n'est pas bonne, mais c'était un moment où je sentais que je pouvais me battre. Ces temps ont duré ces derniers temps pour que je puisse finir de résoudre pendant le concours

Problème A

Produit trois caractères par l'avant.

A.py


s=input()
print(s[:3])

Problème B

J'ai continué à bugger ce problème et les performances ont chuté d'environ 200. C'est trop de gaspillage. Pensez à la vitesse relative entre A chassant et B s'enfuyant. Je me déteste à cause de ça. Je veux garder mon esprit normal même pendant le concours.

B.py


a,v=map(int,input().split())
b,w=map(int,input().split())
t=int(input())
if a<b and v<=w:
    print("NO")
elif a>b and v<=w:
    print("NO")
elif a<b:
    if -((a-b)//(v-w))<=t:
        print("YES")
    else:
        print("NO")
else:
    if -((-a+b)//(v-w))<=t:
        print("YES")
    else:
        print("NO")

Problème C

J'ai essayé d'utiliser un arbre de segment retardé (que je n'ai jamais implémenté) simplement parce que je l'ai vu comme une mise à jour de section. ** Le problème ne peut pas être résolu en s'appuyant sur des structures de données et des algorithmes **. Ce n'est pas du tout bon.

Comme vous pouvez le voir en lisant l'énoncé du problème, chaque opération ** élargit la section que l'ampoule peut éclairer **. De plus, l'intensité lumineuse d'une ampoule est le nombre d'ampoules qui éclairent l'ampoule pendant son fonctionnement. Maintenant, étant donné la puissance de l'ampoule $ B_1, B_2,…, B_N $ pour chaque opération, l'ampoule $ i $ ème illumine l'ampoule $ i-B_i $ à $ i + B_i $ ème. En d'autres termes, si vous répétez la vérification des ampoules que chaque ampoule allume (préparez un tableau de longueur N avec $ 0 $ comme valeur initiale et faites toutes les ampoules dans la section éclairée $ + 1 $), vous pouvez le faire une fois. L'opération peut être effectuée avec $ O (N ^ 2) $. En outre, ** il est inefficace d'ajouter $ + 1 $ à toutes les sections éclairées, et vous pouvez réduire le montant du calcul à $ O (N) $ en utilisant la méthode imos **.

À première vue, le montant du calcul semble être $ O (NK) $, mais quand j'ai expérimenté, j'ai remarqué qu'il pouvait être complété en environ $ \ log {N} $ fois au lieu de $ K $ fois. En tant qu'image, le facteur décisif était que ** l'intensité lumineuse minimale doublait ** comme le montre la figure ci-dessous. ** Même si vous n'êtes pas sûr de vos pensées, vous pouvez facilement vérifier si ce sera TLE si vous faites le cas maximum et le vérifiez **.

De ce qui précède, puisqu'il s'agit de $ O (N \ log {N}) $, vous pouvez écrire un programme dans le délai imparti.

C.py


from itertools import accumulate
n,k=map(int,input().split())
a=list(map(int,input().split()))
for _ in range(k):
    b=[0]*n
    for i in range(n):
        b[max(0,i-a[i])]+=1
        if i+a[i]+1<n:
            b[i+a[i]+1]-=1
    a=list(accumulate(b))
    if a==[n]*n:
        break
print(" ".join(map(str,a)))

Problème D

Tout d'abord, le problème ne fait aucun doute qu'il serait préférable de formuler une politique basée sur le ** problème du sac à dos avec un nombre limité **.

Sous cette prémisse, les éléments peuvent être sélectionnés parmi les ancêtres d'un certain sommet et ceux du sommet lui-même, donc si vous sélectionnez les éléments dans l'ordre de la racine au sommet de l'enfant (** de haut en bas **), c'est normal. Vous pouvez y penser comme un problème de sac à dos. Dans ce cas, ** vous pouvez éviter le calcul dans la requête **, donc ce sera $ O (NW_ {max}) $ dans le pré-calcul par DP et $ O (Q) $ dans le calcul de la requête, mais $ NW_ { Étant donné que max} $ peut atteindre 2 $ ^ {18} \ fois 10 ^ 5 $, cette règle ne peut pas effectuer le calcul à temps. (1)

Par contre, considérant que le calcul est effectué dans la requête, il suffit de sélectionner les éléments dans l'ordre du sommet donné au sommet parent (** de bas en haut **), donc considérons un problème de sac à dos similaire au précédent. Par exemple, ce sera $ O (Q W_ {max}) $ dans le calcul de la requête par DP. Cependant, $ Q W_ {max} $ peut être jusqu'à 10 $ ^ 5 \ fois 10 ^ 5 $, donc même cette politique ne peut pas effectuer le calcul à temps. (2)

Cependant, comme (1) et (2) valent environ 10 $ ^ {10} $, on considère que la politique de base n'est pas erronée, et ** effectue bien le pré-calcul et effectue le calcul de la requête efficacement **. pense.

Premièrement, dans le calcul avant (1), il ne suffit pas d'exécuter DP à tous les sommets $ N $, donc supposons que DP est effectué à $ K $ sommets. À ce stade, le montant de DP calculé est $ O (KW_ {max} \ log {N}) $ et $ W_ {max} $ est de 10 $ ^ 5 $ au maximum, donc $ K $ est d'environ 10 $ ^ 3 $ au maximum. Si tel est le cas, le pré-calcul peut être effectué dans le délai imparti.

Ici, dans le calcul de la requête, les éléments sont sélectionnés dans l'ordre du sommet donné au sommet parent, de sorte que vous pouvez voir que l'élément avec le sommet le plus proche de la racine est plus susceptible d'être sélectionné à plusieurs reprises . Par conséquent, si vous sélectionnez ** $ K $ sommets parmi les sommets proches de la racine, la requête peut être calculée plus rapidement ** ( Les parties communes peuvent être rendues plus efficaces en calculant à l'avance !! * *). De plus, puisqu'il s'agit de $ K \ simeq2 ^ {10} -1 $, on peut supposer que le pré-calcul par DP a été complété jusqu'au pic avec une profondeur de 9 $ $. De plus, comme la profondeur maximale des sommets est de 17 $ à partir de $ N <2 ^ {18} $, nous pouvons voir que nous n'avons besoin de calculer que pour les éléments sur les profondeurs maximales de 8 $ de 10 $ à 17 $. ..

Par conséquent, envisagez de maximiser la valeur lorsque vous choisissez parmi les éléments en haut de $ L $ avec $ L = 8 $. Ici, si DP est utilisé, le traitement de la requête sera $ O (QLW_ {max}) $ et ce ne sera pas à temps, mais ** Si vous énumérez tout, ce sera $ O (Q2 ^ L) $, donc ** $ Q2 ^ L \ simeq10 ^ 7 À partir de $, vous pouvez également traiter la requête à temps. (N'oubliez pas que la base du ** problème du sac à dos est une énumération complète ** !!)

De plus, il semble que le problème que ** énumérer tout ne soit pas dans le temps, mais n'énumérer que la moitié et résumer plus tard est dans le temps est appelé demi-énumération **. Ensuite, je veux pouvoir résoudre des problèmes similaires. Si vous savez cela, l'idée est que ** la méthode d'énumération de tout dans une requête est $ O (QN) $, et le montant du calcul peut être réduit à $ O (Q \ sqrt {N}) $ dans une énumération à moitié complète **. Je pense que je pourrais le faire.

De plus, comme l'accès au tableau créé par DP après en avoir énuméré la moitié dans la requête doit être $ O (1) $, le tableau créé par DP doit être ** le plus grand élément avec un poids de W ou moins. Il est également important de noter que la valeur ** doit être stockée et que la valeur maximale cumulée doit être calculée après avoir calculé la valeur de l'article maximum avec un poids W en DP normal.

Ce qui précède est implémenté et devient comme suit, mais l'implémentation est médiocre et elle ne peut pas être passée avec Python et PyPy, mais elle peut être passée avec C ++. J'espère que la mise en œuvre ira de mieux en mieux.

D.cc


//Comprendre(Ordre alphabétique)
#include<algorithm>//sort,Recherche de bisection,Tel
#include<bitset>//Jeu de bits de longueur fixe
#include<cmath>//pow,journal etc.
#include<complex>//Nombre complexe
#include<deque>//File d'attente d'accès double
#include<functional>//trier plus
#include<iomanip>//setprecision(Erreur de sortie en virgule flottante)
#include<iostream>//Entrée sortie
#include<iterator>//Régler l'opération(Ensemble de produits,Ensemble de somme,Ensemble de différences, etc.)
#include<map>//map(dictionnaire)
#include<numeric>//iota(Génération d'une chaîne entière),pgcd et lcm(c++17)
#include<queue>//queue
#include<set>//ensemble
#include<stack>//empiler
#include<string>//Chaîne
#include<unordered_map>//Carte avec itérateur mais sans ordre
#include<unordered_set>//Il y a un itérateur mais l'ordre n'est pas maintenu défini
#include<utility>//pair
#include<vector>//Tableau de longueur variable

using namespace std;
typedef long long ll;

//macro
//pour la relation de boucle
//L'argument est(Variables dans la boucle,Amplitude de mouvement)Ou(Variables dans la boucle,Premier numéro,Nombre d'extrémités)、のどちらOu
//Les variables de boucle sans D sont incrémentées de 1 et les variables de boucle avec D sont décrémentées de 1.
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
//#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//x est un conteneur tel que vector
#define ALL(x) (x).begin(),(x).end() //Je souhaite omettre des arguments tels que le tri
#define SIZE(x) ((ll)(x).size()) //taille à la taille_Changement de t à ll
#define MAX(x) *max_element(ALL(x)) //Trouvez la valeur maximale
#define MIN(x) *min_element(ALL(x)) //Trouvez la valeur minimale
//constant
#define INF 1000000000000 //10^12:Valeur extrêmement élevée,∞
#define MOD 1000000007 //10^9+7:Droit commun
#define MAXR 100000 //10^5:Portée maximale de la baie(Utilisé pour l'énumération des nombres premiers, etc.)
//Abréviation
#define PB push_back //Insérer dans le vecteur
#define MP make_pair //constructeur de paires
#define F first //Le premier élément de paire
#define S second //Le deuxième élément de paire

ll n;vector<pair<ll,ll>> vw;vector<vector<ll>> dp;
ll c1,c2;

void dfs(ll i){
    if(i==1){
        dp[i-1][vw[i-1].S]=vw[i-1].F;
    }else{
        ll j=i/2;
        FORD(k,c2,0){
            if(dp[j-1][k]!=0 or k==0){
                ll ne=k+vw[i-1].S;
                if(ne<=c2)dp[i-1][ne]=max(dp[j-1][k]+vw[i-1].F,dp[i-1][ne]);
            }
            dp[i-1][k]=dp[j-1][k];
        }
    }
    if(i*2<=c1 and i*2<=n)dfs(i*2);
    if(i*2+1<=c1 and i*2+1<=n)dfs(i*2+1);
}

signed main(){
    //Code pour accélérer la saisie
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    cin>>n;
    vw.resize(n);
    REP(i,n)cin>>vw[i].F>>vw[i].S;
    c1=1<<10;c2=100000;
    dp.resize(c1);REP(i,c1)dp[i].resize(c2+1);
    dfs(1);//cout << 1 << endl;
    REP(i,c1)REP(j,c2)dp[i][j+1]=max(dp[i][j],dp[i][j+1]);
    ll q;cin>>q;
    REP(i,q){
        ll v,l;cin>>v>>l;
        vector<ll> cand;
        while(v>c1){
            cand.PB(v);
            v=v/2;
        }
        ll r=SIZE(cand);//cout << r << endl;
        ll ans=0;
        REP(j,1<<r){
            ll v_sub=0;ll w_sub=0;
            REP(k,r){
                if((j>>k)&1){
                    v_sub+=vw[cand[k]-1].first;
                    w_sub+=vw[cand[k]-1].second;
                }
            }
            if(w_sub<=l)ans=max(ans,dp[v-1][l-w_sub]+v_sub);
        }
        cout<<ans<<endl;
    }
}

D_TLE_py


n=int(input())
vw=[list(map(int,input().split())) for i in range(n)]
#vmax=max(i[0] for i in vw)
#Préparer DP pour le pré-calcul
#1~2^Calculez jusqu'à 10 en premier
dp=[[0]*(10**5+1) for i in range(2**10)]
#Pré-calcul
def dfs(i):
    global n,vw,dp
    j=i//2
    for k in range(10**5,-1,-1):
        if dp[j-1][k]!=0 or k==0:
            if k+vw[i-1][1]<=10**5:
                dp[i-1][k+vw[i-1][1]]=max(dp[j-1][k]+vw[i-1][0],dp[i-1][k+vw[i-1][1]])
            dp[i-1][k]=max(dp[j-1][k],dp[i-1][k])
    if i*2<=2**10 and i*2<=n:
        dfs(i*2)
        if i*2+1<=2**10 and i*2+1<=n:
            dfs(i*2+1)
dfs(1)
for i in range(2**10):
    for j in range(10**5):
        dp[i][j+1]=max(dp[i][j],dp[i][j+1])
q=int(input())
for i in range(q):
    #Suivez chaque sous-arbre
    #Explorez le reste ici
    v,l=map(int,input().split())
    cand=[]
    while v>2**10:
        cand.append(v//2)
        v=v//2
    r=len(cand)
    ans=0
    for j in range(2**r):
        v_sub=0
        w_sub=0
        for k in range(r):
            v_sub+=vw[cand[k]-1][0]*(j>>k)&1
            w_sub+=vw[cand[k]-1][1]*(j>>k)&1
        if w_sub>l:
            continue
        else:
            ans=max(ans,dp[v-1][l-w_sub]+v_sub)
    print(ans)

E problème

Le problème F n'a pas encore été résolu (il faudra du temps pour le résoudre), c'est donc le dernier problème à être expliqué dans cet article.

À première vue, je savais que c'était un principe d'encapsulation, mais je n'avais pas l'impression de pouvoir arriver à temps pour ma mise en œuvre, donc je ne pouvais pas le résoudre. Cependant, j'ai trouvé que je pouvais le passer si je le calculais plus tard, et c'était la même méthode que l'autre réponse, alors j'aimerais l'examiner d'ici la fin de la journée **.

Dans ce qui suit, DP [i] [s, t] = (le nombre de méthodes dans lesquelles le produit logique est s et la somme logique est t lorsque i nombres sont sélectionnés) **, et le nombre de DP est limité. Je l'ai implémenté, et si je l'ai implémenté correctement, j'ai pu le forcer. Ce n'est pas une méthode générale car je pense que ce ne sera pas à temps pour le montant du calcul, mais ** Dans le cas de DP de deux dimensions ou plus, il peut être accéléré en utilisant map **, ** Dans unordeed_map, la paire peut être utilisée comme clé J'ai appris trois choses: il est indéfini **, et ** il y a une limite sur le nombre de DP, et si vous décidez de l'arrière de la séquence préparée par DP, vous n'avez pas besoin d'une matrice pour le stockage temporaire et vous pouvez accélérer **.

E.cc


//Comprendre(Ordre alphabétique)
#include<algorithm>//sort,Recherche de bisection,Tel
#include<bitset>//Jeu de bits de longueur fixe
#include<cmath>//pow,journal etc.
#include<complex>//Nombre complexe
#include<deque>//File d'attente d'accès double
#include<functional>//trier plus
#include<iomanip>//setprecision(Erreur de sortie en virgule flottante)
#include<iostream>//Entrée sortie
#include<iterator>//Régler l'opération(Ensemble de produits,Ensemble de somme,Ensemble de différences, etc.)
#include<map>//map(dictionnaire)
#include<numeric>//iota(Génération d'une chaîne entière),pgcd et lcm(c++17)
#include<queue>//queue
#include<set>//ensemble
#include<stack>//empiler
#include<string>//Chaîne
#include<unordered_map>//Carte avec itérateur mais sans ordre
#include<unordered_set>//Il y a un itérateur mais l'ordre n'est pas maintenu défini
#include<utility>//pair
#include<vector>//Tableau de longueur variable

using namespace std;
typedef long long ll;

//macro
//pour la relation de boucle
//L'argument est(Variables dans la boucle,Amplitude de mouvement)Ou(Variables dans la boucle,Premier numéro,Nombre d'extrémités)、のどちらOu
//Les variables de boucle sans D sont incrémentées de 1 et les variables de boucle avec D sont décrémentées de 1.
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//x est un conteneur tel que vector
#define ALL(x) (x).begin(),(x).end() //Je souhaite omettre des arguments tels que le tri
#define SIZE(x) ((ll)(x).size()) //taille à la taille_Changement de t à ll
#define MAX(x) *max_element(ALL(x)) //Trouvez la valeur maximale
#define MIN(x) *min_element(ALL(x)) //Trouvez la valeur minimale
//constant
#define INF 1000000000000 //10^12:Valeur extrêmement élevée,∞
#define MOD 1000000007 //10^9+7:Droit commun
#define MAXR 100000 //10^5:Portée maximale de la baie(Utilisé pour l'énumération des nombres premiers, etc.)
//Abréviation
#define PB push_back //Insérer dans le vecteur
#define MP make_pair //constructeur de paires
#define F first //Le premier élément de paire
#define S second //Le deuxième élément de paire

signed main(){
    //Code pour accélérer la saisie
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n,k,s,t;cin >> n >> k >> s >> t;
    vector<ll> b(n);REP(i,n)cin >> b[i];
    vector<ll> a;
    REP(i,n){
        bool f=true;
        REP(j,18){
            if((s>>j)&1 and !((b[i]>>j)&1)){
                f=false;break;
            }
            if(!((t>>j)&1) and (b[i]>>j)&1){
                f=false;break;
            }
        }
        if(f)a.PB(b[i]);
    }
    n=SIZE(a);
    k=min(n,k);
    //cout << n << endl;
    //cout << n << endl;
    //unordered_la carte ne peut pas utiliser la paire comme clé
    //dp_Il est lent de préparer les sous(Cela change plusieurs fois simplement en ne préparant pas)
    //OK si vous le faites dans l'ordre inverse
    vector<map<pair<ll,ll>,ll>> dp(k);
    REP(i,n){
        FORD(j,k-2,0){
            for(auto l=dp[j].begin();l!=dp[j].end();l++){
                dp[j+1][MP((l->F.F)&a[i],(l->F.S)|a[i])]+=(l->S);
            }
        }
        dp[0][MP(a[i],a[i])]=1;
    }
    ll ans=0;
    REP(i,k)ans+=(dp[i][MP(s,t)]);
    cout << ans << endl;
}

Problème F

Je suis satisfait de la résolution jusqu'à E, je vais donc l'omettre cette fois.

Recommended Posts

Critique du concours de programmation Tokio Marine & Nichido 2020
Examen du concours de programmation Keyence 2020
Revue du concours de programmation NOMURA 2020
Examen du concours de programmation HHKB 2020
Bilan 2019 du concours de programmation Sumitomo Mitsui Trust Bank
concours yukicoder 259 avis
concours yukicoder 264 avis
Concours de programmation Acing 2020
concours yukicoder 261 avis
concours yukicoder 267 avis
Concours de programmation HHKB 2020
concours yukicoder 266 avis
concours yukicoder 263 avis
yukicoder contest 268 avis
Critique du concours AtCoder Beginner Contest 152
AtCoder Grand Contest 041 Critique
Critique du concours AtCoder Débutant 160
Critique du concours AtCoder Débutant 178
Critique du concours AtCoder pour débutant 166
AtCoder Débutant Contest 167 Évaluation
Critique du concours AtCoder
AtCoder Débutant Contest 169 Évaluation
AtCoder Grand Contest 048 Critique
Critique du concours AtCoder Débutant 181
Après le "Concours de programmation Diverta 2019"
AtCoder Débutant Contest 171 Critique
Critique du concours AtCoder pour débutant 182
Critique du concours AtCoder Débutant 180
Critique du concours AtCoder pour débutant 177
AtCoder Débutant Contest 168 Critique
AtCoder Grand Contest 045 Critique
AtCoder Grand Contest 044 Critique
Critique du concours AtCoder
Critique du concours AtCoder pour débutant 172
AtCoder Regular Contest 106 Évaluation
Critique du concours AtCoder
AtCoder Grand Contest 046 Critique
AtCoder Débutant Contest 175 Critique
Critique du concours AtCoder
Critique du concours AtCoder Beginner Contest 153
Critique du concours AtCoder pour débutant 156
AtCoder Débutant Contest 161 Critique
AtCoder Débutant Contest 170 Critique
Revue du concours régulier AtCoder 104
Critique du concours AtCoder
AtCoder Débutant Contest 173 Critique
AtCoder Débutant Contest 155 Critique
AtCoder Débutant Contest 162 Évaluation
Concours de programmation Atcoder Acing Python
Notes pour le concours de programmation HHKB 2020
atcoder Review of Panasonic Programming Contest 2020, jusqu'à la question E (Python)