AtCoder Beginner Contest 113
Updated:
Source codes
Solutions
A - Discount Fare
$x + y/2$ を出力する。
B - Palace
まず、
def th(x)
return @t - x * 0.006
end
を作る。あとは (a - th(h[i])).abs が一番大きい index を求めるだけ。
C - ID
pref = Array.new(n){[]} のようにしておき、 pref[pf - 1] << [year, i] のようにする。その後県ごとに sort! して、 ans << [pref[i][j][1], (i+1).to_s.rjust(6, "0") + (j+1).to_s.rjust(6, "0")] としていく。つまり、
for i in 0...n
pref[i].sort!
for j in 0...pref[i].size
ans << [pref[i][j][1], (i+1).to_s.rjust(6, "0") + (j+1).to_s.rjust(6, "0")]
end
end
とする。あとは
ans.sort.each{|cnt, a|
puts a
}
とする。
ポイント
leading zeros は x.to_s.rjust(6, "0") のようにできる。便利。 Ruby の配列は結構時間かかるので注意。私の解答は 1259 ms であった。
D - Number of Amidakuji
横は $0$ - indexed とする。動的計画法による。まず、
$DP[i][j] = $ 縦が $i+1$ cm で、 $0$ が $j$ にたどり着くあみだくじの総数
とする。すると、
- 初期状態： $DP[0][0] = 1$ 、 $DP[0][j] = 0$ ($j \geq 1$) 。
- 答え： $DP[H][K]$ 。
あとは遷移だけ求めればいいのだが、補題を $2$ つ用意する。
第 1 段階
$cnt[i] = $ あみだくじをの横棒を引く「間」の個数が $i$ 個の時に、好きなように横棒を引く場合の数
とする。すると $cnt[0] = 1$, $cnt[1] = 2$ はすぐわかる。また、 $i = 2, 3, \dots$ の場合、 $cnt[i]$ は以下のように求まる： 一番左を引く場合は $cnt[i - 2]$ 個、引かない場合は $cnt[i - 1]$ 個。よって、
\[ cnt[i] = cnt[i - 1] + cnt[i - 2] ~~~~ (i = 2, 3, \dots) \]
である。
第 2 段階
$S[i] = i$ 番目と $i + 1$ 番目の間に横棒を引き、その他は自由に横棒を引く場合の数、
$T[i] = i$ 番目と $i + 1$ 番目の間、及び、 $i - 1$ 番目と $i$ 番目の間に横棒を引かず、その他は自由に横棒を引く場合の数。
と定める。すると、これは $cnt$ を用いて簡単に数え上げることができる。左右にどれだけ自由に横棒が引ける「間」があるのかを数えれば良い。具体的には、
\[
\begin{align}
S[i] &= cnt[\max(x - 1, 0)] cnt[\max(W - x - 3, 0)], \\
T[i] &= cnt[\max(x - 1, 0)] cnt[\max(W - x - 2, 0)]
\end{align}
\]
となる。
遷移
深さ $i$ で $j$ に到達するためには、深さ $i - 1$ で $j, j - 1, j + 1$ のいずれかに到達していなければならない。そこで、遷移は以下の通りになる。ただし第 2, 3 項目の index がはみ出す場合は足さない。
\[ DP[i][j] = DP[i - 1][j] T[i] + DP[i - 1][j - 1] S[j - 1] + DP[i - 1][j + 1] S[j]. \]
以上で解ける。計算量は $O(W + W + HW) = O(HW)$ である。
ポイント
$cnt$ の遷移が最初わからず混乱していた。 $W \leq 8$ なのでその気になれば全部書き出してやろうと思っていたが、実験しているうちにわかった。
植木算的ミスをしないように努力した。サンプルで落ちたが $x - 1$ を $x - 2$ にしているだけだったことに割と早く気がついた。一発で通った。
Others
今日は調子が悪かったが D をなんとか解けた。 B, C ももう少し早く解きたかった。
今日のコンテストは提出が重くて、 D はタイムアウトした。即座に気づいて手動で提出してよかった。