AtCoder Beginner Contest 115
Updated:
Source codes
Solutions
A - Christmas Eve Eve Eve
どんな解法でも良いでしょうけど、私は配列 str に文字列を入れておき、 $str[D - 22]$ を出力した。
B - Christmas Eve Eve
$\sum a _i - \max a _i / 2$ を出力する。
C - Christmas Eve
$h$ は昇順に並べ替えてよろしい。すると答えは以下で求まる。 \[ \min \{ h[K - 1 + i] - h[i] \in \mathbb{N} \mid 0 \leq i \leq N - K \}. \]
D - Christmas
以下を定義する。
$L[i] = $ レベル $i$ のバーガーの高さ、
$Q[i] = $ レベル $i$ のバーガーに含まれるパティの数。
$L[0] = Q[0] = 1$ とし、以下の漸化式を回す。
\[
\begin{align}
L[i] &= 3 + 2L[i - 1], \\
Q[i] &= 1 + 2Q[i - 1].
\end{align}
\]
関数 $f(y, k)$ をレベル $k$ のバーガーを下から $y$ 層食べる時に食べるパティの数と定める。するとこれは以下の通りに再帰的に計算可能である。
\[
f(y, k) =
\begin{cases}
y & k = 0, \\
f(y - 1, k - 1) & y \leq L[k]/2, \\
Q[k - 1] + 1 & y = L[k]/2 + 1, \\
Q[k - 1] + 1 + f(y - L[k]/2 - 1, k - 1) & y \leq L[k] - 1, \\
Q[k] & y = L[k].
\end{cases}
\]
ここで場合分けは、上から順番に見ていくものとした。一応解説：一番上は問題なかろう。 $2$ 行目は、一番下のパンと、レベル $k - 1$ のバーガーを下から $y - 1$ で食べていることになる。 $3$ 行目は、レベル $k - 1$ のバーガーに加え、中間のパティも食べている。 $4$ 行目はそれらに加えさらに レベル $k - 1$ のバーガーを下から $y - L[k]/2 - 1$ 枚食べている。 $5$ 行目は全部食べている。
$f(X, N)$ を求めればよろしい。 $Q$ を予め求めているため、再起で同じレベルの $f$ は $0$ または $1$ 回しか計算していないで済む。ゆえに、計算量は $O(N)$ で済む。
ポイント
最後の部分を $f(N, X)$ にしてしまったので、そこに手間取らなければ多分 20 位以内でした。
Others
21 位でした。エイジシュートまた達成。
A - sample: 2, tle: 2.000, time: 01:48, from_submit: 17:24
B - sample: 2, tle: 2.000, time: 01:05, from_submit: 16:20
C - sample: 2, tle: 2.000, time: 02:40, from_submit: 13:40
D - sample: 3, tle: 2.000, time: 13:40, from_submit: 00:00