Critique du concours AtCoder Beginner Contest 152

Les résultats de cette fois

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.