[PYTHON] Critique du concours de programmation Tokio Marine & Nichido 2020

Les résultats de cette fois

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.