AtCoder Beginner Contest 115

更新日時:

AtCoder Beginner Contest 115

ソースコード

解法のメモ

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 位以内でした。

その他

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

コメントする