[PYTHON] AtCoder Regular Contest 106 Review

This time's results

Impressions of this time

I didn't have enough time to solve D ... (I passed about 10 minutes later). ** I spent too much time without noticing the part I missed due to the C problem ...

It's a shame, but I think it's the first time I've worked on a blue diff (almost yellow diff) during the contest, so I'll take this as a good sign and work harder. (Domino Quality ...)

Problem A

Since there is room in TL, I will search all appropriately. Neither A nor B is a very large number.

It might be a little more interesting if the query requires repeated decisions.

A.py

n=int(input())
x3,x5=[3],[5]
while True:
    if x3[-1]*3<n:
        x3.append(x3[-1]*3)
    else:
        break
while True:
    if x5[-1]*5<n:
        x5.append(x5[-1]*5)
    else:
        break
x3,x5=[i for i in x3 if i<n],[i for i in x5 if i<n]
y3,y5=set(x3),set(x5)
#print(y3,y5)
for i in y3:
    if n-i in y5:
        a,b=i,n-i
        ans1,ans2=0,0
        while a!=1:
            a//=3
            ans1+=1
        while b!=1:
            b//=5
            ans2+=1
        print(ans1,ans2)
        exit()
print(-1)

B problem

Since it is not required to minimize the number of operations, I thought it would be good if the sum of $ a \ _i, b \ _i $ of any vertex was equal **, but ** the graph is unconcatenated. I noticed when.

In any case, the value of $ a $ can be adjusted well between connected vertices, so ** the sum of $ a \ _i, b \ _i $ of the vertices contained in each connected component is equal **. Is a condition. It's not difficult to implement with UnionFind.

B.cc

//Debugging options:-fsanitize=undefined,address

//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 endings)、のどちら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

//Below, the disjoint sets and the tree represent the same thing.
class UnionFind{
public:
    vector<ll> parent; //parent[i]Is the parent of i
    vector<ll> siz; //An array representing the size of the disjoint sets(Initialize with 1)
    map<ll,vector<ll>> group; //Manage by set(key:Set representative element, value:Array of elements of the set)
    ll n; //Element count

    //constructor
    UnionFind(ll n_):n(n_),parent(n_),siz(n_,1){ 
        //Initialize as the root of all elements is itself
        for(ll i=0;i<n;i++){parent[i]=i;}
    }

    //Get the root of the tree to which the data x belongs(Also performs path compression)
    ll root(ll x){
        if(parent[x]==x) return x;
        return parent[x]=root(parent[x]);//Since the value of the assignment expression is the value of the assigned variable, the route can be compressed.
    }

    //Merge x and y trees
    void unite(ll x,ll y){
        ll rx=root(x);//root of x
        ll ry=root(y);//root of y
        if(rx==ry) return;//When in the same tree
        //Merge small set into large set(Merged from ry to rx)
        if(siz[rx]<siz[ry]) swap(rx,ry);
        siz[rx]+=siz[ry];
        parent[ry]=rx;//When x and y are not in the same tree, attach y root ry to x root rx
    }

    //Determine if the tree to which x and y belong is the same
    bool same(ll x,ll y){
        ll rx=root(x);
        ll ry=root(y);
        return rx==ry;
    }

    //Get the size of the disjoint sets of x
    ll size(ll x){
        return siz[root(x)];
    }

    //Group each disjoint set
    void grouping(){
        //Perform path compression first
        REP(i,n)root(i);
        //Manage with map(Use default build)
        REP(i,n)group[parent[i]].PB(i);
    }

    //Delete the disjoint sets and initialize
    void clear(){
        REP(i,n){parent[i]=i;}
        siz=vector<ll>(n,1);
        group.clear();
    }
};

