AtCoder Beginner Contest 107 Review of past questions

Time required

スクリーンショット 2020-05-15 9.01.44.png

Impressions

D problem was difficult and I wrestled for a few days after Bachacon. I needed a lot of thinking ability and knowledge of BIT (Binary Indexed Tree), so I would like to summarize it. I explained BIT in Another article in an easy-to-understand manner, so please refer to it.

Problem A

Note that what you should output is n-i + 1.

answerA.py


n,i=map(int,input().split())
print(n-i+1)

B problem

I want to use numpy for this kind of grid problem. I hope I can learn how to operate numpy in the near future. The implementation is easy to understand if the operations except rows and columns are performed separately.

answerB.py


h,w=map(int,input().split())
a=[]
#Excludes lines consisting only of white squares
for i in range(h):
    k=input()
    if k!="."*w:
        a.append(k)
l=len(a)

ans=[[] for i in range(l)]
#Excludes columns consisting only of white squares
for i in range(w):
    for j in range(l):
        if a[j][i]=="#":
            for k in range(l):
                ans[k].append(a[k][i])
            break
for i in range(l):
    print("".join(ans[i]))

C problem

It is best to light ** k consecutive candles **, and there are n-k + 1 possible candidates. Furthermore, since we are at the point of coordinate 0 at the beginning, there are two patterns for each candidate, one that goes from coordinate 0 → left end → right end and the other that goes from coordinate 0 → right end → left end, so this $ 2 \ times (n) -k + 1) Find the minimum time (= distance traveled) in the $ street.

answerC.py


n,k=map(int,input().split())
x=list(map(int,input().split()))
mi=10**10
for i in range(n-k+1):
    mi=min(mi,x[k-1+i]-x[i]+min(abs(x[i]),abs(x[k-1+i])))
print(mi)

D problem

I tried to find the median well, but ** misread ** that the given sequence was sorted in the first place. Also, I read and understood the correct answer, but I felt that it was quite difficult and my ability was insufficient. However, it was a very informative problem, so I would like to explain it in detail. Also, as mentioned in the previous impression, BIT will be explained as known, so please refer to this article for BIT. ..

First, we need to abstract the median condition ** so that it is easy to find ** (this sense of abstraction seems to increase as we solve more problems).

Assuming that the median value of the sequence b of length M is x, there are more than $ [\ frac {M} {2}] $ and more elements in ①: b, and ②: ① is satisfied. Two conditions are required: x is the maximum. … (✳︎)

What you can see from this is that it is ** monotonic . Therefore, we can see that the median can be found by binary search ( Median → Binary search seems to occur frequently **).

Since we found that we can search by binary search, we will consider "conditions where the median value of the subject sequence $ m $ is ** x or more **" ... (1).

From (✳︎), (1) sets the median of $ (a_l, a_ {l + 1},…, a_ {r}) $ to $ m_ {l, r} (1 \ leqq l \ leqq r \ leqq N) There are $ [\ frac {_ {n + 1} C 2} {2}] $ or more $ m {l, r} $ that is x or more when it is $ ... (2) I can do it.

Furthermore, using (✳︎) in the same way, $ (a_l, a_ {l + 1},…, a_ {r}) $ has elements of x or more in $ for $ m_ {l, r} $ to be x or more. You can also see that [\ frac {r-l + 1} {2}] $ or more is enough. … (3)

Therefore, we only need information about ** x or more or less than x **, so if we replace ** with 1 for the former and -1 for the latter, (3) will be $ (a_l, a_ {l +). 1},…, a_ {r}) The cumulative sum of $ elements $ S_ {l, r} $ is 0 or more… (4).

Here, if the cumulative sum $ S_k $ of $ (a_1, a_2,…, a_ {k}) $ is obtained and saved first by the cumulative sum, $ S_ {l, r} = S_r-S_ {l -1} $, and (4) is $ S_r-S_ {l-1} \ geqq 0 \ leftrightarrow S_ {l-1} \ leqq It can be rephrased as S_r $… (5).

Furthermore, (5) is $ S_ {l-1} \ leqq Since it is S_r (1 \ leqq l \ leqq r \ leqq N) $, it is equivalent to $ S_l \ leqq S_r (0 \ leqq l <r \ leqq N) $… (6).

From the above consideration, the condition of (1) is that $ S_l \ leqq S_r $ is $ [\ frac {_ {n + 1 + 1 for $ l, r $ that satisfies $ 0 \ leqq l <r \ leqq N $. } C _2} {2}] It can be rephrased that there are $ or more, and we will consider asking for this.

