yukicoder contest 266 Review

result

スクリーンショット 2020-09-19 13.59.27.png

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

dp[(i+A\_j)\%10]+=dp[i]

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

yukicoder contest 259 Review
yukicoder contest 264 Review
yukicoder contest 261 Review
yukicoder contest 267 Review
yukicoder contest 266 Review
yukicoder contest 263 Review
yukicoder contest 268 Review
AtCoder Beginner Contest 152 Review
AtCoder Grand Contest 041 Review
yukicoder contest 265 Participation record
AtCoder Regular Contest 105 Review
yukicoder contest 266 Participation record
yukicoder contest 263 Participation record
yukicoder contest 243 Participation record
yukicoder contest 256 entry record
yukicoder contest 273 Participation record
Keyence Programming Contest 2020 Review
AtCoder Beginner Contest 160 Review
AtCoder Beginner Contest 178 Review
AtCoder Beginner Contest 166 Review
AtCoder Beginner Contest 167 Review
yukicoder contest 252 Participation record
yukicoder contest 259 Participation record
yukicoder contest 249 Participation record
AtCoder Beginner Contest 169 Review
yukicoder contest 271 Participation record
AtCoder Grand Contest 048 Review
AtCoder Beginner Contest 181 Review
yukicoder contest 251 Participation record
AtCoder Beginner Contest 171 Review
AtCoder Beginner Contest 182 Review
yukicoder contest 242 Participation record
AtCoder Beginner Contest 180 Review
yukicoder contest 241 Participation record
yukicoder contest 277 Participation record
AtCoder Beginner Contest 177 Review
yukicoder contest 264 entry record
AtCoder Beginner Contest 168 Review
AtCoder Grand Contest 045 Review
NOMURA Programming Contest 2020 Review
AtCoder Grand Contest 044 Review
yukicoder contest 245 entry record
yukicoder contest 250 entry record
yukicoder contest 254 Participation record
AtCoder Beginner Contest 179 Review
AtCoder Beginner Contest 172 Review
AtCoder Regular Contest 106 Review
yukicoder contest 246 Participation record
yukicoder contest 275 Participation record
yukicoder contest 274 Participation record
AtCoder Beginner Contest 176 Review
yukicoder contest 247 Participation record
AtCoder Grand Contest 046 Review
AtCoder Beginner Contest 175 Review
HHKB Programming Contest 2020 Review
AtCoder Beginner Contest 174 Review
AtCoder Beginner Contest 153 Review
AtCoder Beginner Contest 156 Review
AtCoder Beginner Contest 161 Review
yukicoder contest 261 Participation record
AtCoder Beginner Contest 170 Review