AtCoder Beginner Contest 113

更新日時:

AtCoder Beginner Contest 113

ソースコード

解法のメモ

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$ にしているだけだったことに割と早く気がついた。一発で通った。

その他

今日は調子が悪かったが D をなんとか解けた。 B, C ももう少し早く解きたかった。

今日のコンテストは提出が重くて、 D はタイムアウトした。即座に気づいて手動で提出してよかった。

コメントする