yukicoder contest 259 Review

result

スクリーンショット 2020-08-01 0.08.04.png

Impressions

A I felt that the problem was difficult and ran away. It's not difficult if you follow the basics, so I regret it. In the B problem, I made a mistake in the constant and lost time. I'm sorry ... The C problem was a kind of problem that I hadn't done much, but I solved it. I'm glad I was sticky.

Problem A

(1) The range of $ t $ depends on $ D $, and $ D $ is ** extremely large. ** It is necessary to find the ** minimum value ** $ T $ of that $ t $. (2) It holds for $ t <T $. Since there is ** monotonicity ** that holds for $ t> T $, $ T $ may be obtained by binary search because of these two conditions. Also, if the total distance traveled by each slime in a certain $ t $ is calculated by $ O (N) $, the amount of calculation will be $ O (N \ log {D}) $, so if you can write a program in time. I thought.

Now consider the total distance traveled by all slimes in $ t $, but when the two slimes (speeds are $ v_1 $, $ v_2 $) are combined into one slime, the speed of the remaining slime The result is $ v_1 + v_2 $. Therefore, ** pay attention to the total distance traveled **, even if each slime does not coalesce, it does not change, so considering how far all slimes travel up to $ t $ (when not coalescing), $ O It can be calculated by (N) $.

Also, please refer to this article for binary search. In addition, this problem can be solved with $ O (N) $ instead of $ O (N \ log {D}) $ (Main Solution editorial)).

A.py


n,d=map(int,input().split())
x=list(map(int,input().split()))
v=list(map(int,input().split()))
s=sum(v)

def f(k):
    return s*k

#l is false,r is true
l,r=0,1000000000000
while l+1<r:
    k=l+(r-l)//2
    if f(k)>=d:
        r=k
    else:
        l=k
print(r)

Problem B

First, since the ** primality test is performed by the query, all the prime numbers that can be judged by the Eratosthenes sieve ** are checked (this makes the query primality test $ O (1) $). Here, if it is determined that $ p $ is not a prime number, $ -1 $ can be output, so the discussion below assumes that $ p $ is a prime number.

Under this, if you simply ask for $ A ^ {P!} \ (Mod \ P) $ as $ ((A ^ 1) ^ 2) ^ 3… $, it will not be in time even under the condition of $ mod \ P $. Hmm. What should be remembered here is ** Fermat's Little Theorem **. I think you should keep in mind that it is common sense in problems related to the power of $ remainder $. In this theorem, ** $ A ^ {p-1} = 1 \ (mod \ p) $ ** holds for $ A $, which is not a multiple of $ p $ for the prime number $ p $. Here, $ A ^ {p!} = (A ^ {p-1}) ^ x \ (x = 1,2,…, p-2, p) $ holds, so ($ \ because \ p $ is $ 2 $ or more than a prime number), $ A ^ {p!} = 0 \ (mod \ P) $ if $ A $ is a multiple of $ p $, $ A ^ {p!} = 1 \ otherwise It will be (mod \ P) $.

To summarize the above, $ -1 $ when $ p $ is not a prime number, $ 0 $ when $ p $ is a prime number and $ A % p = 0 $, and $ A % p \ when $ p $ is a prime number. When neq is 0 $, $ 1 $ should be output.

** I forgot to change the range of MAXRR in the code and issued WA **. It was painful. This took a lot of time.

B.cc


//Compiler optimization
#pragma GCC optimize("Ofast")
//Include etc.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//macro
//for loop
//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.
//FORA is a range for statement(If it's hard to use, erase it)
#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 is a container such as 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:Congruence law
#define MAXR 6000000 //10^5:The largest range in the array
//Abbreviation
#define PB push_back //Insert
#define MP make_pair //pair constructor
#define F first //The first element of pair
#define S second //The second element of pair

#define PN true //Prime number
#define NPN false //Not a prime number
//Non-essence
#define MAXRR 3000 //√ Set a number greater than or equal to MAXR

//Assume that integers up to MAXR are prime numbers(Shave from here)
vector<bool> PN_chk(MAXR+1,PN);//0index corresponds to the i-th integer i(0~MAXR)
//Prepare an array to store prime numbers
vector<ll> PNs;

