[PYTHON] AtCoder Débutant Contest 169 Évaluation

Les résultats de cette fois

Impressions de cette époque

Problème C Vous l'avez rendu trop bogué ... Je ne pense pas que ce soit environ 30 minutes, mais je n'y pense pas trop, alors ne soyez pas trop impatient. Aussi,

Problème A

Je viens de faire la multiplication, mais je l'ai mis parce que le code pour remplacer le blanc reçu par entrée avec $ \ times $ et l'exécuter était intéressant (le deuxième code).

A.py

a,b=map(int,input().split())
print(a*b)

A_shortest.py

print(eval(input().replace(" ","*")))

Problème B

Arrêtez quand il dépasse 10 $ ^ {18} $ pour éviter un calcul lent. Python peut faire des ** entiers multi-multiplicateurs et de très grands ** nombres, mais vous devez également savoir que ** les grands nombres seront plus lents **.

B.py

n=int(input())
a=sorted(list(map(int,input().split())))
ans=1
for i in range(n):
    ans*=a[i]
    if ans>10**18:
        print(-1)
        break
else:
    print(ans)

De plus, si vous le forcez sur une ligne, ce sera comme suit (malheureusement le plus court ne peut pas être pris). Il est intéressant que l'instruction for puisse être écrite sur une seule ligne si elle est incluse dans la liste, il peut donc être utile de s'en souvenir, mais cela réduira la lisibilité, donc je pense qu'il vaut mieux l'éviter.

B_oneline.py

t=1;print([t:=(-1,t:=t*int(a))[0<=t<=1e18]for a in[*open(0)][1].split()][-1])

Problème C

Le problème B était simple, mais j'ai passé beaucoup de temps sur le problème C. ** Je pense que c'était une bonne décision de réfléchir à 20 minutes, d'abandonner et de passer au problème suivant **.

J'ai écrit le code suivant pendant le concours. Après tout, dans ce problème, ** la précision des fractions décimales ** est un problème, j'ai donc pensé que je devrais le convertir en entier et le calculer. Pour cette raison, j'ai pris le point décimal et l'ai fait correspondre. (Veuillez également vous référer à cet article et aux commentaires à ce sujet.)

C.py

