AtCoder Beginner Contest 169 Review

This time's results

スクリーンショット 2020-06-01 12.06.29.png

Impressions of this time

C problem You made too many bugs ... I don't think it's about 30 minutes, but I don't think too much about it, so don't be too impatient. Also,

Problem A

I just do the multiplication, but I put it because the code to replace the blank received by input with $ \ times $ and execute it was interesting (the second code).

A.py


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

A_shortest.py


print(eval(input().replace(" ","*")))

B problem

Try to break when it exceeds $ 10 ^ {18} $ to avoid slow calculation. Python can do ** arbitrary precision integers and very large ** numbers, but you should also be aware that ** large numbers will be slower **.

B.py


n=int(input())
a=sorted(list(map(int,input().split())))
ans=1
for i in range(n):
    ans*=a[i]
    if ans>10**18:
        print(-1)
        break
else:
    print(ans)

Also, if you force it in one line, it will be as follows (unfortunately the shortest cannot be taken). It is interesting that the for statement can be written in one line if it is included in the list comprehension, so it may be useful to remember it, but I think that it should be avoided because it reduces readability.

B_oneline.py


t=1;print([t:=(-1,t:=t*int(a))[0<=t<=1e18]for a in[*open(0)][1].split()][-1])

C problem

Problem B was smooth, but I spent a lot of time on problem C. ** I think it was a good decision to think about 20 minutes and give up and move on to the next problem **.

I wrote the following code during the contest. After all, in this problem, ** precision of decimal numbers ** is a problem, so I thought that I should convert it to an integer and calculate it. For that reason, I took the decimal point and made it correspond. (Also, please refer to this article and comments about this.)

C.py