void se(){
    //0 and 1 are not prime numbers
    PN_chk[0]=NPN;PN_chk[1]=NPN;

    FOR(i,2,MAXRR){
        //A prime number if it is assumed to be a prime number when you arrive
        if(PN_chk[i]) FOR(j,i,ll(MAXR/i)){PN_chk[j*i]=NPN;}
    }
    FOR(i,2,MAXR){
        if(PN_chk[i]) PNs.PB(i);
    }
}

ll modpow(ll a,ll n,ll p){
    if(n==0)return 1;
    ll t=modpow(a,n/2,p);
    t=t*t%p;
    if(n&1)t=t*a%p;
    return t;
}

signed main(){
    //Code for speeding up input
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    se();
    ll t;cin>>t;
    REP(_,t){
        ll a,p;cin>>a>>p;
        if(!PN_chk[p]){
            cout<<-1<<endl;
            continue;
        }
        if(a%p==0){
            cout<<0<<endl;
            continue;
        }
        cout<<1<<endl;
    }
}

C problem

If I knew the similar subject, I could do my best to implement it, so I felt the power of devotion.

First, if you put $ r_i and c_i $ as shown below, you can divide them into the four parts shown in the figure below.

IMG_0509 2.JPG

Based on this, we can see that the answer to be obtained is to find the product of the products of the numbers contained in each of the rectangles ①, ②, ③, and ④. For the part included in such a rectangle, query processing can be performed with $ O (1) $ by pre-calculating with ** two-dimensional accumulation **.

In creating a table by pre-calculation, ** in the case of two-dimensional cumulative sum ** is as follows. Also, each cell is $ a [x] [y] $, and the following are all 0-indexed.

$ s [x] [y]: = [0, x) × [0, y) The sum of the rectangular intervals of $ s[x+1][y+1] = s[x][y+1] + s[x+1][y] - s[x][y] + a[x][y]

Therefore, in the case of ** two-dimensional cumulative product **, if you do the same, it will be as follows.

$ s [x] [y]: = [0, x) × [0, y) The product of the rectangular intervals of $ s[x+1][y+1] = s[x][y+1] \times s[x+1][y] \div s[x][y] \times a[x][y]

Therefore, this ** two-dimensional cumulative product can be defined in four directions **, and the remaining three rectangular intervals are as follows. The expression of the interval is different from the definition of mathematics, but I hope you can understand the atmosphere. (I was trying to do it in an atmosphere without describing the following. ** I will thoroughly describe the policy **.)

$ s [x] [y]: = [w-1, x) × [0, y) The product of the rectangular intervals of $ s[x-1][y+1] = s[x][y+1] \times s[x-1][y] \div s[x][y] \times a[x][y]

$ s [x] [y]: = [0, x) × [h-1, y) The product of the rectangular intervals of $ s[x+1][y-1] = s[x][y-1] \times s[x+1][y] \div s[x][y] \times a[x][y]

$ s [x] [y]: = [w-1, x) × [h-1, y) The product of the rectangular intervals of $ s[x+1][y+1] = s[x][y+1] \times s[x+1][y] \div s[x][y] \times a[x][y]

If you can implement this, you can write a program by ** noting that it is an open interval **. Also, I used my modint library because I only need to find the remainder divided by $ 10 ^ 9 + 7 $.

Postscript (8/2)

Dividing by zero is troublesome if you divide the filled part from the whole, so it seems better to be aware that ** the problem of finding the product of multiple numbers is expressed only by the product **.

C.cc


//Compiler optimization
#pragma GCC optimize("Ofast")
//Include etc.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//macro
//for loop
//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.
//FORA is a range for statement(If it's hard to use, erase it)
#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 is a container such as 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:Congruence law
#define MAXR 100000 //10^5:The largest range in the array
//Abbreviation
#define PB push_back //Insert
#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;
}

//Exponentiation
mint modpow(const mint &a,ll n){
    if(n==0)return 1;
    mint t=modpow(a,n/2);
    t=t*t;
    if(n&1)t=t*a;
    return t;
}



