[PYTHON] Revue du concours régulier AtCoder 105
Les résultats de cette fois
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.
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