[PYTHON] AtCoder Beginner Contest 169 Review

This time's results

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>)

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])