[PYTHON] AtCoder Anfängerwettbewerb 152 Rückblick

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Dieses Mal bemerkte ich nicht, dass das E-Problem ** eine Ganzzahl mit mehreren Längen war, also konnte ich es durch Drücken mit Python ** tun, aber mir wurde klar, dass ich es nach dem Wettbewerb tun konnte ... Außerdem konnte ich mich aufgrund von Problemen und Besorgungen überhaupt nicht aktualisieren und dem Artikel widmen. Ich werde ab heute wieder mein Bestes geben.

Problem A

Fall, ob sie gleich sind

A.py

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

B-Problem

Konvertiert die kleinere Zahl in eine Zeichenfolge und gibt sie mit der Länge einer anderen Zahl aus.

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

Der einfachste Weg ist zu zeigen, dass $ P \ _i \ leqq P \ _j $ für jedes Element $ P \ _j $ durch j = 1 → i gilt, aber es ist $ O (n ^ 2) $. Natürlich kann ich es nicht rechtzeitig schaffen. Wenn man bedenkt, welche Art von Element $ P \ _j $ unter Bezugnahme auf das Beispielbeispiel gezählt wird und denkt, dass es besser wäre, dies mit O (n) zu tun, wird die Bedingung nur gesetzt, wenn der Mindestwert bis zu diesem Punkt aktualisiert wird. Es stellt sich heraus, dass es als zu treffende Nummer aktualisiert wird. Wenn Sie es gehorsam implementieren, wird es wie folgt sein.

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

Als ich Code Golf ausprobierte, wurde es so (ich kann nicht das kürzeste von Python bekommen, c_r_5 ist zu stark)

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

Die Richtlinie ist die gleiche wie die Antwort, aber ich beeilte mich, während des Wettbewerbs seltsamen Code zu schreiben. Der erste ist der schöne Code, der nach dem Wettbewerb neu geschrieben wurde, und der zweite ist der schmutzige Code, der während des Wettbewerbs geschrieben wurde. Das Folgende ist die Richtlinie. ** Da die erste und die letzte Ziffer jeder Nummer gleich sind, achten Sie nur auf diese Nummer ** und es kann sich um einen Satz von 81 Nummern von (1,1) bis (9,9) handeln. Ich verstehe. Wenn man auf einen bestimmten Satz von Zahlen (i, j) achtet, entspricht (j, i) diesem Satz von Zahlen. Wo $ 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

Wie Sie aus der Überlegung ersehen können, kann bei diesem Problem die richtige Antwort erhalten werden, indem zuerst das minimale gemeinsame Vielfache von n Zahlen ermittelt und dann das minimale gemeinsame Vielfache durch jede n Zahl dividiert und die Summe berücksichtigt wird. Dieses Problem kann jedoch ** ein minimales gemeinsames Vielfaches haben, das zu groß ist und überläuft ** und ** eine große Anzahl von Ziffern, die größere Berechnungen erfordern **, was zu WA oder TLE in einer reinen Implementierung führt. Ich werde am Ende. Tatsächlich hat Python (3er-Serie) keine Obergrenze für Ganzzahlen, und wenn der zugewiesene Speicher überschritten wird, wird automatisch neuer Speicher zugewiesen, sodass das erste Problem gelöst wird. Darüber hinaus ist es möglich, das zweite Problem in Bezug auf den Rechenaufwand innerhalb des Zeitlimits zu lösen, indem eine konstante Mehrfachbeschleunigung angewendet wird. Die Implementierung erfolgt wie folgt. Der zweite Code ist ein Code, der Einfachheit anstrebt. Übrigens, als ich den ersten Code auskommentierte, passierte er nicht. Intuitiv dachte ich, dass das Reduzieren der Anzahl der Stellen die Berechnung beschleunigen würde, aber ich stellte fest, dass die% -Berechnung Zeit braucht. Außerdem schien Pypy keinen der Codes zu verlangsamen (warum ...?).

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 ++ habe ich versucht, es mit Writer-Lösung zu implementieren. Zunächst ist der Code, den Sie selbst implementieren, der erste Code (beachten Sie, dass es sich um TLE handelt). Das Problem bei diesem Problem ist, dass das minimale gemeinsame Vielfache zu groß wird. Betrachten wir also zunächst das minimale gemeinsame Vielfache, das in Primfaktoren zerlegt wird. Wenn Sie sich dann auf jeden Primfaktor konzentrieren, ist wie viele von jedem Primfaktor enthalten (wenn in Primfaktoren zerlegt), wie viele von jedem Primfaktor enthalten sind, wenn Sie sich auf jede von n Zahlen konzentrieren. Ich weiß, dass es gut ist. Betrachtet man die erste Stichprobe, so ist $ 2 = 2 ^ 1,3 = 3 ^ 1,4 = 2 ^ 2 $, so dass das Ergebnis der Primfaktorisierung des minimalen gemeinsamen Vielfachen $ 12 = 2 ^ 2 \ mal 3 ^ 1 $ ist. ..

