AtCoder Beginner Contest 117

AtCoder Beginner Contest 117

Source codes

• My submissions (AtCoder)
• My source codes (GitHub)

Solutions

A - Entrance Examination

puts sprintf("%.12f", t/x)

ポイント

Ruby で小数点以下を表示する方法を忘れてしまった。

B - Polygon

l.inject(:+) - l.max > l.max かどうかを判定する。

C - Streamline

$0$-indexed とする。 $N \geq M$ ならば、答えは $0$ である。そこで以下では $N < M$ としてよい。

まず sort することにより、 $X_ 0 < X_ 1 < \dots < X_ {M - 1}$ としてよい。するとこの問題は ${ X_ i \in \mathbb{Z} \mid i \in M }$ を $N$ 個の disjoint union ${ U_ j }_ {j \in N}$ に分解し、 $S = \sum_ {j \in N} (\max U_ j - \min U_ j)$ を最小化する問題だとわかる。最小値を達成する場合、 $0 \leq i_ 0 < i_ 1 < i_ 2 < M$ に対し、 $X_ {i_ 0}, X_ {i_ 2} \in U_ j$ ならば $X_ {i_ 1} \in U_ j$ である。よって $K_ j = \max U_ j - \min U_ j = X_ {\mathop{\mathrm{argmax}} U_ j} - X_ {\mathop{\mathrm{argmin}} U_ j}$ である。ここで $A_ j = \mathop{\mathrm{argmin}} U_ j$, $B_ j = \mathop{\mathrm{argmax}} U_ j$ とおくと、 $K_ j = \sum_ {k = A_ j}^{B_ j - 1} \lvert X_ {k + 1} - X_ k \rvert$ である。つまりこれは $Y_ i = X_ {i + 1} - X_ i$ for $i = 0, \dots, M - 2$ とおくと、答えは ${ Y_ i }$ を小さい方から $M - N$ 個選んだ時の和であると結論づけられる。

D - XXOR

まず

$S[i][0] = i$ 桁目を立たせなかった場合 $i$ 桁目で得られるスコア、
$S[i][1] = i$ 桁目を立たせた場合 $i$ 桁目で得られるスコア。

とし、普通に計算する。次に上から桁 DP をする。

$DP[i][0] = i$ 桁目まで見たときの最高スコア。ただしここまでの進行では $arg = K$ である可能性を残している。
$DP[i][1] = i$ 桁目まで見たときの最高スコア。ただしここまでの進行で $arg < K$ であることが確定している。

とする。すると

• 答え： $\max(DP[0][0], DP[0][1])$
• 初期状態： $DP[60][0] = 0$, $DP[60][1] = -1$

である。遷移は以下の通りである。 $i = 59, 58, \dots, 0$ に対し、

• まず $DP[i][0] = 0$, $DP[i][1] = -1$ とする。
• $K$ の $i$ 桁目が立っている場合、
  • $j = 0$ の進行の場合、$0$ を入れると $j = 1$ に遷移し、 $1$ を入れると $j = 0$ の進行のままである。つまり、 \[ \begin{align} DP[i][1] &\gets \max(DP[i][1], DP[i + 1][0] + S[i][0]), \\
    DP[i][0] &\gets \max(DP[i][0], DP[i + 1][0] + S[i][1]). \end{align} \]
  • $j = 1$ の進行の場合も同様である。 \[ \begin{align} DP[i][1] &\gets \max(DP[i][1], DP[i + 1][1] + S[i][0]), \\
    DP[i][1] &\gets \max(DP[i][1], DP[i + 1][1] + S[i][1]). \end{align} \]
    • ただし、 $DP[i + 1][1] = -1$ の場合は、 $0$ を入れるしか方法がなく、これの代わりに以下を実行する。 \[ DP[i][1] = S[i][0]. \]
• $K$ の $i$ 桁目が立っていない場合、
  • $j = 0$ の進行の場合、$0$ を入れるしかなく $j = 0$ の進行のままである。つまり、 \[ DP[i][0] \gets \max(DP[i][0], DP[i + 1][0] + S[i][0]). \]
  • $j = 1$ の進行の場合、 $0$ を入れても $1$ を入れても良い。 \[ \begin{align} DP[i][1] &\gets \max(DP[i][1], DP[i + 1][1] + S[i][0]), \\
    DP[i][1] &\gets \max(DP[i][1], DP[i + 1][1] + S[i][1]). \end{align} \]
    • ただし、 $DP[i + 1][1] = -1$ の場合は、 $0$ を入れるしか方法がなく、この場合 $j = 0$ 進行である。つまり $j = 1$ で進行することはあり得ない。ゆえに上記を実行しない。

ポイント

正しく遷移を書ききるのが難しかった。 8WA もしてしまった。

Others

もう最悪の成績でした。もっと実装力を磨かねば。

A - sample: 3, tle: 2.000, time: 02:42, from_submit: 77:11
B - sample: 3, tle: 2.000, time: 01:42, from_submit: 75:29
C - sample: 3, tle: 2.000, time: 06:11, from_submit: 69:18
D - sample: 3, tle: 2.000, time: 69:19, from_submit: 00:00