This time's results

Impressions of this time

It is a past question that I have already solved in real time, but I forgot all the problems, so I solved it with a bacha. I couldn't solve the E problem when I solved it in real time, but I couldn't solve the E problem this time either ... I have no choice but to review it often ...

Problem A

Gets the ASCII code (ord) and outputs the next element.

`A.py`


print(chr(ord(input())+1))

B problem

Consider the points from 0 to k required to make the total and average up to that point m points or more.

`B.py`


n,k,m=map(int,input().split())
a=sum(list(map(int,input().split())))
if n*m-a>k:
    print(-1)
else:
    print(max(n*m-a,0))

C problem

** Count the number of penalties until AC. Consider each case depending on whether or not it is AC.

`C.py`


n,m=map(int,input().split())
ps=[list(input().split()) for i in range(m)]
pen=[0]*n#Number of pena
rig=[0]*n#ACorWA

for i in range(m):
    if ps[i][1]=="AC":
        rig[int(ps[i][0])-1]=1
    else:
        if rig[int(ps[i][0])-1]==0:
            pen[int(ps[i][0])-1]+=1
cnt1,cnt2=0,0
for i in range(n):
    if rig[i]==1:
        cnt1+=rig[i]
        cnt2+=pen[i]

print(str(cnt1)+" "+str(cnt2))

D problem

Grid search I get lost every time I write code. Why? (There seems to be no reason other than being unfamiliar). The first is the BFS written in real time, and the second is the WF written in the Bachacon. In the case of BFS, the order of one search is O ($ HW ), and the selection of the starting node is O ( HW ), so O ( H ^ 2W ^ 2 ) is enough. (Since it is a basic BFS, the explanation of how to do it is only to write a comment out in the code. BFS is the most basic when going the shortest distance.) In the case of WF (it doesn't pass in Python, it passes in PyPy), it treats all grids as nodes and simply performs the WF method, and finally finds the value of the largest element (except inf) (excluding inf). O ( H ^ 3W ^ 3 $)). The grid of i and j is an array for recording WF and is i * w + j (I personally like BFS because the judgment conditions are complicated).

`answerD_BFS.py`


import queue
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]

inf=100000000
ma=[]
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            x=[[inf for i_sub in range(w)] for j_sub in range(h)]
            #The grid you are looking at
            q=queue.Queue()
            d=0
            #First grid
            q.put([i,j])
            x[i][j]=0
            #Follow the grid one after another and finish after following all the grids
            while q.qsize()!=0:
                #Add distance
                d+=1
                l=q.qsize()
                #Count the number of grids you have
                for t in range(l):
                    I,J=q.get()
                    #From the current grid to the next grid
                    #The judgment is"Is there a grid there","Can you follow that","Have you already followed"There are three.
                    if I-1>=0 and s[I-1][J]=="." and x[I-1][J]==inf:
                        q.put([I-1,J])
                        #If this update is not done in the if statement, the grid will be examined more.
                        x[I-1][J]=d
                    if I+1<=h-1 and s[I+1][J]=="." and x[I+1][J]==inf:
                        q.put([I+1,J])
                        x[I+1][J]=d
                    if J-1>=0 and s[I][J-1]=="." and x[I][J-1]==inf:
                        q.put([I,J-1])
                        x[I][J-1]=d
                    if J+1<=w-1 and s[I][J+1]=="." and x[I][J+1]==inf:
                        q.put([I,J+1])
                        x[I][J+1]=d
            ma_sub=0
            for k in range(h):
                for l in range(w):
                    if x[k][l]!=inf:
                        ma_sub=max(ma_sub,x[k][l])
            ma.append(ma_sub)

print(max(ma))

`answerD_WF.py`


