ABC113
A
解法
A + B / 2を出力する
ソースコード
B
解法
abs(A - (T - 0.006 * H[i]))が一番小さいiを出力する
ソースコード
C
解法
県ごとに市が誕生した年順にソートして番号を割り振る
実装方針としては以下の通り。
- 1.vector<vector<pair<int,int>>>型の変数vvを用意する。
- vv[i]にpair<int,int>の要素を追加していく。追加される要素の変数名をeとした時、e.firstは年代を表しe.secondはid(何行目に登場したか)を表す。
- vv[i](i = 1 ~ M)をそれぞれソートする。
- 最初の6桁をi, 次の6桁をvv[i][j].firstとしたものをans[vv[i][j].second]に代入する。
(言葉で説明すると難しかったのでソースコードを見てください><)
ソースコード
D
解法
動的計画法を用いて考える。
以下に深さという単語を用いるがここでいう深さとはスタート地点の深さを0として横線を設置可能な場所を超えるたびに深さは1増えるものとする。
dpを以下のように定義する。
- dp[i][h] := スタート地点(縦棒1の一番上)から初めた場合、深さがhのとき縦棒iに達する組み合わせの数。
- dp[1][0] = 1とする。
こう定義した場合dp[i][h]の遷移先は以下の通りになる。
- dp[i - 1][h + 1]
- dp[i][h + 1]
- dp[i + 1][h + 1]
それぞれの遷移が意味することを考えてみる
- dp[i][h]からdp[i-1][h + 1]に遷移するということは深さhとh+1の間の縦棒i-1とiの間に線を引くということである。
すなわち
- dp[i - 1][h + 1] = (1 ~ i-2の間に線を引く組み合わせ数) * (i+1 ~ Wの間に線を引く組み合わせ数) * dp[i][h]
となる。
(xからyまでの間に線を引く組み合わせ数)を求めることを考える。
xからyまでの間に線を引く候補はy - x 個ある。
これはy - x個のボールを隣り合う2つが同時に選ばれないように選ぶ組み合わせと同じである。
func(n)を以下のように定義すると(xからyまでの間に線を引く組み合わせ数)はfunc(y - x)となる。
- n <= 0のとき、 func(n) = 1
- それ以外のとき、 func(n) = func(n-1) + func(n - 2)
すなわち
- dp[i - 1][h + 1] = func(i - 3) * func(W - i - 1) * dp[i][h]
となる。
同様に考えると
- dp[i + 1][h + 1] = func(i - 2) * func(N - i - 2) * dp[i][h]
- dp[i][h + 1] = func(i - 2) * func(W - i - 1) * dp[i][h]
となる。
こうやってdpを求めると答えはdp[K][H]となる。
ソースコード
