As usual, it feels like "complete the ABC problem 3 and get stuck with the D problem for the rest of your life." Looking at the standings, I want to raise the accuracy rate of question D in order to get closer to the target green to blue belt ...
Click here for the contest page:
https://atcoder.jp/contests/abc156
A - Beginner
https://atcoder.jp/contests/abc156/tasks/abc156_a
If $ R_ {in} $ is the internal rating and $ R_ {out} $ is the external rating,
Is.
[N,R]=[int(item)for item in input().split()]
print(max(R, R+100*(10-N)))
https://atcoder.jp/contests/abc156/submissions/11763127
There is also a case where the size of K is usually divided. [^ 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
For example, 100 to 999 are decimal numbers with ** 3 digits **.
That is, the value of $ 10 ^ 2 $ to $ 10 ^ 3-1 $ is ** 3 digits ** in decimal.
Also, values from 1000 to 9999, that is, values from $ 10 ^ 3 $ to $ 10 ^ 4-1 $, have ** 4 digits ** in decimal.
Think in decimal (From now on, add 2 to the lower right of the binary value to clearly indicate that it is a decimal number. For example, the decimal number "5" is the binary number "101", but this is Expressed as $ 101_ {2} $.)
For example, if 6 is expressed in binary, it is $ 110_2 $, which is 3 digits.
In other words, the number between 4 and 7 ($ 100_2 $ to $ 111_2 $) is ** 3 digits ** in binary.
By the way, 4 ~ 7 can also be expressed as $ 2 ^ 2 $ ~ $ 2 ^ 3-1 $.
Also, the number between 8 and 15 ($ 1000_2 $ to $ 1111_2 $) is ** 4 digits ** in binary.
By the way, 8 ~ 15 can also be expressed as $ 2 ^ 3 $ ~ $ 2 ^ 4-1 $.
As you may have noticed [^ 2], this, the upper limit of (lower limit to upper limit), $ 10 ^ 3-1 $, $ 10 ^ 4-1 $, or $ 2 ^ 3-1 $, $ 2 There is a relationship between the exponent of ^ 4-1 $ and the number of decimal digits.
Generally, when the decimal number N is converted to a K-number, between [digits, K, N]
Taking the logarithm of K for each term
(For example, in the case of a sample, (N, K) = (11,2), and $ (number of digits) -1 \ leq \ log_2 (11) = 3.45 ... \ lt (number of digits) $ holds. $ ( Number of digits) 11 is a binary number with 4 digits because there are only 4 integers that can fit in $.)
here,
Can be calculated as.
After that, if you put this into the program ...
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
It was $ log_2 (11) = 3.45 ... $. This means that if the concept of "decimal digits" exists, the number of digits required to represent the number 11 in binary is 3.45 ... Of course, there is no concept of decimal numbers in the number of digits (no haze), so at least 4 digits are required to fully represent 11.
There is a "scent" of information entropy in information theory ... but I'm not sure because I'm illiterate. Very disappointing.
C - Rally
https://atcoder.jp/contests/abc156/tasks/abc156_c
Let the coordinates of P obtained in this problem be the same $ P
When $ \ sum ^ N_ {i = 1} (X_i-P') ^ 2 $ is transformed
\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' + (Constant term)\\
&=(P-\frac{X_1+X_2+...+X_n}{n})^2+(Constant term)\\
\end{align}\\
When $ (P- \ frac {X_1 + X_2 + ... + X_n} {n}) ^ 2 \ geq0 $ and $ P = \ frac {X_1 + X_2 + ... + X_n} {n} $ Since $ (P- \ frac {X_1 + X_2 + ... + X_n} {n}) ^ 2 = 0 $, the whole expression is minimized.
(Of course, the same result can be obtained by differentiating with P)
D - Bouquet
I will describe it as soon as it is solved.
[^ 1]: I'm not sure for beginners which implementation is better.
Recommended Posts