h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
inf=1000000000
wf=[[inf]*(h*w) for i in range(h*w)]
for i in range(h*w):
    k,l=i//w,i%w
    #print(l)
    if s[k][l]=="#":
        continue
    if k!=0:
        if s[k-1][l]==".":
            wf[i][i-w]=1
    if k!=h-1:
        if s[k+1][l]==".":
            wf[i][i+w]=1
    if l!=0:
        if s[k][l-1]==".":
            wf[i][i-1]=1
    if l!=w-1:
        if s[k][l+1]==".":
            wf[i][i+1]=1
    wf[i][i]=0
for i in range(h*w):
    for j in range(h*w):
        for k in range(h*w):
            wf[j][k]=min(wf[j][k],wf[j][i]+wf[i][k])
ans=0
for i in range(h*w):
    for j in range(h*w):
        if wf[i][j]!=inf:
            ans=max(ans,wf[i][j])
print(ans)

E problem

I was wondering why O ($ N ^ 2 $) would pass even with N = $ 10 ^ 5 $. It became TLE without passing.

In the solution method that becomes O ($ N ^ 2 $), max and min are determined and only the required number of elements (k-2) are selected between them, so ** max and min are set at the same time. If you don't decide, you will notice that you can solve it with O (N) **. In other words, it can be easily solved by finding the sum of max and the sum of min, and finally considering the difference between the sums **.

Regarding how to solve the correct answer, the TLE pattern and the calculation itself are almost the same. First, prepare array A as an array that receives input and sort it in ascending order. Then, when finding max, consider how many cases each element $ A_i $ becomes max. In this case, select $ A_i $ and then select k-1 from the smaller $ A_1 $ ~ $ A_ {i-1} $, so `COM (i, k-1) ) * a [i] ``` is calculated by the code. First, add this to ans (don't forget to leave it as a mod). Next, when finding min, you can select k-1 from $ A_ {i + 1} $ ~ $ A_ {n-1} $ `COM (ni-1, k-1) You can write the code as * a [i] , so let's go to ans. However, if ans is-, you need to be too careful with the MOD to consider negative division, and avoided it with ans = MOD-abs (ans)% MOD```.

`answerE_TLE.cc`


#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<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
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#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 INF 1000000000000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second
const ll MAX=200000;

ll fac[MAX], finv[MAX], inv[MAX];

//Pretreatment to make a table
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

//Binomial coefficient calculation
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;
}

signed main(){
    COMinit();
    ll n,k;cin >> n >> k;
    vector<ll> a(n);REP(i,n) cin >> a[i];
    sort(ALL(a));
    ll ans=0;
    if(k==1){
        cout << 0 << endl;
        return 0;
    }
    REP(i,n){
        FOR(j,i+1,n-1){
            ans+=((COM(j-i-1,k-2)*((a[j]-a[i])%MOD))%MOD);
            ans%=MOD;
        }
    }
    cout << ans << endl;
}

`answerE.cc`


//Reference: http://ehafib.hatenablog.com/entry/2015/12/23/164517
//Include
#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<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
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#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 INF 1000000000000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second
const ll MAX=200000;

ll fac[MAX], finv[MAX], inv[MAX];

//Pretreatment to make a table
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

//Binomial coefficient calculation
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;
}

signed main(){
    COMinit();
    ll n,k;cin >> n >> k;
    vector<ll> a(n);REP(i,n) cin >> a[i];
    sort(ALL(a));
    ll ans=0;
    if(k==1){cout << 0 << endl;return 0;}
    //First think about MAX
    REP(i,n){
        ans+=(COM(i,k-1)*a[i]);
        ans%=MOD;
    }
    REP(i,n){
        ans-=(COM(n-i-1,k-1)*a[i]);
        if(ans<0){
            ans=MOD-abs(ans)%MOD;
        }else{
            ans%=MOD;
        }
    }
    cout << ans << endl;
}

F problem

I haven't solved it yet, I'm sorry. Solve when you have time! Geometry hasn't solved much of the problem yet, and I'm not very good at it ...

AtCoder Beginner Contest 151 Review of past questions

This time's results

Impressions of this time

Problem A

A.py

B problem

B.py

C problem

C.py