[PYTHON] AtCoder Beginner Contest 152 Review

This time's results

スクリーンショット 2020-01-20 20.56.26.png

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.

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 167 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 Beginner Contest 181 Note
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 102 Review of past questions
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 051 Review of past questions
AtCoder Beginner Contest 127 Review of past questions
AtCoder Beginner Contest 119 Review of past questions
AtCoder Beginner Contest 151 Review of past questions