[PYTHON] AtCoder Beginner Contest 152 Review

This time's results

Impressions of this time

This time, I didn't notice that the E problem was ** a multiple precision integer, so I could do it by pressing it with Python **, but I realized that I could do it after the contest ... Also, due to issues and errands, I was not able to update and devote myself to the article at all. I will do my best again from today.

Problem A

Case by whether they are the same

A.py

n,m=map(int,input().split())
if m==n:
    print("Yes")
else:
    print("No")

B problem

Converts the smaller number to a character string and outputs it with the length of another number.

B.py

a,b=map(int,input().split())
if a>b:
    print(str(b)*a)
elif a<b:
    print(str(a)*b)
else:
    print(str(a)*a)

C problem

The easiest way is to show that $ P \ _i \ leqq P \ _j $ holds for each element $ P \ _j $ by j = 1 → i, but it is $ O (n ^ 2) $. Of course not in time. Therefore, considering what kind of element $ P \ _j $ is counted by referring to the sample example, thinking that it would be better to do it with O (n), the condition is set only when the minimum value up to that point is updated. It turns out that it is updated as a number to meet. If you implement it obediently, it will be as follows.

C.py

n=int(input())
p=[int(i) for i in input().split()]
mi=10000000
x=[0]*n
for i in range(n):
    if mi>p[i]:
        x[i]=1
        mi=p[i]
print(sum(x))