Zählen Sie daher zunächst mit dem Eratostenes-Sieb alle Primfaktoren auf, die als Primfaktoren des minimalen gemeinsamen Vielfachen enthalten sein können, und prüfen Sie, ob diese Primzahlen enthalten sind, wenn jede n-Zahl faktorisiert wird ( Später stellte ich fest, dass ich mit dem Eratostenes-Feldsieb keine Primzahlentabelle erstellen musste, und korrigierte sie mit dem zweiten Code.) Durch diese Überprüfung in der Reihenfolge von vorne konnten wir jede Zahl in Primfaktoren zerlegen. Als nächstes wird das minimale gemeinsame Vielfache in Form einer Primfaktorzerlegung erhalten, indem der Maximalwert der Anzahl von Primfaktoren verglichen wird, wenn jede Zahl für jeden Primfaktor in Primfaktoren zerlegt wird. Und schließlich müssen Sie das minimale gemeinsame Vielfache durch n Zahlen teilen und addieren, aber wenn Sie einfach versuchen zu teilen, wird es überlaufen, also habe ich versucht, jede Zahl der Reihe nach zu multiplizieren, aber es wurde TLE Ich habe.

Als Ergebnis verschiedener Untersuchungen kam ich auf die Idee, dass bei der Berechnung von $ lcm / A \ _i % mod $, wenn es mit $ lcm % mod / A \ _i $ berechnet wird, es nicht überläuft. .. $ Lcm % mod $ muss teilbar sein, wenn $ lcm % mod $ durch $ A \ _i $ geteilt wird, damit beide gleich sind. Da $ mod $ hier jedoch eine Primzahl ist, ist es eine Primzahl für $ A \ _i $, und durch Hinzufügen von Mods zu $ lcm % mod $ kann $ lcm % mod $ in $ A \ _i $ konvertiert werden. Sie können es teilen.

Es wäre schön, diese Dinge zu implementieren, aber tatsächlich werden alle Berechnungen mit zu viel Mod durchgeführt. In diesem Problem haben wir also eine Bibliothek namens "int (mod int), die immer von zu viel geteilt durch mod gehalten wird". Ich habe es verwendet (ich habe es unter Bezugnahme auf [diesen Artikel] implementiert (http://noshi91.hatenablog.com/entry/2019/03/31/174006)).

Informationen zur Lösung dieses Problems finden Sie in Kenchons Artikel.

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

//√ Schieben Sie alles in einen Vektor, auf den mit MAX zugegriffen werden kann
vector<int> primes;
ll sieve_check[MAX+1]={0};//i-th entspricht der ganzen Zahl i(1~100000)
//Implementieren Sie das Eratostenes-Sieb
void es(){
  //0 ist hier eine Primzahl-1 ist keine Primzahl
  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;
}

//Bei n Stücken wird lcm ebenfalls mit 2 Stücken verglichen und der Reihe nach aufgetragen
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>;

//Bei n Stücken wird lcm ebenfalls mit 2 Stücken verglichen und der Reihe nach aufgetragen
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

Ich habe das E-Problem gelöst und mich erschöpft, daher möchte ich es wieder lösen, wenn ich Zeit habe.