[PYTHON] AtCoder Beginner Contest 107 Review of past questions
Time required
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