When I tried to play code golf, it became like this (I can't get the shortest of Python, c_r_5 is too strong)

C2.py

n,*p=map(int,open(0).read().split())
for i in range(1,n):p[i]=min(p[~-i],p[i])
print(len(set(p)))

D problem

The policy is the same as the answer, but I rushed to write strange code during the contest. The first is the beautiful code that was rewritten after the contest, and the second is the dirty code that was written during the contest. The following is the policy. ** Since the first digit and the last digit of each number are the same, pay attention only to that number ** and it can be a set of 81 numbers from (1,1) to (9,9) I understand. When paying attention to a certain set of numbers (i, j), it is (j, i) that corresponds to that set of numbers. Where $ i \ neq j $

answerD_better.py

n=int(input())
check=[[0]*9 for i in range(9)]
for i in range(1,n+1):
    s=str(i)
    s1=int(s[0])-1
    s2=int(s[-1])-1
    if s2==-1:continue
    check[s1][s2]+=1
cnt=0
for i in range(9):
    for j in range(9):
        cnt+=check[i][j]*check[j][i]
print(cnt)

answerD.py

n=int(input())
check1=[[i,i,0] for i in range(1,10)]
check2=[[i,j,0] for i in range(1,10) for j in range(i+1,10)]
l=len(check2)
check3=[[check2[i][1],check2[i][0],0] for i in range(l)]

for i in range(1,n+1):
    s=str(i)
    s1=int(s[0])
    s2=int(s[-1])
    if s2!=0:
        if s1==s2:
            check1[s1-1][2]+=1
        elif s1<s2:
            x=[0,8,15,21,26,30,33,35]
            check2[x[s1-1]+(s2-s1-1)][2]+=1
        else:
            x=[0,8,15,21,26,30,33,35]
            check3[x[s2-1]+(s1-s2-1)][2]+=1
cnt=0
for i in range(9):
    cnt+=(check1[i][2])*(check1[i][2])
for i in range(l):
    cnt+=2*(check2[i][2]*check3[i][2])
print(cnt)

E problem

In this problem, as you can see from the consideration, the correct answer can be obtained by first finding the least common multiple of n numbers and then dividing the least common multiple by each n number and considering the total. However, in this problem, the least common multiple may be too large to overflow ** and the number of digits may be large, which may require a larger calculation **, resulting in WA or TLE in a pure implementation. I will end up. Here, in fact, Python (3 series) has no upper limit on integers, and if the allocated memory is exceeded, new memory is automatically allocated, so the first problem is solved. Furthermore, the second problem related to the amount of calculation can be passed within the time limit by multiplying the speed by a constant. The implementation of this is as follows. The second code is a code that pursues simplicity. By the way, when I uncommented the first code, it didn't pass. Intuitively, I thought that reducing the number of digits would speed up the calculation, but I found that the% calculation takes time. In addition, pypy didn't seem to slow down either code (why ...?).

answerE.py

from fractions import gcd

def lcm(c,d):
    return c//gcd(c,d)*d
mod=10**9+7

n=int(input())
a=[int(i) for i in input().split()]
l=a[0]
for i in range(1,n):
    l=lcm(l,a[i])
ans=0
for i in range(n):
    ans+=l//a[i]
    #ans%=mod
print(ans%mod)

python:answerE.better.py

from fractions import gcd
from functools import reduce
mod=10**9+7
n=int(input())
a=[int(i) for i in input().split()]
l=reduce(lambda x,y:x//gcd(x,y)*y,a)
ans=sum(map(lambda x:l//x,a))
print(ans%mod)

In C ++, I tried to implement it with Writer solution. The code you implement yourself first is the first code (note that it is a TLE). The problem with this problem is that the least common multiple becomes too large, so let's first consider the least common multiple factored into prime factors. Then, when focusing on each prime factor, how many of each prime factor is included (when factoring into prime factors) is considered as to how many of each prime factor is included when focusing on each of n numbers. I know it's good. Considering the first sample, $ 2 = 2 ^ 1,3 = 3 ^ 1,4 = 2 ^ 2 $, so the result of factoring the least common multiple into prime factors is $ 12 = 2 ^ 2 \ times 3 ^ 1 $. ..

Therefore, first enumerate all the prime numbers that may be included as prime factors of the least common multiple using the Eratosthenes sieve, and check whether those prime numbers are included when each n numbers are factored (). Later, I realized that I didn't need to make a prime number table with the Eratosthenes field sieve, and corrected it with the second code.) By performing this check in order from the front, each number could be factored into prime factors. Next, the least common multiple is obtained in the form of prime factorization by comparing the maximum value of the number of prime factors when each number is factorized for each prime factor. And finally, you have to divide the least common multiple by n numbers and add them, but if you simply try to divide, it will overflow, so I tried to multiply each number in order, but it became TLE. I have.

After a lot of research, I came up with the idea that if you use $ lcm % mod / A \ _i $ to find $ lcm / A \ _i % mod $, it will not overflow. .. To be equivalent, $ lcm % mod $ must be divisible when dividing $ lcm % mod $ by $ A \ _i $. However, since $ mod $ is a prime number here, it is relatively prime to $ A \ _i $, and by adding mods appropriately to $ lcm % mod $, $ lcm % mod $ can be converted to $ A \ _i $. You can divide it.

It would be nice to implement these things, but in fact, all calculations are done with too much mod, so in this problem we have a library called "int (mod int) that is always held by too much divided by mod". I used it (Implemented by referring to this article).

Also, for the solution of this problem, please refer to Kenchon's article.

answerE_TLE.cc

#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<utility>
#include<map>
using namespace std;
typedef long long ll;
#define MAX 1000000

//√ Push everything into a vector that can be accessed with MAX
vector<int> primes;
ll sieve_check[MAX+1]={0};//i-th corresponds to integer i(1~100000)
//Implement the Eratosthenes sieve
void es(){
  //0 is a prime number, here-1 is not a prime number
  for(ll i=2;i<=1000;i++){
    if(sieve_check[i]==0){
      primes.push_back(i);
      for(ll j=1;j<=floor(MAX/i);j++){
        if(j!=1) sieve_check[j*i]=-1;
      }
    }
  }
}

ll modpow(ll a,ll n,ll mod){
  ll res = 1;
  while(n > 0){
    if(n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

//In the case of n pieces, lcm is also compared with 2 pieces and applied in order.
signed main(){
  ll mod=pow(10,9)+7;
  int n;cin >> n;
  vector<ll> a(n);for(int i=0;i<n;i++){cin >> a[i];}
  es();
  int x=primes.size();
  vector< map<ll,int> > prime_factors(n);
  for(int i=0;i<n;i++){
    for(int j=0;j<x;j++){
      while(a[i]%primes[j]==0){prime_factors[i][primes[j]]++;a[i]/=primes[j];}
    }
    if(a[i]!=1) prime_factors[i][a[i]]=1;
  }
  map<ll,int> lcm_all;
  for(ll i=0;i<n;i++){
    map<ll,int> now=prime_factors[i];
    for(auto& now_sub : now){
      lcm_all[now_sub.first]=max(now_sub.second,lcm_all[now_sub.first]);
    }
  }
  ll cnt=0;
  for(int i=0;i<n;i++){
    ll cnt_sub=1;
    map<ll,int> now=prime_factors[i];
    for(auto& lcm_all_sub : lcm_all){
      cnt_sub*=modpow(lcm_all_sub.first,lcm_all_sub.second-now[lcm_all_sub.first],mod);cnt_sub%=mod;
    }
    cnt+=cnt_sub;
    cnt%=mod;
  }
  cout << cnt << endl;
}

answerE.cc

#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<utility>
#include<map>
#include<cstdint>
using namespace std;
typedef long long ll;
const ll MOD=1000000007;

template<ll mod> class modint{
public:
  ll val=0;
  constexpr modint(ll x=0) noexcept : val(x%mod){
    while(x<0)x+=mod;
  }
  constexpr ll getmod(){return mod;}
  constexpr ll getvalue(){return val;}
  constexpr const ll &value() const noexcept {return val;}
  constexpr modint operator+(const modint &r) const noexcept{return modint(*this)+=r;}
  constexpr modint operator-(const modint &r) const noexcept{return modint(*this)-=r;}
  constexpr modint operator*(const modint &r) const noexcept{return modint(*this)*=r;}
  constexpr modint operator/(const modint &r) const noexcept{return modint(*this)/=r;}
  constexpr modint& operator+=(const modint &r) noexcept{
    val += r.val;
    if(val >= mod){
      val -= mod;
    }
    return *this;
  }
  constexpr modint& operator-=(const modint &r) noexcept{
    if(val < r.val){
      val += mod;
    }
    val -= r.val;
    return *this;
  }
  constexpr modint& operator*=(const modint &r) noexcept{
    val = val * r.val % mod;
    return *this;
  }
  constexpr modint& operator/=(const modint &r) noexcept{
    ll a=r.val,b=mod,u=1,v=0;
    while (b) {
      ll t = a/b;
      a -= t*b;swap(a,b);
      u -= t*v;swap(u,v);
    }
    val = val * u % mod;
    if(val < 0)val += mod;
    return *this;
  }
  constexpr bool operator == (const modint& r) const noexcept {
    return this->val == r.val;
  }
  constexpr bool operator < (const modint& r) const noexcept {
    return this->val < r.val;
  }
  constexpr bool operator != (const modint& r) const noexcept {
    return this->val != r.val;
  }
  friend constexpr ostream& operator << (ostream &os, const modint<mod>& x) noexcept {
    return os << x.val;
  }
  friend constexpr modint<mod> modpow(const modint<mod> &a,ll n) noexcept {
    if(n == 0) return 1;
    auto t = modpow(a, n / 2);
    t = t * t;
    if(n & 1) t = t * a;
    return t;
  }
};

using mint = modint<MOD>;

//In the case of n pieces, lcm is also compared with 2 pieces and applied in order.
signed main(){
  int n;cin >> n;
  vector<ll> a(n);for(int i=0;i<n;i++){cin >> a[i];}
  vector< map<mint,int> > prime_factors(n);
  for(int i=0;i<n;i++){
    for(int j=2;j<=1000;j++){
      while(a[i]%j==0){prime_factors[i][mint(j)]++;a[i]/=j;}
    }
    if(a[i]!=1) prime_factors[i][mint(a[i])]=1;
  }
  map<mint,int> lcm_all;
  for(ll i=0;i<n;i++){
    map<mint,int> now=prime_factors[i];
    for(auto& now_sub : now){
      lcm_all[now_sub.first]=max(now_sub.second,lcm_all[now_sub.first]);
    }
  }
  mint lcm_ans=mint(1);
  for(auto& lcm_all_sub : lcm_all){
    lcm_ans*=modpow(lcm_all_sub.first,lcm_all_sub.second);
  }
  mint cnt=0;
  for(int i=0;i<n;i++){
    mint cnt_sub=lcm_ans;
    map<mint,int> now=prime_factors[i];
    for(auto& now_sub : now){
      cnt_sub/=modpow(now_sub.first,now_sub.second);
    }
    cnt+=cnt_sub;
  }
  cout << cnt << endl;
}

F problem

I have solved the E problem and have exhausted myself, so I would like to solve it again when I have time.