AtCoder Grand Contest 046 Review

This time's results

スクリーンショット 2020-06-24 13.06.37.png

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.

IMG_0424.JPG

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.)

IMG_0425.JPG

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.

IMG_0426.JPG

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

AtCoder Grand Contest 041 Review
AtCoder Grand Contest 048 Review
AtCoder Grand Contest 045 Review
AtCoder Grand Contest 044 Review
AtCoder Grand Contest 046 Review
AtCoder Beginner Contest 152 Review
AtCoder Regular Contest 105 Review
AtCoder Beginner Contest 160 Review
AtCoder Beginner Contest 178 Review
AtCoder Beginner Contest 166 Review
AtCoder Beginner Contest 167 Review
AtCoder Beginner Contest 169 Review
AtCoder Beginner Contest 181 Review
AtCoder Beginner Contest 171 Review
AtCoder Beginner Contest 182 Review
AtCoder Beginner Contest 180 Review
AtCoder Beginner Contest 177 Review
AtCoder Beginner Contest 168 Review
AtCoder Beginner Contest 179 Review
AtCoder Beginner Contest 172 Review
AtCoder Beginner Contest 176 Review
AtCoder Beginner Contest 175 Review
AtCoder Beginner Contest 174 Review
AtCoder Beginner Contest 153 Review
AtCoder Beginner Contest 156 Review
AtCoder Beginner Contest 161 Review
AtCoder Beginner Contest 170 Review
AtCoder Regular Contest 104 Review
AtCoder Beginner Contest 165 Review
AtCoder Beginner Contest 173 Review
AtCoder Beginner Contest 155 Review
AtCoder Beginner Contest 162 Review
AtCoder Grand Contest 041 Participation Report
AtCoder Grand Contest 040 Participation Report
AtCoder Grand Contest 047 Participation Report
AtCoder Grand Contest Past Question Challenge 2
AtCoder Grand Contest Past Question Challenge 1
AtCoder Beginner Contest 066 Review past questions
AtCoder Beginner Contest 177
yukicoder contest 259 Review
yukicoder contest 264 Review
AtCoder Beginner Contest 179
AtCoder Beginner Contest 172
AtCoder Beginner Contest 180
yukicoder contest 261 Review
yukicoder contest 267 Review
AtCoder Beginner Contest 173
Atcoder Beginner Contest 153
yukicoder contest 263 Review
yukicoder contest 268 Review
AtCoder Beginner Contest 102 Review of past questions
AtCoder Beginner Contest 072 Review of past questions
AtCoder Beginner Contest 085 Review of past questions
AtCoder Beginner Contest 062 Review of past questions
AtCoder Beginner Contest 051 Review of past questions
AtCoder Beginner Contest 127 Review of past questions
AtCoder Beginner Contest 119 Review of past questions
AtCoder Beginner Contest 151 Review of past questions
AtCoder Beginner Contest 075 Review of past questions
AtCoder Beginner Contest 110 Review of past questions
AtCoder Beginner Contest 117 Review of past questions