AtCoder Beginner Contest 151 Review of past questions

This time's results

スクリーンショット 2020-02-02 20.20.53.png

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 ...

Recommended Posts

AtCoder Beginner Contest 102 Review of past questions
AtCoder Beginner Contest 072 Review of past questions
AtCoder Beginner Contest 062 Review of past questions
AtCoder Beginner Contest 113 Review of past questions
AtCoder Beginner Contest 074 Review of past questions
AtCoder Beginner Contest 051 Review of past questions
AtCoder Beginner Contest 127 Review of past questions
AtCoder Beginner Contest 119 Review of past questions
AtCoder Beginner Contest 151 Review of past questions
AtCoder Beginner Contest 075 Review of past questions
AtCoder Beginner Contest 054 Review of past questions
AtCoder Beginner Contest 110 Review of past questions
AtCoder Beginner Contest 117 Review of past questions
AtCoder Beginner Contest 070 Review of past questions
AtCoder Beginner Contest 105 Review of past questions
AtCoder Beginner Contest 112 Review of past questions
AtCoder Beginner Contest 076 Review of past questions
AtCoder Beginner Contest 089 Review of past questions
AtCoder Beginner Contest 069 Review of past questions
AtCoder Beginner Contest 079 Review of past questions
AtCoder Beginner Contest 056 Review of past questions
AtCoder Beginner Contest 087 Review of past questions
AtCoder Beginner Contest 067 Review of past questions
AtCoder Beginner Contest 093 Review of past questions
AtCoder Beginner Contest 046 Review of past questions
AtCoder Beginner Contest 123 Review of past questions
AtCoder Beginner Contest 049 Review of past questions
AtCoder Beginner Contest 078 Review of past questions
AtCoder Beginner Contest 081 Review of past questions
AtCoder Beginner Contest 047 Review of past questions
AtCoder Beginner Contest 060 Review of past questions
AtCoder Beginner Contest 104 Review of past questions
AtCoder Beginner Contest 057 Review of past questions
AtCoder Beginner Contest 121 Review of past questions
AtCoder Beginner Contest 126 Review of past questions
AtCoder Beginner Contest 090 Review of past questions
AtCoder Beginner Contest 103 Review of past questions
AtCoder Beginner Contest 061 Review of past questions
AtCoder Beginner Contest 059 Review of past questions
AtCoder Beginner Contest 044 Review of past questions
AtCoder Beginner Contest 083 Review of past questions
AtCoder Beginner Contest 048 Review of past questions
AtCoder Beginner Contest 124 Review of past questions
AtCoder Beginner Contest 116 Review of past questions
AtCoder Beginner Contest 097 Review of past questions
AtCoder Beginner Contest 088 Review of past questions
AtCoder Beginner Contest 092 Review of past questions
AtCoder Beginner Contest 099 Review of past questions
AtCoder Beginner Contest 065 Review of past questions
AtCoder Beginner Contest 053 Review of past questions
AtCoder Beginner Contest 094 Review of past questions
AtCoder Beginner Contest 063 Review of past questions
AtCoder Beginner Contest 107 Review of past questions
AtCoder Beginner Contest 071 Review of past questions
AtCoder Beginner Contest 064 Review of past questions
AtCoder Beginner Contest 082 Review of past questions
AtCoder Beginner Contest 084 Review of past questions
AtCoder Beginner Contest 068 Review of past questions
AtCoder Beginner Contest 058 Review of past questions
AtCoder Beginner Contest 043 Review of past questions
AtCoder Beginner Contest 098 Review of past questions