[PYTHON] AtCoder Grand Contest 046 Critique
Les résultats de cette fois
Impressions de cette époque
R Le problème était étonnamment simple et surprenant. En conséquence, j'aurais dû suivre ma propre solution pour le problème B, donc je pense que si je peux gagner en confiance dans les problèmes de diff d'eau et de diff bleu, je pourrai AC.
Problème A
Je suis content que la vitesse ait été raisonnablement bien résolue.
Comme le montre la figure ci-dessous, si le point de départ est l'origine O du plan complexe, vous pouvez voir que l'angle de déviation est $ + x $. Aussi, comme il est clair qu'ils sont toujours sur la même circonférence après l'opération, il suffit que l'angle de déviation soit égal au début de l'opération, et après l'opération $ k $ fois, il tourne autour de $ l $ et atteint parfois l'origine O. Pensez au plus petit d'entre eux.
Par conséquent, $ kx = 360 l \ leftrightarrow k = \ frac {360l} {x} $ tient. Ici, puisque $ k $ est un entier, $ 360l $ est un multiple de $ x $ et $ 360 $, et le minimum $ l $ peut être considéré, il s'agit donc du multiple commun minimum. De ce qui précède, la réponse est le multiple commun minimum de 360 $ $ et $ x $ divisé par $ x $.
A.py
from math import gcd
def lcm(a,b):
return a//gcd(a,b)*b
x=int(input())
print(lcm(360,x)//x)
Problème B
J'étais impatient et je l'ai résolu parce que j'avais peur de ne pas pouvoir le résoudre ...
Tout d'abord, j'ai mal lu diverses choses et j'ai essayé de trouver un modèle qui me convenait. Une mauvaise lecture n'est pas bonne, mais je pense que ce n'est pas une mauvaise politique de rechercher d'abord un modèle pratique. Ici, ** dans l'ordre, vous devez réfléchir directement à la manière de postuler ** quelle que soit la commande réelle. ** N'est-il pas préférable de classer les observations selon que la ligne ou la colonne est peinte **? J'ai pensé, mais en raison de la considération, j'ai trouvé cela difficile. ↑ Vous ne pouvez pas l'utiliser ici pendant environ 30 minutes ...
De la politique ci-dessus, nous sommes passés à la politique basée sur la méthode de planification dynamique. La seule chose qui a été déplacée vers cette politique est que vous n'avez qu'à gérer l'état ** car vous n'avez qu'à ajouter des lignes ou des colonnes ** et qu'il n'y a que des transitions (D + C) - (B + A) **. Est la raison.
Ici, le tableau DP doit être ** dp [i] [x, y] = (nombre total de peintures pour que la ligne devienne x et la colonne devienne y en i opérations) **. Je pense que c'est évident. En outre, la transition ** DP dépend de si vous souhaitez ajouter une ligne ou une colonne **. Dans le premier cas, dp [i] [x, y] → dp [i + 1] [x + 1, y], et dans le dernier cas, dp [i] [x, y] → dp [i + 1] [x , Y + 1].
À ce stade, puisqu'il existe un moyen de peindre le motif à couvrir au moment de la transition, dp [i + 1] de dp [i + 1] [x, y + 1] et dp [i + 1] [x + 1, y] +2] Considérez la transition vers [x + 1, y + 1] dans la figure ci-dessous. (** J'essayais d'ajuster l'échantillon en utilisant la symétrie sans examiner attentivement ce modèle **. Je vais y réfléchir et l'utiliser la prochaine fois.)
Ici, on peut voir à partir de la figure ci-dessus que le motif à couvrir se produit dans la ligne $ x + 1 $ et la colonne $ y + 1 $, alors considérez la ** partie commune $ x \ times y $ matrice **. J'ai pensé que je pourrais poursuivre l'examen.
De plus, lors du passage de la matrice $ (x + 1) \ times y $ et de la matrice $ x \ times (y + 1) $ à la matrice $ (x + 1) \ times (y + 1) $ Le modèle qui souffre est la matrice $ (x + 1) \ times y $ et $ x \ times lors de la génération de la matrice $ (x + 1) \ times (y + 1) $ à partir de la matrice $ x \ times y $. Il peut être reformulé comme un motif qui peut être créé via l'une des matrices (y + 1) $, et le motif est comme illustré dans la figure ci-dessous.
Par conséquent, vous pouvez effacer la partie couverte dans la figure ci-dessus, mais "Si $ x + 1 $ devient A et $ y + 1 $ devient B, aucune couverture ne se produira" et "$ x + 1" Si $ dépasse C et $ y + 1 $ dépasse D, cela n'existe pas. »Si vous l'implémentez soigneusement, vous obtiendrez le deuxième code.
Dans le deuxième code, map est utilisée dans le conteneur qui stocke le résultat de dp, et ** cela prend plusieurs heures pour y accéder, donc il est à peine calculé **. Ici, il est possible d'accélérer environ 5 à 10 fois en utilisant un tableau normal sans utiliser de map, et la définition de l'élément du conteneur qui stocke dp change comme suit.
** dp [i] [x, y] = (nombre total de peintures qui forment les lignes x et les colonnes y en i opérations) ** ↓ ** dp [i] [j] = (nombre total de peintures lorsque le nombre de lignes est augmenté de j en i opérations) **
Par conséquent, x = j + A et y = i-j + B, et si vous l'implémentez en faisant attention à l'index, vous pouvez avoir la même discussion que précédemment, qui est le premier code.
B_AC.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
//constant
#define INF 1000000000000 //10^12:Valeur extrêmement élevée,∞
#define MOD 998244353 //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
template<ll mod> class modint{
public:
ll val=0;
//constructeur
modint(ll x=0){while(x<0)x+=mod;val=x%mod;}
//Copier le constructeur
modint(const modint &r){val=r.val;}
//Opérateur arithmétique
modint operator -(){return modint(-val);} //unaire
modint operator +(const modint &r){return modint(*this)+=r;}
modint operator -(const modint &r){return modint(*this)-=r;}
modint operator *(const modint &r){return modint(*this)*=r;}
modint operator /(const modint &r){return modint(*this)/=r;}
//Opérateur d'assignation
modint &operator +=(const modint &r){
val+=r.val;
if(val>=mod)val-=mod;
return *this;
}
modint &operator -=(const modint &r){
if(val<r.val)val+=mod;
val-=r.val;
return *this;
}
modint &operator *=(const modint &r){
val=val*r.val%mod;
return *this;
}
modint &operator /=(const modint &r){
ll a=r.val,b=mod,u=1,v=0;
while(b){
ll t=a/b;
a-=t*b;swap(a,b);
u-=t*v;swap(u,v);
}
val=val*u%mod;
if(val<0)val+=mod;
return *this;
}
//Opérateur de comparaison d'équivalence
bool operator ==(const modint& r){return this->val==r.val;}
bool operator <(const modint& r){return this->val<r.val;}
bool operator !=(const modint& r){return this->val!=r.val;}
};
using mint = modint<MOD>;
//Flux d'E / S
istream &operator >>(istream &is,mint& x){//N'ajoutez pas de const à x
ll t;is >> t;
x=t;
return (is);
}
ostream &operator <<(ostream &os,const mint& x){
return os<<x.val;
}
mint dp[6000][3000]={0};
signed main(){
ll A,B,C,D;cin>>A>>B>>C>>D;
//i-th sélectionne i colonnes ou lignes
//a=Quand A correspond à l'index 0 du tableau
//dp[i][j]Comme la somme des éléments est A+B+i,La somme des éléments de a est j+A,La somme des éléments de b est B+i-j
//j+A est A ou plus et C ou moins,B+i-j est B ou plus et D ou moins
//j vaut 0 ou plus C-A ou moins et B+i-D ou plus et i ou moins
dp[0][0]=1;
REP(i,(D+C)-(B+A)){
FOR(j,max(ll(0),B+i-D),min(C-A,i)){
if(B+i-j!=D)dp[i+1][j]+=(dp[i][j]*mint(j+A));
if(A+j!=C)dp[i+1][j+1]+=(dp[i][j]*mint(B+i-j));
}
if(i==0)continue;
FOR(j,max(ll(0),B+i+1-D),min(C-A,i+1)){
if(j!=0 and i+1!=j){
dp[i+1][j]-=(dp[i-1][j-1]*mint(j+A-1)*mint(B+i-j));
}
}
}
cout<<dp[(D+C)-(B+A)][C-A]<<endl;
}
B_TLE.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
//constant
#define INF 1000000000000 //10^12:Valeur extrêmement élevée,∞
#define MOD 998244353 //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
template<ll mod> class modint{
public:
ll val=0;
//constructeur
modint(ll x=0){while(x<0)x+=mod;val=x%mod;}
//Copier le constructeur
modint(const modint &r){val=r.val;}
//Opérateur arithmétique
modint operator -(){return modint(-val);} //unaire
modint operator +(const modint &r){return modint(*this)+=r;}
modint operator -(const modint &r){return modint(*this)-=r;}
modint operator *(const modint &r){return modint(*this)*=r;}
modint operator /(const modint &r){return modint(*this)/=r;}
//Opérateur d'assignation
modint &operator +=(const modint &r){
val+=r.val;
if(val>=mod)val-=mod;
return *this;
}
modint &operator -=(const modint &r){
if(val<r.val)val+=mod;
val-=r.val;
return *this;
}
modint &operator *=(const modint &r){
val=val*r.val%mod;
return *this;
}
modint &operator /=(const modint &r){
ll a=r.val,b=mod,u=1,v=0;
while(b){
ll t=a/b;
a-=t*b;swap(a,b);
u-=t*v;swap(u,v);
}
val=val*u%mod;
if(val<0)val+=mod;
return *this;
}
//Opérateur de comparaison d'équivalence
bool operator ==(const modint& r){return this->val==r.val;}
bool operator <(const modint& r){return this->val<r.val;}
bool operator !=(const modint& r){return this->val!=r.val;}
};
using mint = modint<MOD>;
//Flux d'E / S
istream &operator >>(istream &is,mint& x){//N'ajoutez pas de const à x
ll t;is >> t;
x=t;
return (is);
}
ostream &operator <<(ostream &os,const mint& x){
return os<<x.val;
}
signed main(){
ll A,B,C,D;cin>>A>>B>>C>>D;
//i-th sélectionne i colonnes ou lignes
vector<map<pair<ll,ll>,mint>> dp((D+C)-(B+A)+1);
dp[0][MP(A,B)]=1;
REP(i,(D+C)-(B+A)){
for(auto j=dp[i].begin();j!=dp[i].end();j++){
ll a,b;a=j->F.F;b=j->F.S;
if(b!=D){
dp[i+1][MP(a,b+1)]+=(dp[i][MP(a,b)]*mint(a));
}
if(a!=C){
dp[i+1][MP(a+1,b)]+=(dp[i][MP(a,b)]*mint(b));
}
}
if(i==0)continue;
for(auto j=dp[i+1].begin();j!=dp[i+1].end();j++){
ll a,b;a=j->F.F;b=j->F.S;
if(a!=A and b!=B){
dp[i+1][MP(a,b)]-=(dp[i-1][MP(a-1,b-1)]*mint(a-1)*mint(b-1));
}
}
}
cout<<dp[(D+C)-(B+A)][MP(C,D)]<<endl;
}
Problème après C
Je vais sauter cette fois.
Recommended Posts