[PYTHON] AtCoder Beginner Contest 167 Review

This time's results

✳︎ ac-predictor isn't working and performance isn't working, but it was 1664.

Impressions of this time

I think it worked reasonably well this time. It was relatively easy to come up with because there were similar questions in the past in D and E. However, there were times when the implementation was buggy, so I want to avoid being impatient with such bugs. Also, I have considered the F problem properly at the very end, so I would like to be careful.

Problem A

You just have to determine if s is equal to the string excluding the end of t.

A.py

s=input()
t=input()
print("Yes" if s==t[:-1] else "No")

B problem

Consider starting with the largest number of cards.

B.py

a,b,c,k=map(int,input().split())
if a>=k:
    print(k)
elif a+b>=k:
    print(a)
else:
    print(a-(k-a-b))

C problem

It's time for a full bit search due to the C problem ... It's hard because the level of AtCoder contestants goes up and keeps up. I will do my best not to lose.

First, consider a full search (** No more doubts about DP, first a full search **). At this time, you only have to think about which reference book to choose, and the amount of calculation to select is $ O (n \ times 2 ^ n) $. How much the comprehension level of each algorithm increases when selecting a reference book here is calculated by $ O (m) $, and after deciding which reference book to select, the comprehension level of all algorithms is X or higher. Since the judgment can be made with $ O (m) $, it can be calculated with $ O (2 ^ n \ times (n \ times m + m)) = O (2 ^ n \ times n \ times m) $. Therefore, you can write a program that meets the time limit. Furthermore, even if you buy all the reference books, you may not be able to understand all the algorithms above X, so I initialized them with inf (= 100000000000000000).

Also, I put the line (✳︎) in the for statement of the next line to make it buggy. It's too crazy. However, I was able to ** try bug fixing with a sample **, so it is a good point.

C.py

n,m,x=map(int,input().split())
ca=[list(map(int,input().split())) for i in range(n)]
ans=100000000000000000
for i in range(2**n):
    check=[0]*m
    ans_=0
    for j in range(n):
        if ((i>>j)&1):
            ans_+=ca[j][0]#(✳︎)
            for k in range(m):
                check[k]+=ca[j][k+1]
    if all([l>=x for l in check]):
        ans=min(ans,ans_)
if ans==100000000000000000:
    print(-1)
else:
    print(ans)

D problem

The easiest way is to perform all k moves, but this is not possible due to k constraints. Here, if you move n times, ** there is a town i that you visit more than once ** (this proof is omitted). Furthermore, since the towns visited after the town i visited more than once can always be traced from the town i, a loop is formed in the towns after the town i until the second visit to the town i ** (input). In Example 1, a loop of 1 → 3 → 4 is formed.) Therefore, we will first consider discovering a loop, but if you save the towns you have already visited, you will be able to discover the loop when you have visited a town twice. Also, I want to use ** O (1) to determine if there is a town to visit, so save it as a set **. Also, ** save the order of visiting towns **, so save the order of visiting towns in an array. If the loop can be determined by this, it is determined by using the case before and after entering the loop and where in the loop corresponds to K (mod). This judgment etc. is not difficult (the idea), so I will only comment it out with the following code.

answerD.py

#Save the order of visiting towns in an array
visited=[0]
#Save the towns you visited as a group
visited_set=set()
visited_set.add(0)
n,k=map(int,input().split())
a=list(map(int,input().split()))
#The town where next1 is visiting now, the town where next2 is visiting next
#Exit the while loop if next2 is already visited
next1=0
next2=-1
while True:
    #To the next town
    next2=a[next1]-1
    #Make it the town you are visiting now
    next1=next2
    if next2 in visited_set:
        #Because it's a town I've already visited
        break
    else:
        #Insert into array in order
        visited.append(next2)
        #Insert into a set that records whether you have visited
        visited_set.add(next2)

#If k is smaller than the total number of visited towns, output the kth town as it is
if k<len(visited):
    print(visited[k]+1)
else:
    #Find the length of the loop(I tend to make a mistake here, so I wrote a diagram)
    loop_len=(len(visited)-visited.index(next2))
    #Until you reach the loop
    k-=(len(visited)-loop_len)
    #Given the remainder of the loop length, it's easy to see where you are in the loop.
    print(visited[k%loop_len+visited.index(next2)]+1)

E problem

I personally felt that it was easier than the D problem. However, it was a new issue, so I'm glad I came up with it during the contest (I was surprised to find it through).

Since n blocks are lined up side by side and how to paint with m color seems to be obtained by O (1), I assumed that there are $ l $ pairs of adjacent blocks. If you decide the color of the blocks from the leftmost side here, if the colors of the adjacent blocks are not different, $ m \ times (m-1) \ times (m-1) \ times (m-1) \ times … It will be $. On the other hand, if the second block is the same, we can see that it is $ m \ times (m-1) \ times 1 \ times (m-1) \ times… $. Therefore, I thought that it would be okay to ignore the parts with the same color in these adjacent blocks, so I decided to ** connect the blocks and regard them as one block **. Therefore, if there are $ l $ pairs of adjacent blocks, you can ** consider a block sequence of $ n-l $ in length that all have different colors **. Also, there are $ _ {n-1} C _ {l} $ depending on which block has the same color, so when there are $ l $ pairs of adjacent blocks, the color painting method is $ m . times (m-1) ^ {nl-1} \ times _ {n-1} C _ {l} $ It will be the same, and you can calculate this with $ l = 0 ~ k $. Also, since the answer can be very large, you need to do combination calculation by inverse element of mod (= 998244353). Furthermore, here, if you implement it while paying attention to ** that the power calculation must also be performed under mod (= 998244353) **, it will be as follows.

