総評

いつも通り、「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の大小で場合分けするのもあり。¹

[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$とも表せる。

勘のいい読者諸氏は気づいただろうが²、この、(下限〜上限)の上限の部分、$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

解き次第記述します。

どっちの実装のほうが良いのかは、初心者的にはよくわかりませんな。 ↩
https://twitter.com/kiricat848/status/1246676059606536192 ↩