[PYTHON] Educational Codeforces Round 87
This time's results
Impressions of this time
I participated in a contest called Edufo, commonly known as Codeforces. I was confused because I couldn't understand the difference between the regular contests. It was three completes up to A, B, C1. I felt that both C2 and D could be solved, but in the end I couldn't solve either.
When I checked the solution on Twitter etc., it seemed that I could do it by finding the method I wanted to envision, so I would like to investigate the cause of the solution.
Problem A
It was difficult to decipher the problem statement and it took a long time to solve it. Four values of $ a, b, c and d $ are given, but this problem can be answered correctly by drawing the following figure.
The total sleep time should be $ a $ or more, and if you sleep for $ b $ at the beginning, the alarm will sound, and after that, the alarm will sound for $ c $, and $ d $ will try to sleep **. ** So you can actually sleep only $ cd $ and this will be repeated endlessly.
First, when $ b \ geqq a $, it happens when $ b $ has passed. Note that this is $ b $ instead of $ a $.
Also, when $ c \ leqq d $, you can only sleep at the first $ b $, so you need to output -1 when a> b.
Implementing the above, it becomes as follows.
A.py
t=int(input())
for i in range(t):
a,b,c,d=map(int,input().split())
if d>=c:
if b>=a:
print(b)
else:
print(-1)
else:
if b>=a:
print(b)
else:
a-=b
num=-((-a)//(c-d))
print(b+num*c)
Problem B
Outputs the length of the shortest substring that contains all of 1, 2, and 3. However, if such a substring does not exist, it should output 0.
This problem can be solved by using the ** scale method ** because the intervals can be moved and counted ** continuously **, but the implementation is slow after coming up with the scale method. I felt that I was an amateur myself.
In the implementation of the scale method, query processing should be performed in the order of "** advance the right edge in order to the right ** → ** advance the left edge in order to the right **". Also note that ** the right edge does not exceed the range of the array you want to examine ** and ** the left edge does not exceed the right edge **.
B.py
t=int(input())
for i in range(t):
s=input()
le=len(s)
l,r=0,0
d=[0,0,0]
d[int(s[0])-1]=1
ans=0
while True:
#R decision
while not all(d) and r!=le-1:
r+=1
d[int(s[r])-1]+=1
if r==le-1:
break
#l decision
while l!=le-1:
if all(d):
if ans==0:
ans=r-l+1
else:
ans=min(ans,r-l+1)
d[int(s[l])-1]-=1
l+=1
else:
break
if r==le-1 or l==le-1:
break
print(ans)
C1 problem
In the case of even numbers, you can enclose the polygon with the smallest square by arranging the shapes as shown below (I can't prove it because I did it heuristically).
If you make a triangle by connecting the center of the polygon and the vertices of the polygon and calculate using the trigonometric ratio (sin, cos, tan), $ \ frac {1} {\ tan {\ frac {90} {n}} } $ You can ask.
By the way, as a heuristic idea, it is the apex of the polygon that is farthest from the center of the polygon, and this shape is one because it is necessary to consider ** arrangement with good symmetry **. It feels like it was convenient.
C1.py
import math
t=int(input())
for i in range(t):
n=int(input())
print(1/math.tan(math.radians(90/n)))
C2 problem
In the case of an odd number, I misunderstood that the leftmost figure was written dirty and the top and bottom sides touched the square (** draw the figure neatly! **).
As before, there are only the above three patterns ** when drawing with symmetry in mind, but the left and right patterns can be regarded as the same pattern ** by turning the square. Therefore, consider which of the leftmost and middle patterns has the larger area, which is clearly the middle pattern (calculated).
This middle pattern is between the right and left patterns, and since it moves $ \ frac {180} {n} $ from left to right, it is thought that $ \ frac {90} {n} $ is moved from the left pattern. For example, it is possible to obtain $ \ frac {\ cos {\ frac {45} {n}}} {\ sin {\ frac {90} {n}}} $ by performing the same geometrical consideration as before. I can do it.
C2.py
import math
t=int(input())
for i in range(t):
n=int(input())
print(math.cos(math.radians(45/n))/math.sin(math.radians(90/n)))
D problem
I thought it would be possible to solve it by using BIT, but I couldn't solve it because I didn't know that binary search was possible on BIT. It's not difficult if you can do a binary search.
First, the position to insert and the position to delete are ** determined based on the sort **, so consider sorting this multiset and operating while keeping that sort.
Here, ** duplicate numbers ** are the same when sorted together, so ** an array x ** ($ 1 \ leqq $ (element of x) that stores how many numbers each number is) Prepare $ \ leqq n $).
If you think about inserting under this, you can execute it with O (1) (because you only add +1 to the element of the $ \ because $ array), but when deleting, decide the element of the array to be -1 It is necessary to get the number of the element, which is O (n).
Here, the array x ** that stores the number of each number is managed by BIT (see this article for BIT). Then, the insertion becomes O ($ \ log {n}
If you can drop the order so far, you can write the program by O ($ n (\ log {n}) ^ 2
ios::sync_with_stdio(false);
cin.tie(nullptr);
D.cc
//Include(Alphabetical order)
#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
//k & -k is LSB
//bit_x to i 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 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;
}
//a_1 + a_2 + … + a_i >=Find the smallest i such that x(a_k >= 0)
//If x is 0 or less, there is no corresponding item → 0 is returned.
ll lower_bound(ll x){
if(x<=0){
return 0;
}else{
ll i=0;ll r=1;
//Get the maximum possible interval length
//Should be the smallest square of n or less(The largest section of the sequence managed by BIT)Seeking
while(r<n) r=r<<1;
//The length of the section is halved each time it is examined
for(int len=r;len>0;len=len>>1) {
//When adopting that section
if(i+len<n && bit[i+len]<x){
x-=bit[i+len];
i+=len;
}
}
return i+1;
}
}
};
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n,q;cin >> n >> q;
BIT a(n);REP(i,n){ll a_sub;cin >> a_sub;a.add(a_sub,1);}
vector<ll> k(q);REP(i,q) cin >> k[i];
REP(i,q){
if(k[i]>0){
a.add(k[i],1);
}else{
//What is included in the sequence is always specified
a.add(a.lower_bound(-k[i]),-1);
}
}
vector<ll> answers(n);
REP(i,n){answers[i]=a.sum(i+1);}
if(answers[n-1]<=0){
cout << 0 << endl;return 0;
}
REP(i,n){
if(i>0){
if(answers[i]-answers[i-1]>0){
cout << i+1 << endl;return 0;
}
}else{
if(answers[i]>0){
cout << i+1 << endl;return 0;
}
}
}
}
E problem, F problem, G problem //codeforces.com/contest/1354/problem/G)
I think I'm still lacking in ability, so I'll skip this time.
Recommended Posts