[PYTHON] Competitive professional devotion diary 18th to 19th days (7/12 to 7/13)

<!-Competitive professional devotion template->

Impressions

I will do my best with the regret of the ABC class contest on Saturday. I also hope to organize some libraries this week.

Day 18

ABC138-E Strings of Impurity

Time taken

10 minutes for consideration, 10 minutes for implementation

Consideration

Since the consideration was neatly summarized, the implementation was completed smoothly. In the following, the $ i $ character of $ t $ is referred to as $ t_i $, and the $ i $ character of $ s $ is referred to as $ s_i $.

First, you can make $ t $ if it consists only of the characters contained in $ s $, so that each character of $ t $ appears in $ s \ ^ {'} $ as soon as possible ** I will greedily choose **. Now consider which $ s_k $ corresponds to $ t_ {i + 1} $ as ** $ s_j $ is chosen as ** $ t_i $.

When $ t_ {i + 1} = s_k (k> j) $ holds, you can select $ s_k $ ** (✳︎), which is the minimum $ k $, as $ t_ {i + 1} $. However, when $ t_ {i + 1} = s_k (k> j) $ does not hold, ** $ s_k $, which is the smallest $ k $ among the next $ s $, is $ t_ {i You can choose it as +1} $. You can get the correct answer by repeating this for any $ t_i $.

In the above, we need to be able to quickly find the index of the alphabet that appears in $ s $, so save in an array (in ascending order) which index exists for each alphabet. If you save it in an ascending array, you can find the minimum $ k (> j) $ in (✳︎) with bisect_right. Also, when you look at the last character, the case is a little different, so you need to be a little careful in the implementation (see the code for details).

from bisect import bisect_right
s=input()
t=input()
ns=len(s)
nt=len(t)
alp=[[] for i in range(26)]
for i in range(ns):
    alp[ord(s[i])-97].append(i)
alpl=[len(alp[i]) for i in range(26)]
ans=0
now=-1
for i in range(nt):
    if alpl[ord(t[i])-97]==0:
        exit(print(-1))
    b=bisect_right(alp[ord(t[i])-97],now)
    if b==alpl[ord(t[i])-97]:
        now=alp[ord(t[i])-97][0]
        ans+=ns
        if i==nt-1:
            ans+=(now+1)
    else:
        now=alp[ord(t[i])-97][b]
        if i==nt-1:
            ans+=(now+1)
print(ans)

ABC139-E League

Time taken

Only one TLE over 30 minutes → Debug for 1 hour or more to speed up constant times

Cause of mistake

The cause was that I misunderstood that $ O (n ^ 3) $ under the maximum $ n = 1000 $ would pass. → Do not neglect to check the amount of calculation

Consideration

As the cause is, I neglected to check the amount of calculation and melted the time infinitely ... As a result, I regret that I only had to remove the unnecessary calculation from the straightforward solution of $ O (N ^ 3) $.

First of all, since there is a ** limit on the order **, I think that it may be possible to decide honestly (playing in order from the person who can play), and there is a better case than ** deciding honestly. There is no **, so this policy is correct.

Considering the people who can play against each other using a sample case, if you save the people who will play against each other as a pair as shown below, you can decide the people who will play against each other in order.

Here, if you save the battleable combinations on the $ i $ day in the dictionary d, the combination with ** value of 2 is battleable **, so next to each person included in that battleable combination If you repeat storing the opponents (the ones you are currently competing in b) in a new dictionary as a pair, the minimum date you can find when you finish watching all the matches. It will be the number of days.

Also, if there is no combination with a value of 2 on a certain day, -1 is output because it is the same value as there is no combination of matches that satisfies the conditions.

Furthermore, if you delete the combination with value 2 from d and add the next pair of opponents to d at the same time as checking the combination with value 2, in the ** for statement The iterator will be broken by deleting and adding elements with **, so ** do it after all the checks are completed **.

By the way, with this policy, it will be $ O (N ^ 3) $, but the combination where the value is 2 on the ** $ i + 1 $ day can only be the updated value on the $ i $ day. Hmm**. Therefore, if you look only at the person changeable1 updated on the $ i $ day without looking at all the combinations contained in the d on the $ i + 1 $ day, all matches $ \ frac {N (N-) All you have to do is check 1)} {2} $ streets, and you can reduce the amount of calculation to $ O (N ^ 2) $ and calculate fast enough.

Another solution

This time, I'll just touch it lightly, but if you take advantage of the fact that each match has an order, the set of matches is a semi-ordered set **. ** A semi-cycled set can always be represented by a DAG (Directed acyclic graph) without a cycle **, so depth-first search can be used to solve this problem.

