Concours AtCoder pour débutants 156 WriteUp

Commentaire général

Comme d'habitude, cela ressemble à "terminer le problème ABC 3 et rester coincé avec le problème D pour le reste de votre vie." En regardant le classement, je souhaite augmenter le taux de précision de la question D afin de me rapprocher de la ceinture verte à bleue cible ...

Cliquez ici pour la page du concours:

https://atcoder.jp/contests/abc156

A - Beginner

https://atcoder.jp/contests/abc156/tasks/abc156_a

Soit $ R_ {in} $ la note interne et $ R_ {out} $ la note externe

R_{in} = \max( R_{out}+100 \times (10-K), R_{out})

Est.

[N,R]=[int(item)for item in input().split()]
print(max(R, R+100*(10-N)))

https://atcoder.jp/contests/abc156/submissions/11763127


Il existe également un cas où la taille de K est généralement divisée. [^ 1]

[N,R]=[int(item)for item in input().split()]
print(R if N>=10 else R+100*(10-N))

https://atcoder.jp/contests/abc156/submissions/11755645


B - Digits

https://atcoder.jp/contests/abc156/tasks/abc156_b

Par exemple, 100 à 999 sont des nombres décimaux avec ** 3 chiffres **.

Autrement dit, la valeur de 10 $ ^ 2 $ à 10 $ ^ 3-1 $ est de ** 3 chiffres ** en décimal.

De plus, les valeurs comprises entre 1000 et 9999, c'est-à-dire les valeurs comprises entre 10 $ ^ 3 $ et 10 $ ^ 4-1 $, sont ** 4 chiffres ** en décimal.

Pensez en binaire (à partir de maintenant, ajoutez 2 en bas à droite de la valeur binaire pour indiquer clairement qu'il s'agit d'un nombre binaire. Par exemple, le nombre décimal «5» est le nombre binaire «101», mais c'est Exprimé en $ 101_ {2} $.)

Par exemple, si 6 est exprimé en binaire, c'est 110_2 $, soit 3 chiffres.

En d'autres termes, le nombre entre 4 et 7 (100_2 $ à 111_2 $) correspond à ** 3 chiffres ** en binaire.

À propos, 4 ~ 7 peut également être exprimé comme $ 2 ^ 2 $ ~ $ 2 ^ 3-1 $.

De plus, le nombre compris entre 8 et 15 (1000_2 $ à 1111_2 $) est ** 4 chiffres ** en binaire.

À propos, 8 ~ 15 peut également être exprimé comme $ 2 ^ 3 $ ~ $ 2 ^ 4-1 $.

Comme vous l'avez peut-être remarqué [^ 2], ceci, la limite supérieure de (limite inférieure à la limite supérieure), 10 $ ^ 3-1 $, 10 $ ^ 4-1 $ ou 2 $ ^ 3-1 $, 2 $ Il existe une relation entre l'exposant de ^ 4-1 $ et le nombre de chiffres décimaux.

Généralement, lorsque le nombre décimal N est converti en nombre K-aire, entre [chiffres, K, N], $ K ^ {(nombre de chiffres) -1} \ leq N \ lt K ^ {(nombre de chiffres)} $ La relation tient.

Si vous prenez le logarithme de K pour chaque terme $ (Nombre de chiffres) -1 \ leq \ log_K (N) \ lt (Nombre de chiffres) $ Sera.

(Par exemple, dans le cas d'un échantillon, (N, K) = (11,2), et $ (nombre de chiffres) -1 \ leq \ log_2 (11) = 3,45 ... \ lt (nombre de chiffres) $ détient. $ ( Nombre de chiffres) 11 est un nombre binaire à 4 chiffres car il n'y a que 4 entiers qui peuvent tenir dans $.)

ici, $ (Nombre de chiffres) -1 = \ lfloor \ log_K (N) \ rfloor $ Notez que le nombre de chiffres de N dans K-aire est $ (Nombre de chiffres) = \ lfloor \ log_K (N) \ rfloor + 1 $

Peut être calculé comme.

Après cela, si vous mettez cela dans le programme ...

import math
[N,K]=[int(item)for item in input().split()]
#print(math.log(N,K))
print(math.floor(math.log(N,K))+1)

