AtCoder Beginner Contest 110 Review of past questions

Time required

スクリーンショット 2020-04-25 11.27.48.png

Impressions

I feel that the performance is actually light blue. The policy change went well. I feel that I am often addicted to the method of ** thinking independently for each prime number ** for problems related to divisors. Also, since I haven't organized the prime number library, I plan to organize and post frequently used ones in the near future.

Problem A

The answer is to multiply the largest number by 10 and add the others as they are, but I treated it as a character string without multiplying it by 10.

answerA.py


abc=list(map(int,input().split()))
abc.sort(reverse=True)
print(int(str(abc[0])+str(abc[1]))+abc[2])

B problem

It would be good if there was one possible thing about Z, but we can see that there are three conditions below. ・ $ X \ leqq Z \ leqq Y $ ・ $ Z> max (x_1, x_2,…, x_N) $ ・ $ Z \ leqq min (y_1, y_2,…, y_M) $ Therefore, for Z = X ~ Y, we should search for the existence of $ max (x_1, x_2,…, x_N) <Z \ leqq min (y_1, y_2,…, y_M) $. You can turn the for statement, but you can easily write it using the any operator. Also, I forgot the = of the inequality sign and it was 1WA **. be careful.

answerB.py


n,m,x,y=map(int,input().split())
X=max(list(map(int,input().split())))
Y=min(list(map(int,input().split())))
for z in range(x+1,y+1):
    if X<z<=Y:
        print("No War")
        break
else:
    print("War")

answerB_better.py


n,m,x,y=map(int,input().split())
X=max(list(map(int,input().split())))
Y=min(list(map(int,input().split())))
print("No War" if any([X<z<=Y for z in range(x+1,y+1)]) else "War")

C problem

Focusing on the characters $ S_i, S_j, T_i, T_j $ of two indexes with the strings S and T, consider that $ S_i = T_i $ and $ S_j = T_j $ hold. Let's say that only ** $ S_i = S_j $ holds and is different for any of the other two characters **. At this time, the goal is to hold $ S_i = T_i $, $ S_j = T_j $, but by changing $ S_i $, to $ T_i $, $ S_j $ also becomes $ T_i $, and $ S_j $, Since $ S_i $ also becomes $ T_j $ by the operation to make $ T_j $, in this case, S cannot be matched with T unless ** $ T_i = T_j $ also holds **. Also, even when ** $ T_i = T_j $ holds only **, $ S_i $, can be changed to $ T_i $, but by changing $ S_j $, to $ T_j $, $ S_i $ is the original. Since it changes to $ S_j $, S cannot be matched to T unless ** $ S_i = S_j $ also holds **. So, generalizing this, both $ T_i = T_j $ when ** $ S_i = S_j $ and $ S_i = S_j $ ** when $ T_i = T_j $ must hold. .. Therefore, it is sufficient if the indexes of the same character are collected by S and T (managed by the dictionary), and the set of the collected indexes is all the same. That is, in the first sample, S is `{'a': [0],'z': [1, 2],'e': [3],'l': [4] } ``` T becomes` `{'a': [0],'p': [1, 2],'l': [3],'e': [4]}` You can see that the combinations of, ``` [0], [1,2], [3], [4]` `` are equal. Also, don't forget to s ** ort when fetching only the item from the map (since you don't need the key) ** (this was 1WA).

answerC.py


d,d_=dict(),dict()
s,t=input(),input()
l=len(s)
for i in range(l):
    if s[i] not in d:
        d[s[i]]=[i]
    else:
        d[s[i]].append(i)
for i in range(l):
    if t[i] not in d_:
        d_[t[i]]=[i]
    else:
        d_[t[i]].append(i)
x=[sorted(i[1]) for i in list(d.items())]
y=[sorted(i[1]) for i in list(d_.items())]
x.sort()
y.sort()
print("Yes" if x==y else "No")

D problem

First, since $ a_1, a_2,…, a_N $ is a divisor of M, consider the combination of numbers that appear in $ a_1, a_2,…, a_N $ by using division, etc., and then arrange them in a permutation (multiplicity). I thought it would be better to find it by dividing by).

At this time, I thought that it would be possible to do it efficiently by thinking in ascending or descending order of numbers, but it was implemented as ** each number itself has no meaning ** (∵ just ask for several ways). Is a little troublesome, so I thought about another method.

