[PYTHON] AtCoder Grand Contest 046 Review
This time's results
Impressions of this time
A The problem was unexpectedly easy and surprising. As a result, I should have followed my own solution for problem B, so I think that if I can gain confidence in the problems of water diff and blue diff, I will be able to AC.
Problem A
I'm glad that the speed was solved reasonably well.
As shown in the figure below, if the starting point is the origin O of the complex plane, the argument is $ + x $. Also, since it is clear that they are always on the same circumference after the operation, it is sufficient if the declination is equal to the start of the operation, and after $ k $ of operation, it goes around $ l $ and sometimes reaches the origin O. Think of the smallest of them.
Therefore, $ kx = 360 l \ leftrightarrow k = \ frac {360l} {x} $ holds. Here, since $ k $ is an integer, $ 360l $ is a multiple of $ x $ and $ 360 $, and the least common multiple can be considered. From the above, the answer is the least common multiple of $ 360 $ and $ x $ divided by $ 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
I was impatient and solved it because I was worried that I couldn't solve it ...
First, I misread various things and tried to find a pattern that was convenient for me. Misreading is not good, but I think it's not a bad policy to look for a convenient pattern first. Here, ** in order, you should think directly about how to apply ** regardless of the actual order. ** Isn't it better to classify cases according to whether the rows or columns are painted **? I thought, but as a result of consideration, I found it difficult. ↑ You can't use it here for about 30 minutes ...
From the above policy, we moved on to the policy based on dynamic programming. I moved to this policy ** because I only need to add rows or columns, so I only have to manage the state ** and ** transitions are only (D + C)-(B + A) times ** Is the reason.
Here, the array of DP should be ** dp [i] [x, y] = (total number of paintings so that the row becomes x and the column becomes y in i operations) **. I think it's obvious. Also, the ** DP transition depends on whether you want to add a row or a column **. In the former case, dp [i] [x, y] → dp [i + 1] [x + 1, y], and in the latter case, dp [i] [x, y] → dp [i + 1] [x , Y + 1].
At this time, since there is a way to paint the pattern to be applied at the time of transition, dp [i + 1] from dp [i + 1] [x, y + 1] and dp [i + 1] [x + 1, y] +2] Consider the transition to [x + 1, y + 1] in the figure below. (** I was trying to fit the sample using symmetry without carefully considering this pattern **. I will reflect on it and make use of it next time.)
Here, since it can be seen from the above figure that the pattern to be covered occurs in the $ x + 1 $ row and the $ y + 1 $ column, consider the ** common part $ x \ times y $ matrix **. I thought that I could proceed with the consideration.
Furthermore, when transitioning from the $ (x + 1) \ times y $ matrix and the $ x \ times (y + 1) $ matrix to the $ (x + 1) \ times (y + 1) $ matrix The pattern that suffers from is the $ (x + 1) \ times y $ matrix and $ x \ times when generating the $ (x + 1) \ times (y + 1) $ matrix from the $ x \ times y $ matrix. It can be rephrased as a pattern that can be created via either of the (y + 1) $ matrices, and the pattern is as shown in the figure below.
Therefore, you can erase the covered part in the above figure, but "If $ x + 1 $ becomes A and $ y + 1 $ becomes B, no cover will occur" and "$ x + 1" If $ exceeds C and $ y + 1 $ exceeds D, it does not exist. ”If you implement it carefully, it will be the second code.
In the second code, map is used in the container that stores the result of dp, and ** it takes logarithmic hours to access, so it is just barely computationally expensive **. Here, you can speed up about 5 to 10 times by using a normal array without using map, and the definition of the container element that stores dp changes as follows.
** dp [i] [x, y] = (total number of paintings where the row is x and the column is y in i operations) ** ↓ ** dp [i] [j] = (total number of paintings when the number of lines is increased by j in i operations) **
Therefore, x = j + A and y = i-j + B, and if you implement it paying attention to the index, you can have the same discussion as before, which is the first code.
B_AC.cc
//Include(Alphabetical order)
#include<algorithm>//sort,Binary search,Such
#include<bitset>//Fixed length bit set
#include<cmath>//pow,log etc.
#include<complex>//Complex number
#include<deque>//Queue for double-ended access
#include<functional>//sort greater
#include<iomanip>//setprecision(Floating point output error)
#include<iostream>//Input / output
#include<iterator>//Set arithmetic(Intersection,Union,Difference set, etc.)
#include<map>//map(dictionary)
#include<numeric>//iota(Generation of integer sequence),gcd and lcm(c++17)
#include<queue>//queue
#include<set>//set
#include<stack>//stack
#include<string>//String
#include<unordered_map>//Map with iterator but not keeping order
#include<unordered_set>//Set with iterator but not keeping order
#include<utility>//pair
#include<vector>//Variable length array
using namespace std;
typedef long long ll;
//macro
//for loop relationship
//The argument is(Variables in the loop,Range of movement)Or(Variables in the loop,First number,Number of ends)、のどちらOr
//If there is no D, the loop variable is incremented by 1, and if it is with D, the loop variable is decremented by 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 is a container such as vector
#define ALL(x) (x).begin(),(x).end() //I want to omit arguments such as sort
#define SIZE(x) ((ll)(x).size()) //size to size_Change from t to ll
//constant
#define INF 1000000000000 //10^12:Extremely large value,∞
#define MOD 998244353 //10^9+7:Congruence law
#define MAXR 100000 //10^5:The largest range in the array(Used for prime number enumeration etc.)
//Abbreviation
#define PB push_back //Insert into vector
#define MP make_pair //pair constructor
#define F first //The first element of pair
#define S second //The second element of pair
template<ll mod> class modint{
public:
ll val=0;
//constructor
modint(ll x=0){while(x<0)x+=mod;val=x%mod;}
//Copy constructor
modint(const modint &r){val=r.val;}
//Arithmetic operator
modint operator -(){return modint(-val);} //unary
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;}
//Assignment operator
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;
}
//Equivalence comparison operator
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>;
//I / O stream
istream &operator >>(istream &is,mint& x){//Do not add const to 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 selects i columns or rows
//a=When A corresponds to array index 0
//dp[i][j]As the sum of the elements is A+B+i,The sum of the elements of a is j+A,The sum of the elements of b is B+i-j
//j+A is A or more and C or less,B+i-j is B or more and D or less
//j is 0 or more C-A or less and B+i-D or more and i or less
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
//Include(Alphabetical order)
#include<algorithm>//sort,Binary search,Such
#include<bitset>//Fixed length bit set
#include<cmath>//pow,log etc.
#include<complex>//Complex number
#include<deque>//Queue for double-ended access
#include<functional>//sort greater
#include<iomanip>//setprecision(Floating point output error)
#include<iostream>//Input / output
#include<iterator>//Set arithmetic(Intersection,Union,Difference set, etc.)
#include<map>//map(dictionary)
#include<numeric>//iota(Generation of integer sequence),gcd and lcm(c++17)
#include<queue>//queue
#include<set>//set
#include<stack>//stack
#include<string>//String
#include<unordered_map>//Map with iterator but not keeping order
#include<unordered_set>//Set with iterator but not keeping order
#include<utility>//pair
#include<vector>//Variable length array
using namespace std;
typedef long long ll;
//macro
//for loop relationship
//The argument is(Variables in the loop,Range of movement)Or(Variables in the loop,First number,Number of ends)、のどちらOr
//If there is no D, the loop variable is incremented by 1, and if it is with D, the loop variable is decremented by 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 is a container such as vector
#define ALL(x) (x).begin(),(x).end() //I want to omit arguments such as sort
#define SIZE(x) ((ll)(x).size()) //size to size_Change from t to ll
//constant
#define INF 1000000000000 //10^12:Extremely large value,∞
#define MOD 998244353 //10^9+7:Congruence law
#define MAXR 100000 //10^5:The largest range in the array(Used for prime number enumeration etc.)
//Abbreviation
#define PB push_back //Insert into vector
#define MP make_pair //pair constructor
#define F first //The first element of pair
#define S second //The second element of pair
template<ll mod> class modint{
public:
ll val=0;
//constructor
modint(ll x=0){while(x<0)x+=mod;val=x%mod;}
//Copy constructor
modint(const modint &r){val=r.val;}
//Arithmetic operator
modint operator -(){return modint(-val);} //unary
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;}
//Assignment operator
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;
}
//Equivalence comparison operator
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>;
//I / O stream
istream &operator >>(istream &is,mint& x){//Do not add const to 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 selects i columns or rows
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;
}
After C problem
I will skip this time.
Recommended Posts