For more information on alternative solutions, see this article (https://algo-logic.info/abc139e/).

//For compiler optimization
#pragma GCC optimize("Ofast")
//Include(Alphabetical order)
#include<bits/stdc++.h>
using namespace std;
typedef int ll;

#define REP(i,n) for(ll i=0;i<n;i++)
//x is a container such as vector
#define SIZE(x) ll(x.size())
#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
#define Umap unordered_map

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n;cin>>n;
    vector<vector<ll>> a(n,vector<ll>(n-1));
    REP(i,n){
        REP(j,n-1){
            ll c;cin>>c;
            if(c-1<i)a[i][j]=c-1+n*i;
            else a[i][j]=i+n*(c-1);
        }
    }
    Umap<ll,ll> d;
    REP(i,n)d[a[i][0]]++;
    vector<ll> b(n,0);
    ll ans=0;
    deque<ll> nextd;
    deque<ll> cleard;
    while(!d.empty()){
        ans++;
        bool g=true;
        for(const auto& i : d){
            if(i.S==2){
                g=false;
                ll e=(i.F)/n;ll f=(i.F)%n;
                cleard.insert(cleard.begin(),i.F);
                b[e]++;b[f]++;
                if(b[e]<n-1)nextd.insert(nextd.begin(),a[e][b[e]]);
                if(b[f]<n-1)nextd.insert(nextd.begin(),a[f][b[f]]);
            }
        }
        if(g){
            cout<<-1<<endl;
            return 0;
        }
        ll ln,lc;ln=SIZE(nextd);lc=SIZE(cleard);
        REP(i,ln){
            d[*--nextd.end()]++;
            nextd.pop_back();
        }
        REP(i,lc){
            d.erase(*--cleard.end());
            cleard.pop_back();
        }
    }
    cout<<ans<<endl;
    return 0;
}

from collections import deque
n=int(input())
#Each length is n-1
a=[[j-1+n*i if j-1<i else i+n*(j-1) for j in list(map(int,input().split()))] for i in range(n)]
#Enter candidates for the match
d=dict()
for i in range(n):
    if a[i][0] in d:
        d[a[i][0]]+=1
    else:
        d[a[i][0]]=1
#How far have you seen
b=[0]*n
#Maximum n(n-1)/Twice
ans=0
nextd=deque()
cleard=deque()
changeable1=deque(set([a[i][0] for i in range(n)]))
while len(d):
    ans+=1
    #If none of them are the same
    g=True
    changeable2=deque()
    for i in changeable1:
        if d[i]==2:
            g=False
            e,f=i//n,i%n
            cleard.append(i)
            b[e]+=1
            b[f]+=1
            if b[e]<n-1:
                nextd.append(a[e][b[e]])
                changeable2.append(a[e][b[e]])
            if b[f]<n-1:
                nextd.append(a[f][b[f]])
                changeable2.append(a[f][b[f]])
    if g:
        exit(print(-1))
    ln,lc=len(nextd),len(cleard)  
    for _ in range(ln):
        i=nextd.popleft()
        if i in d:
            d[i]+=1
        else:
            d[i]=1
    for _ in range(lc):
        i=cleard.popleft()
        d.pop(i)
    changeable1=set(changeable2)
print(ans)

Day 19

ABC140-E Second Sum

Time taken

I don't know after using it for about 30 minutes → Explanation AC

Cause of mistake

I wasn't confident in my solution. The solution could not be simplified.

Consideration

First, if ** all candidates cannot be counted in time ** and ** within the range in which the value candidates can be counted ** in such a sum calculation, ** value candidates are calculated in the sum. You can speed up by thinking about how many times it appears **.

In this problem, we can see that there are only $ 1 \ leqq X_ {L, R} \ leqq N-1 $ $ N-1 $, so it is likely that we can count by value candidates.

Next, looking at the condition of the problem statement, when $ L, R (1 \ leqq L <R \ leqq N) $, the second number in $ P_L, P_ {L + 1},…, P_R $ Is $ X_ {L, R} $. Therefore, when $ P_i $ becomes $ X_ {L, R} $, there is only one number in $ P_L, P_ {L + 1},…, P_R $ that is larger than ** $ P_i $ * *To do. Therefore, to find out if there is a way to choose $ L, R $ in this way, you should pay attention to the numbers larger than ** $ P_i $ **, so such numbers are red circles and $ P_i $ is blue circles. It is represented by and is as shown in the figure below. (It means that you are ** binarizing ** whether it is larger than $ P_i $.)

