[PYTHON] AtCoder Grand Contest 046 Bewertung
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
A Das Problem war unerwartet einfach und überraschend. Infolgedessen hätte ich meine eigene Lösung für Problem B befolgen sollen, und ich denke, wenn ich Vertrauen in die Probleme von Wasserdiff und Blaudiff gewinnen kann, kann ich Wechselstrom erzeugen.
Problem A
Ich bin froh, dass die Geschwindigkeit einigermaßen gut gelöst wurde.
Wie in der folgenden Abbildung gezeigt, können Sie sehen, dass der Abweichungswinkel $ + x $ beträgt, wenn der Startpunkt der Ursprung O der komplexen Ebene ist. Da klar ist, dass sie sich nach der Operation immer auf demselben Umfang befinden, ist es ausreichend, wenn der Abweichungswinkel gleich dem Beginn der Operation ist und nach der Operation $ k $ mal um $ l $ herumgeht und manchmal den Ursprung O erreicht. Denken Sie an den kleinsten von ihnen.
Daher gilt $ kx = 360 l \ leftrightarrow k = \ frac {360l} {x} $. Da $ k $ eine ganze Zahl ist, ist $ 360l $ ein Vielfaches von $ x $ und $ 360 $, und das Minimum $ l $ kann berücksichtigt werden, so dass es das minimale gemeinsame Vielfache ist. Aus dem oben Gesagten ergibt sich die minimale gemeinsame Vielfache von $ 360 $ und $ x $ geteilt durch $ 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)
B-Problem
Ich war ungeduldig und löste es, weil ich mir Sorgen machte, dass ich es nicht lösen könnte ...
Zuerst habe ich verschiedene Dinge falsch verstanden und versucht, ein für mich geeignetes Muster zu finden. Fehlinterpretation ist nicht gut, aber ich denke, es ist keine schlechte Politik, zuerst nach einem geeigneten Muster zu suchen. Hier, ** in der Reihenfolge, sollten Sie direkt darüber nachdenken, wie Sie sich bewerben können **, unabhängig von der tatsächlichen Bestellung. ** Ist es nicht besser, Fälle danach zu klassifizieren, ob die Zeile oder Spalte gezeichnet ist **? Ich dachte, aber aufgrund von Überlegungen fand ich es schwierig. ↑ Sie können es hier etwa 30 Minuten lang nicht verwenden ...
Von der obigen Richtlinie sind wir zu der Richtlinie übergegangen, die auf der dynamischen Planungsmethode basiert. Ich bin zu dieser Richtlinie übergegangen **, weil ich nur Zeilen oder Spalten hinzufügen muss, also muss ich nur den Status verwalten ** und ** Übergänge sind nur (D + C) - (B + A) mal ** Ist der Grund.
Hier sollte das DP-Array ** dp [i] [x, y] = sein (Gesamtzahl der Bilder, so dass die Zeile in i-Operationen zu x und die Spalte zu y wird) **. Ich denke es ist offensichtlich. Der ** DP-Übergang hängt auch davon ab, ob Sie eine Zeile oder eine Spalte ** hinzufügen möchten. Im ersteren Fall ist dp [i] [x, y] → dp [i + 1] [x + 1, y] und im letzteren Fall dp [i] [x, y] → dp [i + 1] [x , Y + 1].
Zu diesem Zeitpunkt gibt es dp [i + 1] von dp [i + 1] [x, y + 1] und dp [i + 1] [x + 1, y], da es eine Möglichkeit gibt, das zum Zeitpunkt des Übergangs abzudeckende Muster zu malen. +2] Betrachten Sie den Übergang zu [x + 1, y + 1] in der folgenden Abbildung. (** Ich habe versucht, die Probe mit Symmetrie anzupassen, ohne dieses Muster sorgfältig zu berücksichtigen **. Ich werde darüber nachdenken und es beim nächsten Mal verwenden.)
Hier ist aus der obigen Abbildung ersichtlich, dass das abzudeckende Muster in der Zeile $ x + 1 $ und in der Spalte $ y + 1 $ vorkommt. Betrachten Sie also den ** gemeinsamen Teil $ x \ times y $ Matrix **. Ich dachte, ich könnte mit der Überlegung fortfahren.
Außerdem beim Übergang von der Matrix $ (x + 1) \ mal y $ und der Matrix $ x \ mal (y + 1) $ zur Matrix $ (x + 1) \ mal (y + 1) $ Das Muster, das darunter leidet, ist die Matrix $ (x + 1) \ mal y $ und $ x \ mal, wenn die Matrix $ (x + 1) \ mal (y + 1) $ aus der Matrix $ x \ mal y $ erzeugt wird. Es kann als Muster umformuliert werden, das über eine der (y + 1) $ -Matrizen erstellt werden kann. Das Muster ist in der folgenden Abbildung dargestellt.
Daher können Sie den abgedeckten Teil in der obigen Abbildung löschen, aber "Wenn $ x + 1 $ zu A und $ y + 1 $ zu B wird, tritt keine Abdeckung auf" und "$ x + 1". Wenn $ C überschreitet und $ y + 1 $ D überschreitet, existiert es nicht. “Wenn Sie es sorgfältig implementieren, erhalten Sie den zweiten Code.
Im zweiten Code wird map in dem Container verwendet, in dem das Ergebnis von dp gespeichert ist, und ** der Zugriff dauert mehrere Stunden, sodass er kaum berechnet wird **. Hier ist es möglich, mit einem normalen Array ohne Verwendung von map etwa fünf- bis zehnmal schneller zu werden, und die Definition des Elements des Containers, in dem dp gespeichert ist, ändert sich wie folgt.
** dp [i] [x, y] = (Gesamtzahl der Bilder, die in i-Operationen Zeilen x und Spalten y bilden) ** ↓ ** dp [i] [j] = (Gesamtzahl der Bilder, wenn die Anzahl der Linien in i-Operationen um j erhöht wird) **
Daher ist x = j + A und y = i-j + B, und wenn Sie es unter Berücksichtigung des Index implementieren, können Sie dieselbe Diskussion wie zuvor führen, bei der es sich um den ersten Code handelt.
B_AC.cc
//Einschließen(Alphabetischer Reihenfolge)
#include<algorithm>//sort,Halbierungssuche,Eine solche
#include<bitset>//Bit mit fester Länge gesetzt
#include<cmath>//pow,Protokoll usw.
#include<complex>//Komplexe Zahl
#include<deque>//Double-Ended-Zugriffswarteschlange
#include<functional>//größer sortieren
#include<iomanip>//setprecision(Gleitkomma-Ausgabefehler)
#include<iostream>//Input-Output
#include<iterator>//Betrieb einstellen(Produktset,Summensatz,Differenzsatz etc.)
#include<map>//map(Wörterbuch)
#include<numeric>//iota(Generierung einer Ganzzahlzeichenfolge),gcd und lcm(c++17)
#include<queue>//Warteschlange
#include<set>//einstellen
#include<stack>//Stapel
#include<string>//String
#include<unordered_map>//Karte mit Iterator, aber ohne Ordnung
#include<unordered_set>//Es gibt einen Iterator, aber die Reihenfolge wird nicht festgelegt
#include<utility>//pair
#include<vector>//Array mit variabler Länge
using namespace std;
typedef long long ll;
//Makro
//für Schleifenbeziehung
//Das Argument ist(Variablen in der Schleife,Bewegungsumfang)Oder(Variablen in der Schleife,Erste Nummer,Anzahl der Endungen)、のどちらOder
//Wenn es kein D gibt, wird die Schleifenvariable um 1 erhöht, und wenn es ein D gibt, wird die Schleifenvariable um 1 dekrementiert.
#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 ist ein Container wie ein Vektor
#define ALL(x) (x).begin(),(x).end() //Ich möchte Argumente wie sort weglassen
#define SIZE(x) ((ll)(x).size()) //Größe zu Größe_Wechseln Sie von t nach ll
//Konstante
#define INF 1000000000000 //10^12:Extrem großer Wert,∞
#define MOD 998244353 //10^9+7:Gemeinsames Recht
#define MAXR 100000 //10^5:Maximale Reichweite des Arrays(Wird für die Aufzählung von Primzahlen usw. verwendet.)
//Abkürzung
#define PB push_back //In Vektor einfügen
#define MP make_pair //Paarkonstruktor
#define F first //Das erste Element des Paares
#define S second //Das zweite Element des Paares
template<ll mod> class modint{
public:
ll val=0;
//Konstrukteur
modint(ll x=0){while(x<0)x+=mod;val=x%mod;}
//Konstruktor kopieren
modint(const modint &r){val=r.val;}
//Arithmetischer Operator
modint operator -(){return modint(-val);} //einstellig
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;}
//Aufgabenverwalter
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;
}
//Äquivalenzvergleichsoperator
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>;
//E / A-Stream
istream &operator >>(istream &is,mint& x){//Fügen Sie x nicht const hinzu
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 wählt i Spalten oder Zeilen aus
//a=Wenn A dem Index 0 des Arrays entspricht
//dp[i][j]Da die Summe der Elemente A ist+B+i,Die Summe der Elemente von a ist j+A,Die Summe der Elemente von b ist B.+i-j
//j+A ist A oder mehr und C oder weniger,B+i-j ist B oder mehr und D oder weniger
//j ist 0 oder mehr C.-A oder weniger und B.+i-D oder mehr und i oder weniger
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
//Einschließen(Alphabetischer Reihenfolge)
#include<algorithm>//sort,Halbierungssuche,Eine solche
#include<bitset>//Bit mit fester Länge gesetzt
#include<cmath>//pow,Protokoll usw.
#include<complex>//Komplexe Zahl
#include<deque>//Double-Ended-Zugriffswarteschlange
#include<functional>//größer sortieren
#include<iomanip>//setprecision(Gleitkomma-Ausgabefehler)
#include<iostream>//Input-Output
#include<iterator>//Betrieb einstellen(Produktset,Summensatz,Differenzsatz etc.)
#include<map>//map(Wörterbuch)
#include<numeric>//iota(Generierung einer Ganzzahlzeichenfolge),gcd und lcm(c++17)
#include<queue>//Warteschlange
#include<set>//einstellen
#include<stack>//Stapel
#include<string>//String
#include<unordered_map>//Karte mit Iterator, aber ohne Ordnung
#include<unordered_set>//Es gibt einen Iterator, aber die Reihenfolge wird nicht festgelegt
#include<utility>//pair
#include<vector>//Array mit variabler Länge
using namespace std;
typedef long long ll;
//Makro
//für Schleifenbeziehung
//Das Argument ist(Variablen in der Schleife,Bewegungsumfang)Oder(Variablen in der Schleife,Erste Nummer,Anzahl der Endungen)、のどちらOder
//Wenn es kein D gibt, wird die Schleifenvariable um 1 erhöht, und wenn es ein D gibt, wird die Schleifenvariable um 1 dekrementiert.
#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 ist ein Container wie ein Vektor
#define ALL(x) (x).begin(),(x).end() //Ich möchte Argumente wie sort weglassen
#define SIZE(x) ((ll)(x).size()) //Größe zu Größe_Wechseln Sie von t nach ll
//Konstante
#define INF 1000000000000 //10^12:Extrem großer Wert,∞
#define MOD 998244353 //10^9+7:Gemeinsames Recht
#define MAXR 100000 //10^5:Maximale Reichweite des Arrays(Wird für die Aufzählung von Primzahlen usw. verwendet.)
//Abkürzung
#define PB push_back //In Vektor einfügen
#define MP make_pair //Paarkonstruktor
#define F first //Das erste Element des Paares
#define S second //Das zweite Element des Paares
template<ll mod> class modint{
public:
ll val=0;
//Konstrukteur
modint(ll x=0){while(x<0)x+=mod;val=x%mod;}
//Konstruktor kopieren
modint(const modint &r){val=r.val;}
//Arithmetischer Operator
modint operator -(){return modint(-val);} //einstellig
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;}
//Aufgabenverwalter
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;
}
//Äquivalenzvergleichsoperator
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>;
//E / A-Stream
istream &operator >>(istream &is,mint& x){//Fügen Sie x nicht const hinzu
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 wählt i Spalten oder Zeilen aus
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;
}
Nach C Problem
Ich werde diesmal überspringen.
Recommended Posts