signed main(){
    //Code for speeding up input
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll h,w;cin>>h>>w;
    vector<vector<ll>> A(h,vector<ll>(w,0));
    REP(i,h)REP(j,w)cin>>A[i][j];
    vector<vector<vector<mint>>> s(4,vector<vector<mint>>(h+1,vector<mint>(w+1,1)));
    REP(j,h){
        REP(k,w){
            ll x,y;
            x=j;y=k;
            s[0][x+1][y+1]=s[0][x+1][y]*s[0][x][y+1]/s[0][x][y]*A[x][y];
        }
    }
    REP(j,h){
        REP(k,w-1){
            ll x,y;
            x=j;y=w-1-k;
            s[1][x+1][y-1]=s[1][x+1][y]*s[1][x][y-1]/s[1][x][y]*A[x][y];
        }
    }
    REP(j,h-1){
        REP(k,w){
            ll x,y;
            x=h-1-j;y=k;
            s[2][x-1][y+1]=s[2][x-1][y]*s[2][x][y+1]/s[2][x][y]*A[x][y];
        }
    }
    REP(j,h-1){
        REP(k,w-1){
            ll x,y;
            x=h-1-j;y=w-1-k;
            s[3][x-1][y-1]=s[3][x-1][y]*s[3][x][y-1]/s[3][x][y]*A[x][y];
        }
    }
    #if 0
    REP(i,4){
        REP(j,h){
            REP(k,w){
                cout<<s[i][j][k]<<" ";
            }
            cout<<endl;
        }
        cout<<endl;
    }
    #endif
    ll q;cin>>q;
    REP(_,q){
        ll r,c;cin>>r>>c;
        mint ans=1;
        ll x,y;
        x=r-1;y=c-1;
        ans*=s[0][x][y];
        //x=r;y=w-c;
        ans*=s[1][x][y];
        //x=h-r;y=c;
        ans*=s[2][x][y];
        //x=h-r;y=w-c;
        ans*=s[3][x][y];
        cout<<ans<<endl;
    }
}

Recommended Posts

yukicoder contest 259 Review
yukicoder contest 264 Review
yukicoder contest 261 Review
yukicoder contest 267 Review
yukicoder contest 266 Review
yukicoder contest 263 Review
yukicoder contest 268 Review
AtCoder Beginner Contest 152 Review
AtCoder Grand Contest 041 Review
yukicoder contest 265 Participation record
AtCoder Regular Contest 105 Review
yukicoder contest 266 Participation record
yukicoder contest 263 Participation record
yukicoder contest 243 Participation record
yukicoder contest 256 entry record
yukicoder contest 273 Participation record
Keyence Programming Contest 2020 Review
AtCoder Beginner Contest 160 Review
AtCoder Beginner Contest 178 Review
AtCoder Beginner Contest 166 Review
AtCoder Beginner Contest 167 Review
yukicoder contest 252 Participation record
yukicoder contest 259 Participation record
AtCoder Beginner Contest 164 Review
yukicoder contest 249 Participation record
AtCoder Beginner Contest 169 Review
yukicoder contest 271 Participation record
AtCoder Grand Contest 048 Review
yukicoder contest 267 entry record
AtCoder Beginner Contest 181 Review
yukicoder contest 251 Participation record
AtCoder Beginner Contest 171 Review
AtCoder Beginner Contest 182 Review
yukicoder contest 242 Participation record
AtCoder Beginner Contest 180 Review
yukicoder contest 241 Participation record
yukicoder contest 277 Participation record
AtCoder Beginner Contest 177 Review
yukicoder contest 264 entry record
AtCoder Beginner Contest 168 Review
AtCoder Grand Contest 045 Review
NOMURA Programming Contest 2020 Review
AtCoder Grand Contest 044 Review
yukicoder contest 245 entry record
yukicoder contest 257 Participation record
yukicoder contest 250 entry record
yukicoder contest 254 Participation record
AtCoder Beginner Contest 179 Review
AtCoder Beginner Contest 172 Review
AtCoder Regular Contest 106 Review
yukicoder contest 246 Participation record
yukicoder contest 275 Participation record
yukicoder contest 274 Participation record
AtCoder Beginner Contest 176 Review
yukicoder contest 247 Participation record
AtCoder Grand Contest 046 Review
AtCoder Beginner Contest 175 Review
HHKB Programming Contest 2020 Review
AtCoder Beginner Contest 174 Review
AtCoder Beginner Contest 153 Review
AtCoder Beginner Contest 156 Review