$ L and R $ can be selected to include the red and blue circles between ① or ② in the above figure (✳︎), so the closest element on the left side of the numbers larger than ** $ P_i $ 2 It can be said that it is only necessary to know the two closest elements on the right side.

Here, if you try to search for a larger element for each $ P_i $ from $ P_1, P_2,…, P_N $ each time, you will search only $ O (N ^ 2) $ in total, which is too late. However, it is better to look at the ** wasteful search range ** and ** only need to know the number of indexes larger than ** $ P_i $ **. In other words, if you prepare a container s that stores only numbers larger than that number, you can calculate at high speed by checking the index ** in order from the largest number and saving it in s. .. Also, ** s must be ordered ** so that we can look up the two indexes closest to $ i $ on the left and right sides, so we decided to use set here.

The above policy can be summarized as follows.

Insert the index into s in descending order. In this child, when inserting the index $ i $ of the number $ P_i $ you are looking at into s, the smallest two indexes (r1 < r2) on the right side and the smallest on the left side Find the index (l1> l2) of the two numbers in and find the number when $ X_ {L, R} = P_i $. Also, as it is, there is a possibility that r1, r2, l1, l2 do not exist, so as ** index for sentinel **, -2, -1, n Store , n + 1 in s first. Under this, the number when $ X_ {L, R} = P_i $ is satisfied can be calculated by (✳︎) as shown in the figure below.

Also, in the case of l1 <0, there is no case where ① is satisfied, and in the case of r1> n-1, there is no case where ② is satisfied, so it is necessary to calculate by excluding these patterns. Yes, you can write a program of $ O (N \ log {N}) $ by performing the above calculation for any $ P_i $.

//For compiler optimization
#pragma GCC optimize("O3")
//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 1000000007 //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
#define Umap unordered_map
#define Uset unordered_set
//.lower_bound is O(√n)
signed main(){
    //Code for speeding up input
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n;cin>>n;
    vector<ll> p(n);vector<ll> p_num(n);
    REP(i,n){cin>>p[i];p[i]--;p_num[p[i]]=i;}
    //It's a good idea to have a sentinel
    //p[i]Save a larger number of indexes
    set<ll> s;
    s.insert(-2);s.insert(-1);
    s.insert(n);s.insert(n+1);
    ll ans=0;
    //Process from large number
    REPD(i,n){
        //Index on p
        ll j=p_num[i];
        ll l1,l2,r1,r2;
        r1=*(s.upper_bound(j));
        r2=*(++s.upper_bound(j));
        l1=*(--s.lower_bound(j));
        l2=*(--(--s.lower_bound(j)));
        //cout<<l2<<" "<<l1<<" "<<r1<<" "<<r2<<endl;
        if(l1>-1)ans+=((i+1)*(l1-l2)*(r1-j));
        if(r1<n)ans+=((i+1)*(r2-r1)*(j-l1));
        s.insert(j);
    }
    cout<<ans<<endl;
}

ABC146-D Coloring Edges on Tree

Time taken

About 25 minutes

Consideration

It would be great if the problems in the first half of green and light blue could be solved in about 10 minutes without making a mistake in the policy.

For each vertex, the colors of the sides that have the vertices as the end points can be painted differently, so if you repeat painting using all the colors other than the side that passed immediately before with BFS or DFS, paint all the sides. I can. However, I chose a different solution because I thought it would be troublesome to implement the judgment I passed immediately before (although it is no different from DFS or BFS after all).

Save each side extending from each vertex, and paint in order from the side connected to the point with the smallest number. At this time, if each side is already painted, that color cannot be painted, so save the color number in cand1. On the contrary, I want to paint the side that has not been painted yet, so save it in cand2. Under this, you can access all the elements of cand2 and paint each side in order from the color with the smallest number only with the colors not included in cand1.

n=int(input())
paths=[[] for i in range(n)]
colors=[0]*(n-1)
for i in range(n-1):
    a,b=map(int,input().split())
    paths[a-1].append(i)
    paths[b-1].append(i)
m=0
for i in range(n):
    m=max(m,len(paths[i]))
print(m)
for i in range(n):
    cand1,cand2=set(),[]
    for j in paths[i]:
        if colors[j]!=0:
            cand1.add(colors[j])
        else:
            cand2.append(j)
    now=1
    for j in cand2:
        while now in cand1:
            now+=1
        colors[j]=now
        now+=1
for i in range(n-1):
    print(colors[i])