Here, since $ a_1, a_2,…, a_N $ is a divisor of M, $ is calculated by multiplying the prime numbers $ p_1, p_2,…, p_k $ that appear when ** M is factored into prime numbers. I noticed that a_1, a_2,…, and a_N $ can be expressed ** respectively. In other words, consider writing the following table and defining $ a_i $ ($ i $ = 1 ~ $ N ) for each. ( M = p_1 ^ {q_1} p_2 ^ {q_2}… p_k ^ {q_k} $)

a_1 a_2 a_N sum
$ p_1 $ 0~q_1 0~q_1 0~q_1 q_1
$ p_2 $ 0~q_2 0~q_2 0~q_2 q_2
$ p_k $ 0~q_k 0~q_k 0~q_k q_k

Also, if the number of $ p_j $ ($ j $ = 1 ~ $ k $) is assigned to $ a_1, a_2,…, a_N $, it can be regarded as a different sequence, so each $ p_j $ ($ j $ = =) Consider the number of combinations of allocations of 1 ~ $ k $) to $ a_1, a_2,…, a_N $ and think about multiplication (** Each $ p_j $ ($ j $ = 1 ~) It can be said that the combination of $ k $) is determined independently **.).

Also, as for the combination of allocation of $ p_j $ to $ a_1, a_2,…, a_N $, it is sufficient to consider $ N-1 $ partitions and $ q_j $ balls and consider how to arrange the balls and partitions. $ \ frac {(N-1 + q_j)!} {(N-1)! \ times q_j!} = _ {N-1 + q_j} C _ {N-1} $ That's right (in high school mathematics) Since it is knowledge, I will omit the explanation.)

Furthermore, since $ q_j $ is clearly smaller than 30 (∵ $ 10 ^ 9 <2 ^ {30} $), it is $ N-1 + q_j <10 ^ 6 , and the combination calculation table is O ( N ). You can also make do with the method of initializing with) and performing the combination calculation with O (1) (For the combination calculation, [Kenchon's article](https://drken1215.hatenablog.com/entry/2018/06) / 08/210000).). Therefore, the calculation of how many sequences there are can be done with O ( k $), and k is clearly smaller than 30 (∵ $ 10 ^ 9 <2 ^ {30} $), so the prime factorization by the Prime_factorize function is O ( You can solve this problem with O (max (N, $ \ sqrt {M} $)) in combination with being $ \ sqrt {M} $).

✳︎ Prime number theorem shows that prime numbers are less than x It seems to be about $ \ frac {x} {\ log {x}} $. For this problem, it will be about $ \ frac {x} {\ log {x}} \ fallingdotseq = 4.8 \ times 10 ^ 7 $ from $ x = 10 ^ 9 $. The actual value is $ 5.0847534 \ times 10 ^ 7 $, so you can see that it is a pretty good approximation. (** If I have time, I would like to make a better expression for this approximation. **)

✳︎ The implementation of Prime_factorize is dirty because I wrote it while looking at the spiral book when I was just starting the competition pro. In the near future, I would like to upload an article with a beautiful implementation.

answerD.cc


#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<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
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#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 INF 1000000000000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define MAXRR 1000 //√ Set a number greater than or equal to MAXR
#define MAXR 200000

ll fac[MAXR], finv[MAXR], inv[MAXR];

//Pretreatment to make a table
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAXR; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

//Binomial coefficient calculation
ll COM(ll n,ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


void Prime_factorize(vector<ll>& v,ll n){
    if(n<=1) return;
    ll l=ll(sqrt(n));
    for(ll i=2;i<l+1;i++){
        if(n%i==0){
            Prime_factorize(v,i);Prime_factorize(v,ll(n/i));return;
        }
    }
    v.push_back(n);return;
}

signed main(){
    COMinit();
    map<ll,ll> ma;
    ll n,m;cin >> n >> m;
    vector<ll> vp;
    Prime_factorize(vp,m);
    REP(i,SIZE(vp)){
        ma[vp[i]]++;
    }
    ll ans=1;
    for(auto i=ma.begin();i!=ma.end();i++){
        ans*=COM(i->S+(n-1),n-1);
        ans%=MOD;
    }
    cout << ans << endl;
}

Recommended Posts

AtCoder Beginner Contest 102 Review of past questions
AtCoder Beginner Contest 072 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 127 Review of past questions
AtCoder Beginner Contest 119 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 067 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 081 Review of past questions
AtCoder Beginner Contest 047 Review of past questions
AtCoder Beginner Contest 060 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 126 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 059 Review of past questions
AtCoder Beginner Contest 044 Review of past questions
AtCoder Beginner Contest 083 Review of past questions
AtCoder Beginner Contest 048 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 088 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 068 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