Revue du concours régulier AtCoder 105

Les résultats de cette fois

スクリーンショット 2020-10-13 10.18.07.png

Impressions de cette époque

Seuls les problèmes A et B ont pu être résolus, et il s'est avéré que le problème B était une fausse solution plus tard, et quand j'ai essayé de résoudre le problème C, seuls quelques cas sont devenus WA et j'ai beaucoup rencontré. Puisque le problème C est une méthode gourmande, des erreurs peuvent exister, mais j'ai encore du mal à ne pas savoir ce qui ne va pas.

(C'était difficile, mais je l'ai résolu par le chemin le plus long selon la méthode de la solution. Pour plus de détails, voir l'explication du problème C ci-dessous.)

Problème A

Voyez s'il correspond en deux parties. À ce stade, il est bon de penser que le nombre total sélectionné en faisant une certaine sélection doit être exactement la moitié du total.

Par conséquent, s'il est déterminé si l'un des $ a + b, b + c, c + d, d + a, a + c, b + d, a, b, c, d $ est exactement divisé par deux. Est bon. De plus, vous n'avez pas à réfléchir lorsque vous choisissez trois nombres.

A.py


a,b,c,d=map(int,input().split())
cand=[a+b,b+c,c+d,d+a,a+c,b+d,a,b,c,d]
s=sum([a,b,c,d])
if s%2==1:
    print("No")
elif s//2 in cand:
    print("Yes")
else:
    print("No")

Problème B

Faites la simulation honnêtement. De plus, comme il n'y a qu'un seul numéro restant et que la même opération est effectuée pour le même numéro, enregistrez le numéro avec set. Les ensembles alignés sont pratiques car vous choisissez les nombres maximum et minimum.

B.cc


//Options de débogage:-fsanitize=undefined,address

//Optimisation du compilateur
#pragma GCC optimize("Ofast")

//Inclure etc.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//macro
//pour 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.
//FORA est une gamme de déclaration(Si c'est difficile à utiliser, effacez-le)
#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--)
#define FORA(i,I) for(const auto& i:I)
//x est un conteneur tel que vector
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//constant
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Droit commun
#define MAXR 100000 //10^5:Portée maximale de la baie
//Abréviation
#define PB push_back //Insérer
#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;cin>>n;
    set<ll> ans;
    REP(i,n){
        ll a;cin>>a;
        ans.insert(a);
    }
    while(SIZE(ans)!=1){
        ll l,r;l=*ans.begin();r=*--ans.end();
        ans.erase(r);
        ans.insert(r-l);
    }
    cout<<*ans.begin()<<endl;
}

Problème C

Je ne pouvais pas faire AC avec la méthode gourmande pour le problème C, donc j'ai écrit le programme en incorporant la plus longue voie d'explication. Bien qu'il soit plus lourd en calcul que l'explication, il a été accéléré par l'ajout de l'élagage.

Tout d'abord, essayez n'importe quelle commande de chameau et suivez $ N! $. De plus, pour chaque commande, il faut $ O (M \ fois N ^ 2) $ pour trouver la distance entre les chameaux nécessaire pour traverser chaque partie. Par conséquent, le montant du calcul est de $ O (N! \ Fois M \ fois N ^ 2) $, ce qui est trop tard, alors ** accélérez en taillant bien ** (j'ai abandonné pendant le concours). Cependant, jusqu'à ** $ 10 ^ {11} $ peuvent passer même avec une solution non supposée en accélérant d'un facteur constant **, alors n'abandonnez pas.)

Premièrement, la politique ci-dessus est

① Déterminez l'ordre des chameaux (utilisez simplement $ next $ \ _ $ permutation $ (reference)) (2) Commencez avec un chameau avec chaque partie (rue $ M $) et découvrez quel chameau (rue $ N-1 $) ne peut pas être chargé.

Ce sera dans l'ordre.

De plus, si vous utilisez la ** méthode gloutonne dans ②, vous marcherez sur le cas d'angle et deviendrez WA **. Ici, en commençant par un chameau et en considérant les informations sur le chameau qui ne peut pas être chargé (doit être séparé par la longueur de la partie) comme un ** côté **, ** du premier chameau au dernier chameau. Ce serait bien si nous pouvions réduire le problème de trouver le chemin le plus long.

Par conséquent, DP avec $ dp [i]: = $ (la plus longue distance entre le premier chameau et le $ i $ ème chameau) devrait être fait dans l'instruction do-while de $ next $ \ _ $ permutation $. .. Le moment où une certaine partie est sélectionnée est considéré comme une transition, mais les détails sont omis ici.


