[PYTHON] Critique du concours AtCoder Beginner Contest 152

Les résultats de cette fois

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

Impressions de cette époque

Cette fois, je n'ai pas remarqué que le problème E était ** un entier multiple, donc je pouvais le faire en appuyant dessus avec Python **, mais j'ai réalisé que je pouvais le faire après le concours ... De plus, en raison de problèmes et de courses, je n'ai pas pu mettre à jour et me consacrer à l'article du tout. Je ferai de mon mieux à partir d'aujourd'hui.

Problème A

Affaire à savoir s'ils sont identiques

A.py


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

Problème B

Convertit le plus petit nombre en chaîne de caractères et le produit avec la longueur d'un autre nombre.

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)

Problème C

Le moyen le plus simple est de montrer que $ P \ _i \ leqq P \ _j $ vaut pour chaque élément $ P \ _j $ par j = 1 → i, mais c'est $ O (n ^ 2) $. Bien sûr, je ne peux pas arriver à temps. Par conséquent, compte tenu du type d'élément $ P \ _j $ qui est compté en se référant à l'exemple d'exemple, pensant qu'il serait préférable de le faire avec O (n), la condition n'est définie que lorsque la valeur minimale jusqu'à ce point est mise à jour. Il s'avère qu'il sera mis à jour en tant que nombre à respecter. Si vous l'implémentez docilement, ce sera comme suit.

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

Quand j'ai essayé le code golf, c'est devenu comme ça (je ne peux pas obtenir le plus court de Python, c_r_5 est trop fort)

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

Problème D

La politique est la même que la réponse, mais je me suis précipité pour écrire un code étrange pendant le concours. Le premier est le beau code qui a été réécrit après le concours, et le second est le code sale qui a été écrit pendant le concours. Voici la politique. ** Puisque le premier et le dernier chiffres de chaque numéro sont identiques, faites attention uniquement à ce numéro ** et il peut s'agir d'un ensemble de 81 chiffres de (1,1) à (9,9) Je comprends. Quand on prête attention à un certain ensemble de nombres (i, j), c'est (j, i) qui correspond à cet ensemble de nombres. Où $ 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 problème

Dans ce problème, comme vous pouvez le voir d'après la considération, la réponse correcte peut être obtenue en trouvant d'abord le multiple commun minimum de n nombres, puis en divisant le multiple commun minimum par chaque nombre n et en considérant le total. Cependant, dans ce problème ** le multiple commun minimum peut être trop grand pour déborder ** et ** le nombre de chiffres peut être important, nécessitant des calculs plus importants **, ce qui entraîne WA ou TLE dans une implémentation pure. Je vais finir. Ici, en fait, Python (série 3) n'a pas de limite supérieure sur les entiers, et s'il dépasse la mémoire allouée, une nouvelle mémoire est automatiquement allouée, donc le premier problème est résolu. En outre, il est possible de passer le deuxième problème lié à la quantité de calcul dans le délai imparti en appliquant une accélération multiple constante. La mise en œuvre de ceci est la suivante. Le deuxième code est un code qui recherche la simplicité. Au fait, quand j'ai décommenté le premier code, il n'a pas réussi. Intuitivement, j'ai pensé que réduire le nombre de chiffres accélérerait le calcul, mais j'ai trouvé que le calcul du% prend du temps. De plus, pypy ne semblait ralentir aucun des deux codes (pourquoi ...?).

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)

En C ++, j'ai essayé de l'implémenter avec Writer solution. Tout d'abord, le code que vous implémentez vous-même sera le premier code (notez que ce sera TLE). Le problème avec ce problème est que le multiple commun minimum devient trop grand, alors considérons d'abord le multiple commun minimum décomposé en facteurs premiers. Ensuite, lorsque vous vous concentrez sur chaque facteur premier, combien de chaque facteur premier est inclus (lorsqu'il est décomposé en facteurs premiers) est le nombre de chaque facteur premier qui est inclus lorsque vous vous concentrez sur chacun des n nombres. Je sais que c'est bon. En considérant le premier échantillon, $ 2 = 2 ^ 1,3 = 3 ^ 1,4 = 2 ^ 2 $, donc le résultat de la factorisation principale du multiple commun minimum est 12 $ = 2 ^ 2 \ fois 3 ^ 1 $. ..

Par conséquent, commencez par énumérer tous les facteurs premiers qui peuvent être inclus comme facteurs premiers du multiple commun minimum à l'aide du tamis Eratostenes, et vérifiez si ces nombres premiers sont inclus lorsque chaque n nombres est factorisé ( Plus tard, j'ai réalisé que je n'avais pas besoin de créer une table de nombres premiers avec le tamis de champ Eratostenes, et je l'ai corrigée avec le deuxième code.) En effectuant cette vérification dans l'ordre à partir du front, nous avons pu factoriser chaque nombre en facteurs premiers. Ensuite, la valeur maximale du nombre de facteurs premiers lorsque chaque nombre est décomposé en facteurs premiers est comparée pour chaque facteur premier afin d'obtenir le multiple commun minimum sous forme de décomposition des facteurs premiers. Et enfin, vous devez diviser le multiple commun minimum par n nombres et les ajouter, mais si vous essayez simplement de diviser, il débordera, alors j'ai essayé de multiplier chaque nombre dans l'ordre, mais c'est devenu TLE J'ai.

