AtCoder Beginner Contest 110 Review of past questions
Time required
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
| … | sum | ||||
|---|---|---|---|---|---|
| $ p_1 $ | 0~ |
0~ |
0~ |
||
| $ p_2 $ | 0~ |
0~ |
0~ |
||
| … | … | ||||
| $ p_k $ | 0~ |
0~ |
0~ |
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
✳︎ 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