[PYTHON] Codeforces Round # 597 (Div. 2) Bacha Review (10/27)

This time's results

Impressions of this time

I couldn't solve D at all. It seems to be a typical problem, so I would like to reflect on it and make use of it next time.

Problem A

All you have to do is determine that $ a and b $ are relatively prime. ** Just remember the Chinese Remainder Theorem **.

A.py

from math import gcd
for _ in range(int(input())):
    a,b=map(int,input().split())
    if gcd(a,b)==1:
        print("Finite")
    else:
        print("Infinite")

B problem

If the variables $ r, p, s $ below are 0 or more, we will first fill in only the moves that can beat the opponent **. If you can win with more than half when you fill in the winning moves, you can output after deciding the remaining moves appropriately. Even if you can't win more than half, NO is output because the current choice is the best choice.

You can implement it innocently.

B.py

from collections import deque
for _ in range(int(input())):
    n=int(input())
    r,p,s=map(int,input().split())
    t=input()
    ans=["" for i in range(n)]
    w=0
    for i in range(n):
        if t[i]=="R":
            if p>0:
                ans[i]="P"
                p-=1
                w+=1
        elif t[i]=="P":
            if s>0:
                ans[i]="S"
                s-=1
                w+=1
        else:
            if r>0:
                ans[i]="R"
                r-=1
                w+=1
    if w<-(-n//2):
        print("NO")
    else:
        ansp=deque()
        for i in range(r):
            ansp.append("R")
        for i in range(p):
            ansp.append("P")
        for i in range(s):
            ansp.append("S")
        for i in range(n):
            if ans[i]=="":
                ans[i]=ansp.popleft()
        print("YES")
        print("".join(ans))

C problem

I forgot to divide by ** $ 10 ^ 9 + 7 $ ** ...

The problem of counting strings like this is ** better to count in a fixed order **. Also, at that time, you can make it DP by setting the ** state well. In other words, the following DP is set.

$ dp [i]: = $ (total number of possible strings up to the $ i $ th character (1-indexed))

Initialization should be $ dp [0] = 1, dp [1] = 1 $, and at this time, considering the transition to the $ i $ th character, it will be as follows.

(1) When the $ i $ th character is not a converted character dp[i]+=dp[i-1] (2) When the $ i $ th character is a converted character Under the condition that the $ i-1 $ and $ i $ th characters are both $ u $ or both are $ n $. dp[i]+=dp[i-2]

Considering the above two transitions, if you do not forget to divide by $ 10 ^ 9 + 7 $, the answer will come out. Also, $ w and m $ always change to ** $ uu and nn $ respectively, so if $ w $ or $ m $ is included, 0 should be output.

C.py

mod=10**9+7
s=input()
n=len(s)
dp=[0]*(n+1)
dp[0]=1
dp[1]=1
for i in range(2,n+1):
    dp[i]+=dp[i-1]
    dp[i]%=mod
    #print(s[i-2:i])
    if s[i-2:i]=="uu" or s[i-2:i]=="nn":
        dp[i]+=dp[i-2]
        dp[i]%=mod
#print(dp)
if ("w" in s)or("m" in s):
    print(0)
else:
    print(dp[n])

D problem

I think it is impossible to solve without seeing the minimum spanning tree. I only solved it once about 9 months ago, so I didn't think of it at all. However, it has been organized a lot this time, so I feel that it will be solved when it comes out next time.

** To keep costs as low as possible ** We will connect the edges between cities or build a power plant. At this time, it can be regarded as the problem of the minimum spanning tree ** because it aims to minimize the cost when connecting the edges between cities. Also, regarding the cost of building a power plant, by introducing a new vertex (** super vertex **) and considering the weighted edge between the original vertex, it can be reduced to the problem of solving the minimum spanning tree. I can.

In other words, ** you can create the top of the power plant and set the cost to the $ i $ th city as $ c \ _i $ **. In this way, the solution can be found simply by considering the minimum spanning tree at the vertex of $ n + 1 $. It also outputs information about the city where the power plant is located and the area between the connected cities, but this can be easily implemented by dividing the case when adding edges using the Kruskal method.

The discussion and implementation is good above, but I'd also like to mention that I've used ** tuple for the first time ** because I wanted to return multiple different types of values with Kruskal's method. It's very comfortable to use, so I'll continue to use it (document is here).

(✳︎)… Regarding the minimum spanning tree, I posted the library in this article.

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 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();
    }
};

//Edge structure
struct Edge{
    ll u,v,cost;
    //Put const on the back!
    bool operator<(const Edge& e) const {return this->cost<e.cost;}
};

//Kruskal method
//ret:=Sum of the minimum spanning tree weights
//n:=Total number of vertices
//Computational complexity:=O(|E|log|V|)
tuple<ll,vector<ll>,vector<pair<ll,ll>>> Kruskal(vector<Edge> &edges,ll n){
    vector<ll> f1;vector<pair<ll,ll>> f2;
    sort(ALL(edges));//Ascending order of edge weights
    UnionFind uf=UnionFind(n);
    ll ret=0;
    FORA(e,edges){
        //Do you need to add that side(Power plant or side)
        if (!uf.same(e.u,e.v)){
            uf.unite(e.u,e.v);
            ret+=e.cost;
            if(e.v==n-1){
                f1.PB(e.u+1);
            }else{
                f2.PB(MP(e.u+1,e.v+1));
            }
        }
    }
    return {ret,f1,f2};
}


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;cin>>n;
    vector<pair<ll,ll>> xy(n);REP(i,n)cin>>xy[i].F>>xy[i].S;
    vector<ll> c(n);REP(i,n)cin>>c[i];
    vector<ll> k(n);REP(i,n)cin>>k[i];
    vector<Edge> edges;
    REP(i,n){
        FOR(j,i+1,n-1){
            edges.PB({i,j,(abs(xy[i].F-xy[j].F)+abs(xy[i].S-xy[j].S))*(k[i]+k[j])});
        }
    }
    REP(i,n)edges.PB({i,n,c[i]});
    tuple<ll,vector<ll>,vector<pair<ll,ll>>> t=Kruskal(edges,n+1);
    cout<<get<0>(t)<<endl;
    cout<<SIZE(get<1>(t))<<endl;
    REP(i,SIZE(get<1>(t))){
        if(i==SIZE(get<1>(t))-1)cout<<get<1>(t)[i]<<endl;
        else cout<<get<1>(t)[i]<<" ";
    }
    cout<<SIZE(get<2>(t))<<endl;
    REP(i,SIZE(get<2>(t))){
        cout<<get<2>(t)[i].F<<" "<<get<2>(t)[i].S<<endl;
    }
}

E problem

I will skip this time.

F problem

Consider the digit DP at the same time for each of $ a and b $, and when looking at the $ i $ digit from the top, is it equal to $ l $ (①), is it greater than $ l $ and less than $ r $ (②), When I tried to think about 3 ways of equality to $ r $ (③), the implementation was ruined (because there are 27 ways of transitions of $ 3 \ times 3 \ times 3 $).

The policy was correct, but except when $ a = b = 0 $, it is $ a \ neq b $, so if you think in order from the MSB of $ r $, $ a $ is ① and ②, and $ b $ is ②. You can see that only ③ and ③ are satisfied. Therefore, the transition will be $ 2 \ times 2 \ times 3 $, which can be reduced to a sufficient amount to write down.

I will not upsolve this time, but I hope it will be solved the next time I see it. If you think about it carefully, it's just a matter of focusing more on solving it during the contest, so I regret it.