À la suite de diverses enquêtes, j'ai eu l'idée que si $ lcm % mod / A \ _i $ est utilisé pour trouver $ lcm / A \ _i % mod $, il ne débordera pas. .. $ Lcm % mod $ doit être divisible en divisant $ lcm % mod $ par $ A \ _i $ pour que les deux soient égaux. Cependant, puisque $ mod $ est ici un nombre premier, il est premier à $ A \ _i $, et en ajoutant des mods de manière appropriée à $ lcm % mod $, $ lcm % mod $ peut être converti en $ A \ _i $. Vous pouvez le diviser.

Ce serait bien d'implémenter ces choses, mais en fait, tous les calculs sont faits avec trop de mod, donc dans ce problème nous avons une bibliothèque appelée "int (mod int) qui est toujours détenue par trop divisé par mod". Je l'ai utilisé (je l'ai implémenté en faisant référence à cet article).

Aussi, pour la solution de ce problème, veuillez vous référer à l'article de Kenchon.

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

//√ Poussez tout dans un vecteur accessible avec MAX
vector<int> primes;
ll sieve_check[MAX+1]={0};//i-th correspond à l'entier i(1~100000)
//Mettre en œuvre le tamis Eratostenes
void es(){
  //0 est un nombre premier, ici-1 n'est pas un nombre premier
  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;
}

//Dans le cas de n pièces, le lcm est également comparé à 2 pièces et appliqué dans l'ordre
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>;

//Dans le cas de n pièces, le lcm est également comparé à 2 pièces et appliqué dans l'ordre
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;
}

Problème F

J'ai résolu le problème E et je me suis épuisé, alors j'aimerais le résoudre à nouveau quand j'aurai le temps.

Recommended Posts

Critique du concours AtCoder Beginner Contest 152
Critique du concours AtCoder Débutant 160
Critique du concours AtCoder Débutant 178
Critique du concours AtCoder pour débutant 166
AtCoder Débutant Contest 167 Évaluation
Critique du concours AtCoder
AtCoder Débutant Contest 169 Évaluation
Critique du concours AtCoder Débutant 181
AtCoder Débutant Contest 171 Critique
Critique du concours AtCoder pour débutant 182
Critique du concours AtCoder Débutant 180
Critique du concours AtCoder pour débutant 177
AtCoder Débutant Contest 168 Critique
Critique du concours AtCoder
Critique du concours AtCoder pour débutant 172
Critique du concours AtCoder
AtCoder Débutant Contest 175 Critique
Critique du concours AtCoder
Critique du concours AtCoder Beginner Contest 153
Critique du concours AtCoder pour débutant 156
AtCoder Débutant Contest 161 Critique
AtCoder Débutant Contest 170 Critique
Critique du concours AtCoder
AtCoder Débutant Contest 173 Critique
AtCoder Débutant Contest 155 Critique
AtCoder Débutant Contest 162 Évaluation
Concours AtCoder Débutant 177
Concours AtCoder Débutant 179
Concours AtCoder Débutant 172
Concours AtCoder Débutant 180
Concours AtCoder Débutant 173
Concours Atcoder Débutant 153
AtCoder Beginner Contest 066 Revoir les questions précédentes
Concours AtCoder Débutant 181 Remarque
AtCoder Grand Contest 041 Critique
Revue du concours régulier AtCoder 105
Concours AtCoder Débutant 180 Remarque
Concours AtCoder Débutant 182 Remarque
AtCoder Grand Contest 048 Critique
Concours AtCoder pour débutants 156 WriteUp
AtCoder Grand Contest 045 Critique
AtCoder Grand Contest 044 Critique
Concours AtCoder pour débutants 167
Concours AtCoder Débutant 183 Remarque
AtCoder Regular Contest 106 Évaluation
Concours AtCoder Débutant 184 Remarque
AtCoder Grand Contest 046 Critique
Revue du concours régulier AtCoder 104
AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 072 Revue des questions précédentes
AtCoder Beginner Contest 085 Revue des questions précédentes
AtCoder Beginner Contest 062 Revue des questions précédentes
AtCoder Beginner Contest 113 Revue des questions précédentes
AtCoder Beginner Contest 074 Revue des questions précédentes
AtCoder Beginner Contest 051 Revue des questions précédentes
AtCoder Beginner Contest 127 Revue des questions précédentes
AtCoder Beginner Contest 119 Revue des questions précédentes
AtCoder Beginner Contest 151 Revue des questions précédentes