総評
いつも通り、「ABC問題を3完してD問題で一生詰まる」という感じ。順位表を見ていると、目標としている緑〜青帯に近づくためには、D問題の正解率を上げていきたいところ…
コンテストのページはこちら :
A - Beginner
$R_{in}$を内部レーティング、$R_{out}$を外部レーティングとすると、
$$
R_{in} = \max(
R_{out}+100 \times (10-K),
R_{out})
$$
である。
[N,R]=[int(item)for item in input().split()]
print(max(R, R+100*(10-N)))
普通にKの大小で場合分けするのもあり。1
[N,R]=[int(item)for item in input().split()]
print(R if N>=10 else R+100*(10-N))
B - Digits
例えば、100~999は、10進数で3桁の数である。
すなわち、$10^2 $ 〜 $10^3-1$の値は、10進数で3桁となる。
また、1000~9999の値、すなわち$10^3 $ 〜 $10^4-1$の値は、10進数で4桁となる。
2進数で考えてみる（今後、2進数の値の右下に2をつけて、2進数であることを明示する。例えば、10進数の「5」は2進数の「101」だが、これを$101_{2}$のように表す。）
例えば、6を2進数で表すと$110_2$ であり、3桁となる。
もっと言うと、4~7($100_2$~$111_2$)の間の数は、2進数で3桁となる。
ちなみに、4~7は$2^2$〜$2^3-1$とも表せる。
また、8~15($1000_2$~$1111_2$)の間の数は、2進数で4桁となる。
またまたちなみに、8~15は$2^3$〜$2^4-1$とも表せる。
勘のいい読者諸氏は気づいただろうが2、この、(下限〜上限)の上限の部分、$10^3-1$、$10^4-1$、あるいは$2^3-1$、$2^4-1$の指数と、10進数の桁数に、関係性がある。
一般に、10進数のNをK進数に直した時、[桁数、K、N]の間に、
$$
K^{(桁数)-1}\leq N\lt K^{(桁数)}
$$
の関係が成り立つ。
各項に対してKの対数を取ると
$$
(桁数)-1 \leq \log_K(N)\lt (桁数)
$$
となる。
(例えばサンプルの場合(N,K)=(11,2)であり、$(桁数)-1 \leq \log_2(11)=3.45...\lt (桁数)$が成り立つ。$(桁数)$に入りうる整数が4しかないことから、11は2進数で4桁である。)
ここで、
$$
(桁数)-1 =\lfloor \log_K(N) \rfloor
$$
となることに注目すれば、K進数におけるNの桁数は
$$
(桁数)=\lfloor \log_K(N) \rfloor+1
$$
として計算できる。
あとはこれを、プログラムに落とし込むと…
import math
[N,K]=[int(item)for item in input().split()]
#print(math.log(N,K))
print(math.floor(math.log(N,K))+1)
考察
$log_2(11)=3.45...$であった。これは、仮に「小数の桁」の概念が存在すれば、11という数を、2進数で表現するのに必要な桁数が、3.45...になることを意味している。もちろん桁数に小数の概念はないため(ないハズ)、11を十分に表すためには最低でも4桁が必要というわけだ。
情報理論における情報エントロピーの「香り」がする…が、無学なので、よくわからない。とても残念。
C - Rally
この問題で求めるPの座標を、そのまんま$P$とする。改めて書き直すと、求めるPは
$$
P=\min_{P'}\sum^N_{i=1}(X_i-P')^2
$$
となる。
$\sum^N_{i=1}(X_i-P')^2$を式変形すると
\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' + (定数項)\\
&=(P-\frac{X_1+X_2+...+X_n}{n})^2+(定数項)\\
\end{align}\\
$(P-\frac{X_1+X_2+...+X_n}{n})^2\geq0$であり、$P=\frac{X_1+X_2+...+X_n}{n}$のとき、$(P-\frac{X_1+X_2+...+X_n}{n})^2 = 0$となるため、式全体が最小となる。
(もちろんPで微分しても同じ結果が得られる)
D - Bouquet
解き次第記述します。
-
どっちの実装のほうが良いのかは、初心者的にはよくわかりませんな。 ↩