AtCoder Beginner Contest 106 Review of past questions

Time required

スクリーンショット 2020-04-29 14.37.25.png

Impressions

I did it in order higher than the main solution in the D problem and became TLE in Python, so I made it C ++ and speeded it up. This solution is also an important idea, so I would like to learn it.

Problem A

All you have to do is move the road to the end.

answerA.py


a,b=map(int,input().split())
print((a-1)*(b-1))

B problem

Since there are 8 divisors, we will count them using the divisor enumeration function in this article. If you only have how many, you can calculate without preparing an array.

answerB.py


def make_divisors(n):
    divisors=[]
    for i in range(1,int(n**0.5)+1):
        if n%i==0:
            divisors.append(i)
            if i!=n//i:
                divisors.append(n//i)
    return divisors

ans=0
n=int(input())
for i in range(1,n+1):
    ans+=(len(make_divisors(i))==8 and i%2==1)
print(ans)

C problem

Since the subject is operated on the character string 5000 trillion times, each number $ x (\ neq1) $ included in the character string becomes $ x ^ {5000000000000000} $ after 5000 trillion times, so ** $ You can see that it is clearly longer than K $ **. Therefore, if the first character is a character other than 1, you can see that the $ K $ character is $ x $. Similarly, assuming that 1s are consecutive from the 1st character to the $ l $ character, if it is $ l \ geqq K $, the K character will be 1. Conversely, if $ l <K $, the K character is the l + 1 character number.

answerC.py


s=input()
k=int(input())
l=0
for i in s:
    if i=="1":
        l+=1
    else:
        break
print("1" if k<=l else s[l])

D problem

Since the question query asks the interval repeatedly (up to $ 10 ^ 5 $ times), we know that we want to speed up the calculation of the interval here. Therefore, we will consider how to calculate up to $ 10 ^ 3 $ for each query.

Here, when the number of trains passing through the section [$ l, r $] is $ x_ {l, r} $, the trains passing through the section from city $ p_i $ to city $ q_i $. The number of is $ (x_ {p_i, p_i} + x_ {p_i, p_i + 1} +… + x_ {p_i, q_i}) + (x_ {p_i + 1, p_i + 1} +… + x_ {p_i + 1 , q_i}) +… + (x_ {q_i, q_i}) = \ Sigma_ {k = p_i} ^ {q_i} {(\ Sigma_ {l = k} ^ {q_i} {x_ {k, l}})} Since it will be $ (✳︎), I thought that $ k $ (** left end of the section **) should be fixed.

Therefore, when the section through which each train passes is first given in the form of [$ L_i, R_i $], prepare a two-dimensional array train in which the left end of the section is divided by which city, and the $ L_i $ th. Insert the rightmost value $ R_i $ into the array of. Then, after all the insertions, sort each array. Under this, when $ p_i $ and $ q_i $ are given in each question query, ** $ p_i $ th array to $ q_i $ th array (up to N ways) **, respectively ** Just count the number of elements under $ q_i $ ** (∵ (✳︎)). You can do a binary search ($ O (\ log {M}) $) on each ** (sorted) array ** to count how many elements there are. Therefore, the total complexity is $ O (QN log {M}) $. (First and second code, AC for C ++, TLE for Python and PyPy)

Also, if the prepared two-dimensional array train is ** train [$ i ] [ j ]: the number of trains whose section is [ i, j ] **, then [ L_i, R_i ] ], By adding +1 to train [ L_i ] [ R_i $] and considering the cumulative sum, the question query does not perform a binary search for how many elements are under $ q_i $. Since it can be calculated by ** $ O (1) $ **, the amount of calculation is O ($ QN + N ^ 2 $). (Third code, AC with PyPy)

Also, the following code uses bisect_right for binary search. See this article for more information.

answerD_TLE.py


import bisect
n,m,q=map(int,input().split())
train=[[] for i in range(n)]
for i in range(m):
    l,r=map(int,input().split())
    train[l-1].append(r-1)
for i in range(n):
    train[i].sort()
for i in range(q):
    p,q=map(int,input().split())
    ans=0
    for i in range(p-1,q):
        ans+=bisect.bisect_right(train[i],q-1)
    print(ans)

answerD.cc


//Reference: http://ehafib.hatenablog.com/entry/2015/12/23/164517
//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
#define D()
//constant
#define INF 1000000000000 //10^12:Extremely large value,∞
#define MOD 10000007 //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

//↑ Templates from here to above

signed main(){
    ll n,m,q;cin >> n >> m >> q;
    vector<vector<ll>> train(n);
    REP(i,m){
        ll l,r;cin >> l >> r;
        train[l-1].PB(r-1);
    }
    REP(i,n){
        sort(ALL(train[i]));
    }
    REP(i,q){
        ll p,q_;cin >> p >> q_;
        ll ans=0;
        FOR(j,p-1,q_-1){
            ans+=ll(upper_bound(ALL(train[j]),q_-1)-train[j].begin());
        }
        cout << ans << endl;
    }
}

answerD.py


n,m,q=map(int,input().split())
train=[[0]*n for i in range(n)]
for i in range(m):
    l,r=map(int,input().split())
    train[l-1][r-1]+=1
for i in range(n):
    for j in range(n-1):
        train[i][j+1]+=train[i][j]
for i in range(q):
    p,q_=map(int,input().split())
    ans=0
    for j in range(p-1,q_):
        ans+=train[j][q_-1]
    print(ans)

Recommended Posts

AtCoder Beginner Contest 102 Review of past questions
AtCoder Beginner Contest 085 Review of past questions
AtCoder Beginner Contest 062 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 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 089 Review of past questions
AtCoder Beginner Contest 069 Review of past questions
AtCoder Beginner Contest 079 Review of past questions
AtCoder Beginner Contest 056 Review of past questions
AtCoder Beginner Contest 087 Review of past questions
AtCoder Beginner Contest 093 Review of past questions
AtCoder Beginner Contest 046 Review of past questions
AtCoder Beginner Contest 123 Review of past questions
AtCoder Beginner Contest 049 Review of past questions
AtCoder Beginner Contest 078 Review of past questions
AtCoder Beginner Contest 047 Review of past questions
AtCoder Beginner Contest 104 Review of past questions
AtCoder Beginner Contest 057 Review of past questions
AtCoder Beginner Contest 121 Review of past questions
AtCoder Beginner Contest 090 Review of past questions
AtCoder Beginner Contest 103 Review of past questions
AtCoder Beginner Contest 061 Review of past questions
AtCoder Beginner Contest 083 Review of past questions
AtCoder Beginner Contest 124 Review of past questions
AtCoder Beginner Contest 116 Review of past questions
AtCoder Beginner Contest 097 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 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 106 Review of past questions
AtCoder Beginner Contest 122 Review of past questions
AtCoder Beginner Contest 125 Review of past questions
AtCoder Beginner Contest 109 Review of past questions
AtCoder Beginner Contest 118 Review of past questions
AtCoder Beginner Contest 080 Review of past questions
AtCoder Beginner Contest 073 Review of past questions