[PYTHON] yukicoder contest 266 Review
result
Impressions
I was impatient because I couldn't solve D, but if I think about it, I can solve it just by transforming the formula. Also, although I came up with the idea of the E problem, I could not analyze the amount of calculation. ** Keep in mind that analysis using harmonic series is important **.
Recently, the review has been neglected and various things have been delayed, so I would like to adjust the rhythm of the review.
Problem A
Try up to $ [\ frac {n} {5}] $ times, conversion up to $ [\ frac {n} {2}] $, penalty goal up to $ [\ frac {n} {3} ] $ Times. Also, since $ N $ is 100 or less, you can search all. However, keep in mind that it is the number of conversions $ \ leqq $ the number of tries.
A.py
n=int(input())
ans=0
for i in range(n//5+1):
for j in range(n//2+1):
for k in range(n//3+1):
ans+=(i*5+j*2+k*3==n and i>=j)
print(ans)
Problem B
First, the treasure chest probabilities have nothing to do with the answer, so let's say $ p \ leqq q \ leqq r $.
At this time, mark a treasure chest and ** STAY or CHANGE **. When selecting STAY, ** STAY to the treasure chest with the highest probability is the maximum **, so the probability of getting a diamond is equal to the probability of having a diamond in the selected treasure chest $ r / (p + q + r) It's $. When selecting CHANGE, ** the maximum probability is to change from the treasure chest with the lowest probability **, so the probability of getting a diamond is equal to the probability of having a diamond in the unselected treasure chest $ (q + r) / ( p + q + r) $.
Therefore, the answer is $ max (r / (p + q + r), (q + r) / (p + q + r)) = (q + r) / (p + q + r) $.
B.py
p,q,r=sorted(list(map(int,input().split())))
print((q+r)/(p+q+r))
C problem
First, it's important to be a multiple of 10, so take $ mod \ 10 $ for each card. Also, by choosing one card, the value of $ mod \ 10 $ will change, and ** consider the DP that you can have with the maximum number of cards you can choose as the state. At this time, set DP as follows.
$ dp [i]: = $ (maximum number of sheets when the remainder is $ i $)
Also, the transition will be as follows when selecting the card $ A \ _j $.
In addition, ** the transition is not one-way **, so you need to update ** $ dp $ collectively ** when you select card $ A \ _j $. Therefore, each card $ A \ _j $ update must be saved in $ dp \ _sub $ and recorded in $ dp $ after the card $ A \ _j $ has been selected.
C.py
ans=0
n=int(input())
check=[0 for i in range(10)]
a=list(map(int,input().split()))
for i in a:
check[i%10]+=1
dp=[0 for i in range(10)]
for i in range(10):
for j in range(check[i]):
dp_sub=[0]*10
for k in range(10):
if k==0:
dp_sub[(i+k)%10]=dp[k]+1
elif dp[k]!=0:
dp_sub[(i+k)%10]=dp[k]+1
for k in range(10):
dp[k]=max(dp[k],dp_sub[k])
#print(dp_sub)
#print(dp)
print(dp[0])
D problem
I thought about it for a while during and after the contest, but I didn't understand. If I had a head, I might have solved it.
It's hard to think of conspicuous rules and typical solutions, but since it's a ** problem of the relationship between prime numbers and powers **, I'll use ** Fermat's Little Theorem **. Fermat's little theorem is as follows.
When p is a prime number and a is a relatively prime integer with p, a^{p-1} = 1\ (mod \ p) \\
To show this, from the binomial theorem a^{p} = a\ (mod \ p)Just show.
First, if you substitute the value into Fermat's little theorem as it is, $ 2 ^ {p \ _ i-1} = 1 \ (mod \ p \ _ i) $… ① holds, so consider ** transforming this formula **. I will. Also, ** 2 and $ p \ _i $ must be relatively prime **, but this is only when $ p \ _i = 2 $, which holds for $ x = 2 $. Here, the value on the right side does not change when the power of both sides ** of ** ① is taken, but the value on the left side changes. In other words, if you take the $ t $ power of both sides of ①, $ 2 ^ {t (p \ _ i-1)} = 1 \ \ (mod \ p \ _i) $ holds. Also, what you want to find is when $ 2 ^ {t (p \ _ i-1)} = t (p \ _ i-1) \ \ (mod \ p \ _i) $. Therefore, if ** two sides are combined **, $ t (p \ _ i-1) = 1 \ \ (mod \ p \ _ i) $ is established. By transforming this, if $ t = p \ _i-1 $ is set from $ p \ _i-t = 1 \ \ (mod \ p \ _i) $, this is satisfied, and $ x = (p \ _ i-1) ) ^ 2 $ is less than $ 10 ^ {18} $, so it certainly meets the criteria in question.
From the above, the subject is satisfied by $ x = 2 $ when $ p \ _i = 2 $ and $ x = (p \ _ i-1) ^ 2 $ when $ p \ neq 2 $.
D.py
for i in range(int(input())):
n=int(input())
print(2 if n==2 else (n-1)**2)
E problem
I learned a lot because ** Computational complexity analysis by harmonic series ** was the first type of problem to solve an important problem. For the harmonic series, refer to this article.
First, find the sum of the values of $ A \ _i % A \ _j $ for any $ i, j $. In such a ** summation problem, it is good to pay attention to each value **, but it is difficult to leave it as it is, so consider ** paraphrase **. In other words, $ A \ _i % A \ _j = A \ _i-[\ frac {A \ _i} {A \ _ j}] \ times A \ _j $. At this time, $ A \ i $ is $ n \ sum {i = 1} ^ {n} A \ _i $, so it can be calculated by $ O (N) $, but $ [\ frac {A \ _i} {A \ _ j}] \ times A \ _ j $ is not easy to find.
Here, if you fix $ A \ _j $, there may be $ i $ that matches ** $ [\ frac {A \ _i} {A \ _j}] \ times A \ _j $ ** Because there is, let's fix $ A \ _j $ (because if $ \ because $ matches, ** can be calculated together ** in most cases). Also, when the values match and $ [\ frac {A \ _i} {A \ _j}] = k $, $ A \ _j \ times k \ leqq A \ _i <A \ j \ times (k +) 1) Since it becomes $, we will count it together with the image of ** frequency distribution **. At this time, if you arrange the sequence $ A $ in ascending order, you can ** find out how many numbers correspond to a certain $ k $ using a binary search **. Also. To improve the efficiency of calculation, the sum when fixed at a certain $ A \ j $ is saved in the dictionary, and if the same number appears, the number saved in the dictionary is used. Also, there are up to $ [\ frac {A \ _ {max}} {A \ j}] $ for each $ A \ j $, and each search costs $ O (\ log {n}) $. , The total complexity is $ O (\ sum \ _ {j = 1} ^ {n} [\ frac {A \ _ {max}} {A \ _ j}] \ log {n}) = O (A { max} \ log {n} \ sum \ _ {j = 1} ^ {n} [\ frac {1} {A \ _ j}]) $. Also, here from ** the concept of harmonic series ** (✳︎), $ O (\ sum \ _ {j = 1} ^ {n} [\ frac {1} {A \ _ j}]) = O (\ log Since {A {max}}) $, the total amount of calculation is $ O (A {max} \ log {n} \ log {A {max}}) $.
(✳︎)… ** I want to make it so that when I see the sum of fractions, I can reduce it to a harmonic series **!
E.py
n=int(input())
a=list(map(int,input().split()))
a.sort()
from bisect import bisect_left,bisect_right
ans=0
d=dict()
for i in range(n):
if a[i] in d:
ans+=d[a[i]]
continue
ans_sub=0
j=i
while j!=n:
x=a[j]//a[i]
b=bisect_left(a,(x+1)*a[i],lo=j)-1
ans_sub+=(x*(b-j+1)*a[i])
j=b+1
d[a[i]]=ans_sub
ans+=ans_sub
print(sum(a)*n-ans)
F problem
I have copied the code in this article. If it's a simple problem, you can use another library, but it's a difficult problem and you can't do the same, so I'll try to make a library of segment trees as soon as possible.
F.cc
//Debugging options:-fsanitize=undefined,address
//Compiler optimization
#pragma GCC optimize("Ofast")
//Include etc.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//macro
//for loop
//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.
//FORA is a range for statement(If it's hard to use, erase it)
#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--)
#define FORA(i,I) for(const auto& i:I)
//x is a container such as vector
#define ALL(x) x.begin(),x.end()
#define SIZE(x) ll(x.size())
//constant
#define MOD 1000000007 //10^9+7:Congruence law
#define MAXR 100000 //10^5:The largest range in the array
//Abbreviation
#define PB push_back //Insert
#define MP make_pair //pair constructor
#define F first //The first element of pair
#define S second //The second element of pair
/* RMQ：[0,n-1]Structure that manages the minimum value for each section
set(i,x), build():Set the i-th element to x. Build a seg tree together. O(n)
add(a,b,x):section[a,b)Add x to the element of. O(log(n))
query(a,b):section[a,b)Get the smallest element in. O(log(n))
find_rightest(a,b,x): [a,b)Find the rightmost position with elements less than or equal to x. O(log(n))
find_leftest(a,b,x): [a,b)Find the leftmost position with elements less than or equal to x. O(log(n))
*/
template <typename T>
struct RMQ {
const T INF = numeric_limits<T>::max();
int n;
vector<T> dat, lazy;
RMQ(int n_) : n(), dat(n_ * 4, INF), lazy(n_ * 4, 0) {
int x = 1;
while (n_ > x) x *= 2;
n = x;
}
void set(int i, T x) { dat[i + n - 1] = x; }
void build() {
for (int k = n - 2; k >= 0; k--) dat[k] = min(dat[2 * k + 1], dat[2 * k + 2]);
}
/* lazy eval */
void eval(int k) {
if (lazy[k] == 0) return; //Exit if there is nothing to update
if (k < n - 1) { //If it is not a leaf, it propagates to the child
lazy[k * 2 + 1] += lazy[k];
lazy[k * 2 + 2] += lazy[k];
}
//Update yourself
dat[k] += lazy[k];
lazy[k] = 0;
}
void add(int a, int b, T x, int k, int l, int r) {
eval(k);
if (a <= l && r <= b) { //When completely inside
lazy[k] += x;
eval(k);
} else if (a < r && l < b) { //When some sections are covered
add(a, b, x, k * 2 + 1, l, (l + r) / 2); //Left child
add(a, b, x, k * 2 + 2, (l + r) / 2, r); //Right child
dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
}
}
void add(int a, int b, T x) { add(a, b, x, 0, 0, n); }
T query_sub(int a, int b, int k, int l, int r) {
eval(k);
if (r <= a || b <= l) { //When completely outside
return INF;
} else if (a <= l && r <= b) { //When completely inside
return dat[k];
} else { //When some sections are covered
T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
return min(vl, vr);
}
}
T query(int a, int b) { return query_sub(a, b, 0, 0, n); }
T find_rightest(int a, int b, int x) { return find_rightest_sub(a, b, x, 0, 0, n); } //If it does not exist a-1
T find_leftest(int a, int b, int x) { return find_leftest_sub(a, b, x, 0, 0, n); } //If it does not exist b
T find_rightest_sub(int a, int b, int x, int k, int l, int r) {
eval(k);
if (dat[k] > x || r <= a || b <= l) { //Your value is greater than x or[a,b)But[l,r)If it is out of the range of, return a-1
return a - 1;
} else if (k >= n - 1) { //If you are a leaf, return that position
return (k - (n - 1));
} else {
int vr = find_rightest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
if (vr != a - 1) { //Look at the subtree on the right a-If other than 1, return
return vr;
} else { //Look at the subtree on the left and return the value
return find_rightest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
}
}
}
T find_leftest_sub(int a, int b, int x, int k, int l, int r) {
eval(k);
if (dat[k] > x || r <= a || b <= l) { //Your value is greater than x or[a,b)But[l,r)If it is out of the range of, return b
return b;
} else if (k >= n - 1) { //If you are a leaf, return that position
return (k - (n - 1));
} else {
int vl = find_leftest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
if (vl != b) { //Look at the subtree on the left and return if it is other than b
return vl;
} else { //Look at the subtree on the right and return the value
return find_leftest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
}
}
}
/* debug */
inline T operator[](inta){returnquery(a,a+1); }
void print() {
for (int i = 0; i < n; ++i) {
cout << (*this)[i];
if (i != n) cout << ",";
}
cout << endl;
}
};
signed main(){
//Code for speeding up input
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll n;cin>>n;
RMQ<ll> x(n);
REP(i,n){
ll y;cin>>y;
x.set(i,y);
}
x.build();
ll q;cin>>q;
REP(i,q){
ll k,l,r,c;cin>>k>>l>>r>>c;
if(k==1){
x.add(l-1,r,c);
}else{
cout<<x.query(l-1,r)<<endl;
}
}
//x.print();
}
Recommended Posts