(Par la suite, la vitesse sera augmentée d'un facteur constant.) (Bien sûr, vous pouvez passer simplement en accélérant pour réduire la première partie.)

Quand $ (a, b), (c, d) $ existe, qui gère les pièces par (longueur, poids) et devient $ a \ geqq c $ et $ b \ leqq d $, $ (a, b) Si $ est satisfait, $ (c, d) $ tient également, donc ** vous pouvez réduire le nombre de pièces afin que la taille de la longueur et la taille du poids correspondent entre toutes les pièces **. Par conséquent, disposez les pièces par ordre croissant de longueur, regardez celle avec la plus grande longueur et celle avec la plus petite longueur, et si ce qui précède tient, vérifiez que la plus petite n'est pas utilisée. Comme cela est fait avec n'importe quelle pièce, le montant total du calcul est de $ O (M ^ 2) $. Vous pouvez également élaguer ** les pièces qui ont été vérifiées une fois car vous n'avez pas à les rechercher.

Deuxièmement, ** si le chameau le plus lourd n'est pas sur le bord, il vaut mieux le mettre sur le bord ** (non prouvé), afin que vous puissiez fixer le dernier chameau avec le chameau le plus lourd. Vous n'avez qu'à penser à l'ordre des chameaux sur la rue $ (N-1)! $.

De plus, les parties sont disposées par ordre croissant de poids ($ \ leftrightarrow $ ordre croissant de longueur), donc lorsqu'une partie ne peut pas être placée à partir d'un chameau, le chameau sur lequel la partie suivante ne peut pas être placée sera après ce chameau. Par conséquent, vous pouvez enregistrer la quantité de calcul ** comme la méthode de mise à l'échelle **.

En accélérant les temps constants ci-dessus, $ O (N! \ Time M \ times N ^ 2) $ est changé en $ O (M ^ 2 + (N-1)! \ Time N \ times (M + N)) $ Vous pouvez le laisser tomber. En considérant le pire des cas $ N = 10, M = 100000 $, il peut être ramené à environ 10 $ ^ {11} $ → 10 $ ^ {10} $. De plus, je taillais pour 10 $ ^ {10} $, donc j'ai pu le ramener à 26 ms (le plus rapide au 13 octobre 2020). Si la vitesse peut être augmentée à ce niveau, j'estime que même si le pire des cas est inclus, il sera possible de passer.

スクリーンショット 2020-10-13 13.09.44.png

C_fastest.cc


#pragma GCC optimize("Ofast")

#include<bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0;i<int(n);i++)
#define REPD(i,n) for(int i=n-1;i>=0;i--)
#define SIZE(x) int(x.size())
#define INF 2000000000
#define PB push_back
#define F first 
#define S second

int w[8];
pair<int,int> partsx[100000];
bool info[100000];
int n,m;
vector<pair<int,int>> parts;

inline int read(){
	int x=0,w=0;char ch=0;
	while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return w?-x:x;
}

signed main(){
    n=read();m=read();
    REP(i,n)w[i]=read();
    sort(w,w+n);
    REP(i,m){partsx[i].F=read();partsx[i].S=read();}
    sort(partsx,partsx+m);
    int ma=INF;
    REP(i,m)ma=min(ma,partsx[i].S);
    if(ma<w[n-1]){
        cout<<-1<<endl;
        return 0;
    }
    REP(i,m)info[i]=true;
    REPD(i,m){
        if(!info[i])continue;
        REP(j,i){
            if(partsx[i].S<=partsx[j].S){
                info[j]=false;
            }
        }
    }
    REP(i,m)if(info[i])parts.PB(partsx[i]);
    m=SIZE(parts);
    int ans=INF;
    do{
        vector<int> dp(n,0);
        REP(j,n-1){
            int k=j;int check=w[k];
            REP(i,m){
                while(k!=n){
                    if(parts[i].S<check){
                        dp[k]=max(dp[j]+parts[i].F,dp[k]);
                        break;
                    }
                    k++;
                    check+=w[k];
                }
                if(k==n){
                    dp[n-1]=max(dp[j],dp[n-1]);
                    break;
                }
            }
        }
        ans=min(ans,dp[n-1]);
    }while(next_permutation(w,w+n-1));
    cout<<ans<<endl;
}

Problème après D

Recommended Posts

Revue du concours régulier AtCoder 105
AtCoder Regular Contest 106 Évaluation
Revue du concours régulier AtCoder 104
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
Concours régulier AtCoder 106 Remarque
Critique du concours AtCoder
AtCoder Débutant Contest 169 Évaluation
AtCoder Grand Contest 048 Critique
Critique du concours AtCoder Débutant 181
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
Concours régulier AtCoder 105 Remarque
AtCoder Grand Contest 045 Critique
AtCoder Grand Contest 044 Critique
Critique du concours AtCoder
Critique du concours AtCoder pour débutant 172
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
Critique du concours AtCoder
AtCoder Débutant Contest 173 Critique
AtCoder Débutant Contest 155 Critique
AtCoder Débutant Contest 162 Évaluation
AtCoder Regular Contest # 002 Problème C
Rapport de participation au concours régulier AtCoder 105
AtCoder Regular Contest 104 Rapport de participation
AtCoder Beginner Contest 066 Revoir les questions précédentes
Concours AtCoder Débutant 177
concours yukicoder 259 avis
concours yukicoder 264 avis
Concours AtCoder Débutant 179
Concours AtCoder Débutant 172
Concours AtCoder Débutant 180
concours yukicoder 261 avis
concours yukicoder 267 avis
Concours AtCoder Débutant 173
concours yukicoder 266 avis
Concours Atcoder Débutant 153
concours yukicoder 263 avis
yukicoder contest 268 avis
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