https://atcoder.jp/contests/abc156/tasks/abc156_b

Considération

C'était $ log_2 (11) = 3,45 ... $. Cela signifie que si le concept de «chiffres mineurs» existe, le nombre de chiffres requis pour représenter le nombre 11 en binaire serait de 3,45 ... Bien sûr, il n'y a pas de concept de fractions dans le nombre de chiffres (pas de voile), donc au moins 4 chiffres sont nécessaires pour représenter pleinement 11.

Il y a un «parfum» d'entropie de l'information dans la théorie de l'information ... mais je ne suis pas sûr parce que je suis analphabète. Très décevant.

C - Rally

https://atcoder.jp/contests/abc156/tasks/abc156_c

Soit les coordonnées de P obtenues dans ce problème, les mêmes $ P . Si vous le réécrivez à nouveau, le P souhaité est $ P=\min_{P'}\sum^N_{i=1}(X_i-P')^2 $$ Sera.

Quand $ \ sum ^ N_ {i = 1} (X_i-P ') ^ 2 $ est transformé

\sum^N_{i=1}(X_i-P')^2\\
\begin{align}
&=P^2-2X_1P' + X_1^2\\
&+P^2-2X_2P' + X_2^2\\
&\vdots\\
&+P^2-2X_nP' + X_n^2\\
&=nP^2-2(X_1+X_2+...+X_n)P' + (Terme constant)\\
&=(P-\frac{X_1+X_2+...+X_n}{n})^2+(Terme constant)\\
\end{align}\\

Quand $ (P- \ frac {X_1 + X_2 + ... + X_n} {n}) ^ 2 \ geq0 $ et $ P = \ frac {X_1 + X_2 + ... + X_n} {n} $ Puisque $ (P- \ frac {X_1 + X_2 + ... + X_n} {n}) ^ 2 = 0 $, l'expression entière est minimisée.

(Bien sûr, le même résultat peut être obtenu en différenciant avec P)

D - Bouquet

Je le décrirai dès qu'il sera résolu.

[^ 1]: Je ne suis pas sûr pour les débutants quelle implémentation est meilleure.

Recommended Posts

Concours AtCoder pour débutants 156 WriteUp
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
Critique du concours AtCoder Beginner Contest 152
Critique du concours AtCoder Débutant 160
Critique du concours AtCoder Débutant 178
Concours AtCoder Débutant 180 Remarque
Critique du concours AtCoder pour débutant 166
Concours AtCoder Débutant 182 Remarque
Critique du concours AtCoder
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 pour débutant 177
AtCoder Débutant Contest 168 Critique
Critique du concours AtCoder
Concours AtCoder pour débutants 167
Critique du concours AtCoder pour débutant 172
Concours AtCoder Débutant 183 Remarque
Critique du concours AtCoder
Concours AtCoder Débutant 184 Remarque
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
AtCoder Beginner Contest 181 Rapport de participation
AtCoder Beginner Contest 175 Inscription virtuelle
AtCoder Beginner Contest 161 Rapport de participation
AtCoder Débutant Contest 176 Rapport de participation
AtCoder Beginner Contest 154 Rapport de participation
Note de participation au concours pour débutants AtCoder # 003
AtCoder Beginner Contest 166 Rapport de participation
AtCoder Beginner Contest 153 Rapport de participation
AtCoder Beginner Contest 145 Rapport de participation
AtCoder Débutant Contest 184 Rapport de participation
Rapport de participation au concours AtCoder Débutant 160
AtCoder Beginner Contest 169 Rapport de participation
AtCoder Beginner Contest 178 Rapport de participation
AtCoder Beginner Contest 163 Rapport de participation
AtCoder Beginner Contest 159 Rapport de participation
AtCoder Beginner Contest 164 Rapport de participation
AtCoder Beginner Contest 168 Rapport de participation
Rapport de participation au concours AtCoder Débutant 150
AtCoder Beginner Contest 158 Rapport de participation
Rapport de participation au concours AtCoder Débutant 180
AtCoder Beginner Contest 156 Rapport de participation
AtCoder Beginner Contest 162 Rapport de participation
AtCoder Débutant Contest 157 Rapport de participation