a,b=input().split()
a=int(a)
b=int("".join(b.split(".")))
#b=int(b.strip("."))
print((a*b)//100)

Vous trouverez ci-dessous un code raccourci basé sur ce code. Personnellement, j'aime la formule de substitution parce qu'elle est à la mode, alors j'ai essayé de l'utiliser.

C_shorter.py

print(int((s:=input())[:-4])*int(s[-4]+s[-2:])//100)

Il semble que vous puissiez utiliser le module Decimal en Python pour faire le calcul exact de la fraction décimale de ce problème **.

C_decimal.py

from decimal import Decimal
a=int(a)
b=Decimal(b)
print(int(a*b))

De plus, ** en utilisant le module de fractions qui calcule les nombres rationnels sans erreur ** peut être calculé comme dans le premier code ci-dessous, et si vous voulez calculer après avoir arrondi $ b $ à un entier Vous pouvez utiliser la fonction d'arrondi pour arrondir à l'entier le plus proche avant de calculer.

Le contenu ci-dessus est décrit en détail en se référant à cet article.

C_fractions.py

from math import floor
from fractions import Fraction
a,b=input().split()
a=int(a)
b=Fraction(b)
print(int(a*b))

C_round.py

a,b=input().split()
a=int(a)
b=round(float(b)*100)
print(a*b//100)

Problème D

Puisque z est représenté par la puissance d'un nombre premier, nous effectuons d'abord la décomposition des facteurs premiers.

La bibliothèque pour la factorisation des nombres premiers est introduite dans cet article, et la méthode de tamisage des ératostènes n'est pas suffisante pour le montant du calcul, donc la méthode de division d'essai est utilisée pour les facteurs premiers Je l'ai démonté.

Lorsqu'il est factorisé en facteurs premiers, $ n = p_1 ^ {q_1} \ times p_2 ^ {q_2} \ times… \ times p_k ^ {q_k} $ ($ p_1, p_2,… p_k $ est un nombre premier $ q_1, q_2,… q_k $ Est un entier supérieur ou égal à 1 $).

Considérez maintenant ** combien d'opérations peuvent être effectuées sur chaque nombre premier **. En considérant le nombre premier $ p_i $ qui n'est inclus dans la factorisation première que $ q_i $, l'entier z sélectionné par l'opération doit être considéré dans l'ordre de $ p_i ^ 1, p_i ^ 2, ... **.

De plus, puisque la somme des épaules de la puissance est $ q_i $, elle peut être reformulée comme ** $ 1 + 2 +… + x \ leqq q_i $ en trouvant le plus grand x ** ($ 1). Dans le cas de + 2 +… + x \ neq q_i $, toutes les différences doivent être ajoutées à x).

Par conséquent, si vous préparez un tableau dans lequel l'élément ** $ l $ ème est $ 1 + 2 +… + l $ **, l'index du plus grand élément sous $ q_i $ dans un tel tableau. Peut être paraphrasé comme demander. Un tel élément peut être reformulé comme l'élément à côté de upper_bound, qui peut être calculé et ajouté pour chaque nombre premier.

(Personnellement, je pense que c'est une croissance considérable que j'ai pu trouver l'idée de la dichotomie ici. Je suis heureux que le résultat de la dévotion soit sorti.)

D.cc

//Comprendre(Ordre alphabétique)
#include<algorithm>//sort,Recherche de bisection,Tel
#include<bitset>//Jeu de bits de longueur fixe
#include<cmath>//pow,journal etc.
#include<complex>//Nombre complexe
#include<deque>//File d'attente d'accès double
#include<functional>//trier plus
#include<iomanip>//setprecision(Erreur de sortie en virgule flottante)
#include<iostream>//Entrée sortie
#include<iterator>//Régler l'opération(Ensemble de produits,Ensemble de somme,Ensemble de différences, etc.)
#include<map>//map(dictionnaire)
#include<numeric>//iota(Génération d'une chaîne entière),pgcd et lcm(c++17)
#include<queue>//queue
#include<set>//ensemble
#include<stack>//empiler
#include<string>//Chaîne
#include<unordered_map>//Carte avec itérateur mais sans ordre
#include<unordered_set>//Il y a un itérateur mais l'ordre n'est pas maintenu défini
#include<utility>//pair
#include<vector>//Tableau de longueur variable

using namespace std;
typedef long long ll;

//macro
//pour la relation de boucle
//L'argument est(Variables dans la boucle,Amplitude de mouvement)Ou(Variables dans la boucle,Premier numéro,Nombre d'extrémités)、のどちらOu
//Les variables de boucle sans D sont incrémentées de 1 et les variables de boucle avec D sont décrémentées de 1.
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//x est un conteneur tel que vector
#define ALL(x) (x).begin(),(x).end() //Je souhaite omettre des arguments tels que le tri
#define SIZE(x) ((ll)(x).size()) //taille à la taille_Changement de t à ll
#define MAX(x) *max_element(ALL(x)) //Trouvez la valeur maximale
#define MIN(x) *min_element(ALL(x)) //Trouvez la valeur minimale
//constant
#define INF 1000000000000 //10^12:Valeur extrêmement élevée,∞
#define MOD 1000000007 //10^9+7:Droit commun
#define MAXR 100000 //10^5:Portée maximale de la baie(Utilisé pour l'énumération des nombres premiers, etc.)
//Abréviation
#define PB push_back //Insérer dans le vecteur
#define MP make_pair //constructeur de paires
#define F first //Le premier élément de paire
#define S second //Le deuxième élément de paire

map<ll,ll> prime;//Carte pour enregistrer combien de chaque nombre premier est sorti par factorisation premier

//O(√n)
//Aligné(la carte est automatiquement organisée par clé)
void prime_factorize(ll n){
    if(n<=1) return;
    ll l=sqrt(n);
    FOR(i,2,l){
        if(n%i==0){
        prime_factorize(i);prime_factorize(ll(n/i));return;
        }
    }
    //Même si la clé n'existe pas dans la carte, elle sera créée automatiquement.
    prime[n]++;return;
}

signed main(){
    //Code pour accélérer la saisie
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n;cin >> n;
    prime_factorize(n);
    vector<ll> num(100);
    REP(i,100){
        num[i]=i+1;
        if(i>0)num[i]+=num[i-1];
    }
    ll ans=0;
    for(auto i=prime.begin();i!=prime.end();i++){
        //cout << i->F << " " << i->S << endl;
        ans+=(ll(upper_bound(ALL(num),i->S)-num.begin()));
    }
    cout << ans << endl;
}

E problème

Cette fois, j'ai pu résoudre le problème que je ne pouvais pas faire avec ARC la dernière fois, ** en trouvant le meilleur et en montrant s'il était approprié **, en quelques minutes.

Tout d'abord, dans ce problème, ** la définition de la valeur médiane est différente selon la régularité de la longueur de la séquence, alors considérons le cas par régularité **.

Comme cela est commun aux deux, $ A_i \ leqq X_i \ leqq B_i $ est vrai, donc la valeur médiane de $ A_1, A_2,…, A_n $ est le centre possible de $ X_1, X_2,…, X_n $. La valeur médiane de $ B_1, B_2,…, B_n $ est ** minimum ** et la valeur médiane de $ X_1, X_2,…, X_n $ est ** maximum **. De plus, ** $ X_i $ peut être déplacé de 1, vous pouvez donc voir qu'il peut représenter toute valeur médiane qui peut être comprise entre les valeurs minimale et maximale **. (J'ai fait une expérience pour le montrer, mais il serait redondant de tout écrire, veuillez donc vous référer à Solution principale pour plus de détails.)

À partir de là, considérons la classification des cas par pair et impair. Tout d'abord, notez que pour les nombres pairs ** la médiane peut être fractionnaire **. C'est-à-dire, comme vous pouvez le voir sur le premier échantillon, lorsque la médiane minimale est $ \ frac {3} {2} $ et le maximum est $ \ frac {5} {2} $, alors $ \ frac { Ce sera 3} {2}, 2, \ frac {5} {2} $, donc vous pouvez compter combien sont possibles par incréments de $ \ frac {1} {2} $. Si c'est impair, la valeur médiane n'est qu'un entier, vous pouvez donc compter combien peuvent être par incréments de 1 $.

Par conséquent, nous implémentons ceci et obtenons:

answerE.py

n=int(input())
a,b=[],[]
for i in range(n):
    c,d=map(int,input().split())
    a.append(c)
    b.append(d)
a.sort()
b.sort()
if n%2==0:
    x=[a[n//2-1],a[n//2]]
    y=[b[n//2-1],b[n//2]]
    print(sum(y)-sum(x)+1)
else:
    x=a[n//2]
    y=b[n//2]
    print(y-x+1)

Problème F

Tout d'abord, pour de tels problèmes, ** énumérer les modèles de tous les ensembles puis compter ** ne suffit pas. Ici, si vous faites attention au ** combien d'éléments sont sélectionnés **, vous pouvez découvrir comment sélectionner l'élément par $ O (NX) $ comme $ O (X) $.

Par conséquent, dans ce problème, considérez que ** $ A_1, A_2,…, A_N $ sont sélectionnés un par un **. Aussi, je veux considérer un sous-ensemble dont la somme est $ S $, donc sélectionnez $ k $ dans le sous-ensemble de $ dp [i] [j] [k] = $ ($ A_1, A_2,…, A_i $). (Le nombre de choses dont la somme est $ j $).

Sous ceci, la réponse de sortie est la partie qui inclut le sous-ensemble $ U $ qui est "$ dp [N] [S] [k] \ fois $ ($ dp [N] [S] [k] $". Le nombre de candidats pour l'ensemble $ T $… ①) »est la somme de $ k $. De plus, ① est $ 2 ^ {N-k} $, donc la réponse est la somme de $ dp [N] [S] [k] \ times 2 ^ {N-k} $ pour $ k $.

Cependant, ** cette solution est $ O (N ^ 2S) $, donc le montant du calcul doit être réduit **. Ici, en considérant s'il est inclus dans le sous-ensemble $ U $ dans la transition de $ DP $, et enfin en considérant le calcul du produit avec le nombre de candidats du sous-ensemble $ T $, il est inefficace, donc ** sous-ensemble Considérez la transition de $ DP $ tout en considérant simultanément ** si elle est incluse dans $ U $ et $ T $. ( Utiliser uniquement s'il est inclus dans le sous-ensemble $ U $ dans la transition → Pouvez-vous penser à utiliser s'il est inclus dans le sous-ensemble $ U $ et le sous-ensemble $ T $ dans la transition? C'est le point ... </ font>)

mod=998244353
n,s=map(int,input().split())
a=list(map(int,input().split()))
dp=[[0]*(s+1) for i in range(n+1)]
dp[0][0]=1
for i in range(n):
    for j in range(s+1):
        if j-a[i]>=0:
            dp[i+1][j]=dp[i][j]*2+dp[i][j-a[i]]
        else:
            dp[i+1][j]=dp[i][j]*2
        dp[i+1][j]%=mod
print(dp[n][s])