signed main(){
    //Output specification of decimal digits
    //cout<<fixed<<setprecision(10);
    //Code for speeding up input
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n,m;cin>>n>>m;
    vector<ll> a(n);REP(i,n)cin>>a[i];
    vector<ll> b(n);REP(i,n)cin>>b[i];
    UnionFind uf(n);
    REP(i,m){
        ll c,d;cin>>c>>d;
        uf.unite(c-1,d-1);
    }
    uf.grouping();
    FORA(i,uf.group){
        ll s=0;
        FORA(j,i.S){
            s+=(a[j]-b[j]);
        }
        if(s!=0){
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;
}

C problem

The construction that satisfies the case is completed immediately (about 15 minutes), but I wasted time by completely missing the sentence ** of the problem sentence, which outputs -1 if it does not hold **. I did.

First, ** check the conditions if it does not hold **. Here, the two subjects are solving the interval scheduling problem, and the former is solved correctly, so the maximum number of intervals can be selected. Therefore, $ M \ geqq 0 $ always holds, and if $ M \ <0 $, -1 is output.

Therefore, from now on, we will consider the construction when $ M \ geqq 0 $. As anyone who has solved the interval scheduling problem knows, when choosing in ascending order of $ L \ _i $, select in ascending order of $ R \ _i $ with the pattern of the longest interval of $ L \ _i $. You can only choose the number of sections that are clearly smaller than in the case. The figure below is shown.

In the above figure, it is assumed that the minimum $ L \ _i $ mentioned earlier and the long interval includes $ l $ intervals. At this time, the former can select $ n-1 $ sections, and the latter can select only $ n-l $ sections. Therefore, at this time, $ m = l-1 $. Also, it becomes $ 0 \ leqq l \ leqq n-1 $, but when $ l = 0 $, $ m = 0 $, so $ 1 \ leqq l \ leqq n-1 \ leftrightarrow 0 \ leqq m \ leqq n- When it's 2 $, you can build it. Also, when $ m = n-1, n $, construction is not possible, but since both can select one or more sections, $ m = n $ does not hold, and $ m = n- When it is 1 $, Takahashi-kun selects $ n $ sections and Aoki-kun selects $ 1 $ sections, but when Takahashi-kun selects $ n $ sections, none of the sections overlap. So Aoki can also choose $ n $ sections.

Also note that the above does not take into account the case of $ n = 1, m = 0 $. This can be done by simply arranging the non-overlapping sections when $ m = 0 $, so it can be avoided by dividing $ m = 0 $ first.

I don't think it's that difficult to implement just by implementing the above figure as it is.

C.py

n,m=map(int,input().split())
if n==1 and m==0:
    print(1,2)
    exit()
if m==n or m==n-1 or m<0:
    print(-1)
    exit()
ans=[[1,10**7]]
for i in range(m+1):
    ans.append([2*(i+1),2*(i+1)+1])
for i in range(n-m-2):
    ans.append([10**7+2*(i+1),10**7+2*(i+1)+1])
#print(ans)
for i in ans:
    print(i[0],i[1])

D problem

I felt that the D problem was easier because it wasn't that difficult just to do the formula transformation. During the contest, it seemed to be under pressure, but I couldn't come up with it and implement it in the remaining 20 minutes.

First of all, I thought about ** paying attention to the contribution of each $ A \ _i $ because it is just a polynomial in the problem of summation. Then, you want to expand ** $ (A \ _ L + A \ _R) ^ x $ **, so if you expand it by the binomial theorem, it will be as follows.

(A\_L+A\_ R)^x=\_xC\_0 A\_L^x+\_xC\_1 A\_L^{x-1} A\_R+…+\_xC\_x A\_R^x

Here, considering the contribution of a certain $ A \ _i $, ** $ A \ _i $ is a pair of $ (A \ _L, A \ _R) $ with all numbers other than itself **, so above Using the formula, each term expanded by the binomial theorem is as follows. (✳︎)

\_xC\_0:A\_i^{x}(A\_1^0+…+A\_{i-1}^0+A\_{i+1}^0+…+A\_{n}^0) \_xC\_1:A\_i^{x-1}(A\_1^1+…+A\_{i-1}^1+A\_{i+1}^1+…+A\_{n}^1) ↓ \_xC\_{x-1}:A\_i^{1}(A\_1^{x-1}+…+A\_{i-1}^{x-1}+A\_{i+1}^{x-1}+…+A\_{n}^{x-1}) \_xC\_{x}:A\_i^{0}(A\_1^{x}+…+A\_{i-1}^{x}+A\_{i+1}^{x}+…+A\_{n}^{x})

Also, if implemented as it is, even if $ \ _xC \ _i $ is calculated in advance, there are $ k $ candidates for $ x $, $ n $ candidates for $ A \ _i $, and each of the above two. The term coefficient is $ x + 1 $, and the calculation in $ () $ is $ n $ times. Therefore, let's think about ** further summarizing the formulas ** on the premise that some ** pre-calculations **.

That is, consider ** summing each binomial coefficient $ \ _xC \ _i $ for any $ A \ _i $ **. Then, it will be as shown in the figure below.

Therefore, if this sum is put together, $ (A \ _1 ^ {xi} + A \ _2 ^ {xi} +… + A \ _n ^ {xi}) \ times (A \ _1 ^ {i} + A \ _2 ^ {i} +… + A \ _n ^ {i})-(A \ _1 ^ {x} + A \ _2 ^ {x} +… + A \ _n ^ {x}) $ (** symmetry I think it's natural ** from the point of view of sex).

Therefore, not only the pre-calculation of the binomial coefficient is performed, but also the pre-calculation of $ y [i]: = (A \ _1 ^ i + A \ _2 ^ i +… + A \ _n ^ i) $ is $ i = 0. If you do it with $ ~ $ k $ ($ O (nk) $), you can find the sum of $ \ _xC \ _i $ with $ O (1) $. Therefore, the total complexity is $ O (k ^ 2) $ to find the answer for each $ x $.

From the above, the total amount of calculation is $ O (n + nk + k ^ 2) = O (k (k + n)) $, which is sufficiently fast.

(✳︎)… From here on, we are considering the condition of $ 1 \ leqq L, R \ leqq N, L \ neq R $ instead of $ 1 \ leqq L \ leqq n-1, L + 1 \ leqq R \ leqq n $. However, ** it is enough to halve the final answer rather than symmetry **.

D.cc

//Debugging options:-fsanitize=undefined,address

//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 endings)、のどちら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 998244353 //10^9+7:Congruence law
#define MAXR 1000 //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;
}

//Calculation of binomial coefficient
mint fac[MAXR+1],finv[MAXR+1],inv[MAXR+1];
//Creating a table
void COMinit() {
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    FOR(i,2,MAXR){
        fac[i]=fac[i-1]*mint(i);
        inv[i]=-inv[MOD%i]*mint(MOD/i);
        finv[i]=finv[i-1]*inv[i];
    }
}
//Calculation part
mint COM(ll n,ll k){
    if(n<k)return 0;
    if(n<0 || k<0)return 0;
    return fac[n]*finv[k]*finv[n-k];
}

signed main(){
    //Output specification of decimal digits
    //cout<<fixed<<setprecision(10);
    //Code for speeding up input
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    COMinit();
    ll n,k;cin>>n>>k;
    vector<ll> a(n);REP(i,n)cin>>a[i];
    //po
    vector<vector<mint>> po(n,vector<mint>(k+1,0));
    REP(i,n){
        po[i][0]=1;
        REP(j,k){
            po[i][j+1]=po[i][j]*a[i];
        }
    }
    vector<mint> y(k+1,0);
    REP(i,k+1){
        REP(j,n){
            y[i]+=po[j][i];
        }
    }
    vector<mint> ans(k,0);
    FOR(x,1,k){
        mint ans_sub=0;
        REP(j,x+1){
            ans_sub+=(COM(x,j)*((y[x-j])*(y[j])-y[x]));
        }
        ans[x-1]+=ans_sub;
    }
    REP(i,k){
        cout<<ans[i]/2<<endl;
    }
}

After the E problem