✳︎ By the way, I have a library of modint, so I will post it as an article soon.

answerE.cc

//Reference: http://ehafib.hatenablog.com/entry/2015/12/23/164517
//Include(Alphabetical order,bits/stdc++.Factions that do not use h)
#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
#define MAX(x) *max_element(ALL(x)) //Find the maximum value
#define MIN(x) *min_element(ALL(x)) //Find the minimum value
//constant
#define INF 1000000000000 //10^12:Extremely large value,∞
#define MOD 998244353 //10^9+7:Congruence law
#define MAXR 300000 //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

ll 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]*i%MOD;
        inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
        finv[i]=finv[i-1]*inv[i]%MOD;
    }
}

//Calculation of binomial coefficient
ll 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]%MOD)%MOD;
}

ll modpow(ll a,ll n,ll mod){
    ll res = 1;
    while(n > 0){
        if(n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

signed main(){
    COMinit();
    ll n,m,k;cin >> n >> m >> k;
    ll ans=0;
    REP(l,k+1){
        ll ansx=1;
        ansx*=COM(n-1,l);
        ansx*=modpow(m-1,n-l-1,MOD);
        ansx%=MOD;
        ansx*=modpow(m,1,MOD);
        ansx%=MOD;
        ans+=ansx;
        ans%=MOD;
    }
    cout << ans << endl;
}

F problem

It's a problem of parentheses that often appears, but I think it was quite difficult. However, I think I have to solve it even at first glance, so I want to do my best. First, when there is a parenthesis string, when ** (is +1 and) is set to -1 and the cumulative sum is considered from before, the total when all elements are 0 or more and added to the end is 0 All you need is **. Also, this problem is difficult because this condition must be met in the string. Here, for the time being, I thought about concatenating in order from the one with the largest cumulative sum of each character string, but as it is, there is a possibility that it will be smaller than 0 in each character string, so under this You must ensure that the cumulative sum within that string is always positive. For example, when the minimum cumulative sum of a character string is 0 or more, the cumulative sum is always 0 or more for all elements regardless of the order in which they are connected. So the problem is with ** the minimum cumulative sum of strings is less than 0 **. Based on this, if you pay attention to the case where the final cumulative sum of a certain character string is 0 or more **, if you can add that character string, the cumulative sum will not be reduced, and the minimum value at that time will be less than 0. The larger the value, the better, so it is best to greedily concatenate in descending order of ** the minimum cumulative sum of the strings **. On the other hand, ** if the final cumulative sum of a string is less than 0 **, ** it is not easy to greedily decide **. I've been thinking about what would happen if I greedily did it, but I can solve it by looking at kmjp's blog. Is done. Just invert the string and think about it.

I've written it so far, but when I look back on it later, I don't understand it as it is, so I'll give you almost the same explanation below using ** diagrams. I'm sorry that there are many overlapping parts. </ font>

import sys
n=int(input())
s=[input() for i in range(n)]
t=[2*(i.count("("))-len(i) for i in s]
if sum(t)!=0:
    print("No")
    sys.exit()
st=[[t[i]] for i in range(n)]

for i in range(n):
    now,mi=0,0
    for j in s[i]:
        if j=="(":
            now+=1
        else:
            now-=1
        mi=min(mi,now)
    st[i].append(mi)
#st.sort(reverse=True,key=lambda z:z[1])
u,v,w=list(filter(lambda x:x[1]>=0,st)),list(filter(lambda x:x[1]<0 and x[0]>=0,st)),list(filter(lambda x:x[1]<0 and x[0]<0,st))
v.sort(reverse=True)
v.sort(reverse=True,key=lambda z:z[1])
w.sort(key=lambda z:z[0]-z[1],reverse=True)
lu=len(u)
lv=len(v)
now2=0
for i in range(n):
    if i<lu:
        now2+=u[i][0]
    elif i<lu+lv:
        if now2+v[i-lu][1]<0:
            print("No")
            break
        now2+=v[i-lu][0]
    else:
        #No, it ’s wrong here.
        if now2+w[i-lu-lv][1]<0:
            print("No")
            break
        now2+=w[i-lu-lv][0]
else:
    print("Yes")

from itertools import accumulate,chain
n,*s=open(0).read().split()
u=[[min(accumulate(chain([0],t),lambda a,b: a+(1 if b=="(" else -1))),2*t.count("(")-len(t)] for t in s]
m=0
for c,d in chain(sorted([x for x in u if x[1]>=0])[::-1],sorted([x for x in u if x[1]<0],key=lambda z:z[0]-z[1])):
    if m+c<0:print("No");break
    m+=d
else:print("No" if m else "Yes")