a,b=input().split()
a=int(a)
b=int("".join(b.split(".")))
#b=int(b.strip("."))
print((a*b)//100)

Below is a shortened code based on this code. I personally like the substitution formula because it's fashionable, so I tried using it.

C_shorter.py


print(int((s:=input())[:-4])*int(s[-4]+s[-2:])//100)

It seems that you can use the Decimal module in Python to make the calculation of decimal decimal precision of this problem exact.

C_decimal.py


from decimal import Decimal
a=int(a)
b=Decimal(b)
print(int(a*b))

In addition, ** using the fractions module that calculates rational numbers without error ** can be calculated as in the first code below, and if you want to calculate after rounding $ b $ to an integer You can use the round function to round to the nearest integer before calculating.

The above contents are described in detail by referring to this article.

C_fractions.py


from math import floor
from fractions import Fraction
a,b=input().split()
a=int(a)
b=Fraction(b)
print(int(a*b))

C_round.py


a,b=input().split()
a=int(a)
b=round(float(b)*100)
print(a*b//100)

D problem

Since z is expressed as a power of a prime number, we first perform prime factorization.

The library for factoring prime factors is introduced in this article, and the method of eratosthenes sieving is not enough for the calculation amount, so the prime factorization method is used. I disassembled it.

When factoring into prime numbers, $ n = p_1 ^ {q_1} \ times p_2 ^ {q_2} \ times… \ times p_k ^ {q_k} $ ($ p_1, p_2,… p_k $ is a prime number $ q_1, q_2,… q_k $ Is an integer greater than or equal to $ 1 $).

Now consider ** how many operations you can do for each prime number **. Considering the prime number $ p_i $, which is included only in $ q_i $ in the prime factorization, the integer z selected by the operation should be considered in order from the one with the smallest power to $ p_i ^ 1, p_i ^ 2,… $. **.

Also, since the sum of the shoulders of the power is $ q_i $, it can be rephrased as ** $ 1 + 2 +… + x \ leqq q_i $ by finding the largest x ** ($ 1). + 2 +… + x \ neq q_i $, just add all the differences to x).

Therefore, if you prepare an array in which the ** $ l $ th element is $ 1 + 2 +… + l $ **, the index of the largest element below $ q_i $ in such an array ** Can be paraphrased as asking for. Such an element can be rephrased as the element next to upper_bound, which can be calculated and added for each prime number.

(Personally, I think it was a considerable growth that I was able to come up with the idea of binary search here. I am glad that the result of devotion came out.)

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

map<ll,ll> prime;//Map that saves how many each prime number came out in prime factorization

//O(√n)
//Aligned(map is automatically sorted by key)
void prime_factorize(ll n){
    if(n<=1) return;
    ll l=sqrt(n);
    FOR(i,2,l){
        if(n%i==0){
        prime_factorize(i);prime_factorize(ll(n/i));return;
        }
    }
    //Even if the key does not exist in the map, it will be built automatically.
    prime[n]++;return;
}

signed main(){
    //Code for speeding up input
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n;cin >> n;
    prime_factorize(n);
    vector<ll> num(100);
    REP(i,100){
        num[i]=i+1;
        if(i>0)num[i]+=num[i-1];
    }
    ll ans=0;
    for(auto i=prime.begin();i!=prime.end();i++){
        //cout << i->F << " " << i->S << endl;
        ans+=(ll(upper_bound(ALL(num),i->S)-num.begin()));
    }
    cout << ans << endl;
}

E problem

This time, I was able to solve the problem that I couldn't do with ARC last time, ** finding the best one and showing the validity **, in a few minutes.

First of all, in this problem, ** the definition of the median is different depending on the evenness of the length of the sequence, so let's consider the case by evenness **.

As is common to both, $ A_i \ leqq X_i \ leqq B_i $ holds, so the median of $ A_1, A_2,…, A_n $ is the possible center of $ X_1, X_2,…, X_n $. The median value of $ B_1, B_2,…, B_n $ is ** minimum ** and the median value of $ X_1, X_2,…, X_n $ is ** maximum **. Furthermore, we can see that ** $ X_i $ can be moved by 1, so it can represent any median that can be between the minimum and maximum values **. (I did an experiment to show this, but it would be redundant if I wrote everything, so please refer to Main Solution for details.)

From here, let's consider the case classification by even and odd. First, note that if it is an even number, ** the median can be a decimal **. That is, as you can see from the first sample, when the median minimum is $ \ frac {3} {2} $ and the median is $ \ frac {5} {2} $, then $ \ frac { It will be 3} {2}, 2, \ frac {5} {2} $, so you can count how many are possible in $ \ frac {1} {2} $ increments. If it is odd, the median is only an integer, so you can count how many can be in $ 1 $ increments.

Therefore, we implement this and get:

answerE.py


n=int(input())
a,b=[],[]
for i in range(n):
    c,d=map(int,input().split())
    a.append(c)
    b.append(d)
a.sort()
b.sort()
if n%2==0:
    x=[a[n//2-1],a[n//2]]
    y=[b[n//2-1],b[n//2]]
    print(sum(y)-sum(x)+1)
else:
    x=a[n//2]
    y=b[n//2]
    print(y-x+1)

F problem

First of all, in such a problem, ** enumerating the patterns of all sets and then counting ** is not enough **. Here, if you pay attention to ** how many elements are selected **, you can find out how to select the element by $ O (NX) $ as $ O (X) $.

Therefore, in this problem, consider ** $ A_1, A_2,…, A_N $ being selected one by one **. Also, I want to consider a subset whose sum is $ S $, so select $ k $ from the subset of $ dp [i] [j] [k] = $ ($ A_1, A_2,…, A_i $). (The number of things whose sum is $ j $).

Under this, the output answer is the part that includes the subset $ U $ that is "$ dp [N] [S] [k] \ times $ ($ dp [N] [S] [k] $". The number of candidates for the set $ T $… ①) ”is the sum of $ k $. Also, ① is $ 2 ^ {N-k} $, so the answer is the sum of $ dp [N] [S] [k] \ times 2 ^ {N-k} $ for $ k $.

However, ** this solution is $ O (N ^ 2S) $, so the amount of calculation must be reduced **. Here, considering whether it is included in the subset $ U $ in the transition of $ DP $, and finally considering the calculation of the product with the number of candidates of the subset $ T $, it is inefficient, so ** subset Consider the transition of $ DP $ while simultaneously ** considering whether it is included in $ U $ and $ T $. ( Use only whether it is included in the subset $ U $ in the transition → Can you think of using whether it is included in the subset $ U $ and the subset $ T $ in the transition? That's the point ... </ font>)

That is, if we focus on $ A_i $, a pattern that is not included in the subset $ T $ and not included in the subset $ U $ ... (1), also included in the subset $ T $ and also in the subset $ U $ Included patterns… (2), Patterns included in subset $ T $ but not included in subset $ U $… Consider the transition of $ DP $ for the three patterns (3).

Here, the number of subsets $ T $ including the subset $ U $ such that the sum of the subsets of $ dp [i] [j] = $ ($ A_1, A_2,…, A_i $ is $ j $). ), It is not difficult for the DP transition to be as shown in the figure below.

IMG_0397.PNG

If this $ DP $ is improved, it will be $ O (NS) $ and the program will be fast enough.

There is a solution for formal power series here, and it seems that I can understand it somehow, but it seems to be heavy once I start studying, so I will add it later or explain it in another article. Also, [maspy's article](https://maspypy.com/atcoder-%e5%8f%82%e5%8a%a0%e6%84%9f%e6%83%b3-2020-05-31abc- Please also refer to 169).

answerF.py


mod=998244353
n,s=map(int,input().split())
a=list(map(int,input().split()))
dp=[[0]*(s+1) for i in range(n+1)]
dp[0][0]=1
for i in range(n):
    for j in range(s+1):
        if j-a[i]>=0:
            dp[i+1][j]=dp[i][j]*2+dp[i][j-a[i]]
        else:
            dp[i+1][j]=dp[i][j]*2
        dp[i+1][j]%=mod
print(dp[n][s])

Recommended Posts

AtCoder Beginner Contest 152 Review
AtCoder Beginner Contest 160 Review
AtCoder Beginner Contest 178 Review
AtCoder Beginner Contest 166 Review
AtCoder Beginner Contest 164 Review
AtCoder Beginner Contest 169 Review
AtCoder Beginner Contest 181 Review
AtCoder Beginner Contest 171 Review
AtCoder Beginner Contest 182 Review
AtCoder Beginner Contest 180 Review
AtCoder Beginner Contest 177 Review
AtCoder Beginner Contest 168 Review
AtCoder Beginner Contest 179 Review
AtCoder Beginner Contest 172 Review
AtCoder Beginner Contest 176 Review
AtCoder Beginner Contest 175 Review
AtCoder Beginner Contest 174 Review
AtCoder Beginner Contest 153 Review
AtCoder Beginner Contest 156 Review
AtCoder Beginner Contest 161 Review
AtCoder Beginner Contest 170 Review
AtCoder Beginner Contest 165 Review
AtCoder Beginner Contest 173 Review
AtCoder Beginner Contest 155 Review
AtCoder Beginner Contest 162 Review
AtCoder Beginner Contest 177
AtCoder Beginner Contest 179
AtCoder Beginner Contest 172
AtCoder Beginner Contest 180
AtCoder Beginner Contest 173
Atcoder Beginner Contest 153
AtCoder Beginner Contest 066 Review past questions
AtCoder Grand Contest 041 Review
AtCoder Regular Contest 105 Review
AtCoder Beginner Contest 187 Note
AtCoder Beginner Contest 180 Note
AtCoder Beginner Contest 182 Note
AtCoder Grand Contest 048 Review
AtCoder Beginner Contest 156 WriteUp
AtCoder Grand Contest 045 Review
AtCoder Grand Contest 044 Review
Solve AtCoder Beginner Contest 100-102
AtCoder Beginner Contest 167 Memorandum
AtCoder Beginner Contest 183 Note
AtCoder Regular Contest 106 Review
AtCoder Beginner Contest 184 Note
AtCoder Grand Contest 046 Review
AtCoder Regular Contest 104 Review
AtCoder Beginner Contest 188 Note
AtCoder Beginner Contest 072 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 127 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