Also, considering $ l and r $ at this time, the amount of calculation is $ O (n ^ 2) $, but with ** r fixed (r \ *) **, $ S_l \ $ l $ that satisfies leqq S_ {r ^ \ *} $ and $ 0 \ leqq l <r ^ \ * $ is actually obtained by $ O (\ log {n}) $ using ** BIT, so $ O (n \ log {n}) $ can be used to determine the pair of $ l and r $.

When using the previous BIT, the $ i $ th element (1-indexed) of the array $ B $ managed by the BIT is set to ** Cumulative sum $ S_r (0 \ leqq r \ leqq r ^ \ *- 1) Satisfy $ S_l \ leqq S_ {r ^ \ *} $ and $ 0 \ leqq l <r ^ \ * $ by setting how many times $ i $ appears in $ **. You can find $ l $ with $ B_1 + B_2 +… + B_ {S_ {r ^ \ *}} $.

Also, for ** how many times the cumulative sum $ S_r (0 \ leqq r \ leqq r ^ \ * -1) $ that becomes $ i $ appears **, $ B_ {S_ for each r Just add {r}} $.

In addition, the cumulative sum $ S_r (0 \ leqq r \ leqq n) $ can be less than or equal to 0, so $ 1-S_min $ is added to all cumulative sums so that the minimum value is 1.

If all the above is implemented, it will be as follows.

✳︎… Even after the implementation policy was established, I made a mistake in the index and output a segfault or made a mistake in what should be output, so I would like to be careful.

answerD.cc


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


//1-indexed
class BIT {
public:
    ll n; //Data length
    vector<ll> bit; //Data storage location
    BIT(ll n):n(n),bit(n+1,0){} //constructor

    //bit_x to i to o(log(n))Add with
    void add(ll i,ll x){
        if(i==0) return;
        for(ll k=i;k<=n;k+=(k & -k)){
            bit[k]+=x;
        }
    }

    //bit_1 + bit_2 + … + bit_n-1 + bit_n to O(log(n))Ask in
    ll sum(ll i){
        ll s=0;
        if(i==0) return s;
        for(ll k=i;k>0;k-=(k & -k)){
            s+=bit[k];
        }
        return s;
    }
};

ll solve(vector<ll>& a,ll x,ll n){
    vector<ll> b(n,-1);
    REP(i,n)if(a[i]>=x)b[i]=1;
    vector<ll> s(n+1,0);
    
    //It was different here ...
    FOR(i,1,n)s[i]=s[i-1]+b[i-1];

    ll base=1-MIN(s);REP(i,n+1)s[i]+=base;
    BIT T(MAX(s));
    ll ret=0;
    REP(i,n+1){
        ret+=T.sum(s[i]);
        T.add(s[i],1);
    }
    return ret;
}

signed main(){
    ll n;cin >> n;
    vector<ll> a(n,0);vector<ll> c(n,0);
    REP(i,n){cin >> a[i];c[i]=a[i];}
    sort(ALL(c));c.erase(unique(ALL(c)),c.end());
    //Find the answer by binary search
    ll check=((n+1)*n/2)/2;
    ll l,r;l=0;r=SIZE(c)-1;
    while(r>l+1){
        ll h=(l+r)/2;
        if(solve(a,c[h],n)>=check){
            l=h;
        }else{
            r=h;
        }
    }
    #if 0
    //Debug code
    REP(i,SIZE(c)){
        cout << c[i] << " " << solve(a,c[i],n) << endl;
    }
    #endif

    //Again, the mistake of reversing l and r ...
    if(solve(a,c[r],n)>=check){
        cout << c[r] << endl;
    }else{
        cout << c[l] << endl;
    }
}

Recommended Posts

AtCoder Beginner Contest 102 Review of past questions
AtCoder Beginner Contest 072 Review of past questions
AtCoder Beginner Contest 085 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 069 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 049 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 057 Review of past questions
AtCoder Beginner Contest 121 Review of past questions
AtCoder Beginner Contest 126 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 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
AtCoder Beginner Contest 114 Review of past questions
AtCoder Beginner Contest 045 Review of past questions
AtCoder Beginner Contest 120 Review of past questions
AtCoder Beginner Contest 108 Review of past questions
AtCoder Beginner Contest 106 Review of past questions
AtCoder Beginner Contest 122 Review of past questions
AtCoder Beginner Contest 125 Review of past questions