2019/07/02

AtCoder ABC132 C

$d_i$をソートした後、各KでにぶたんしてARC用問題のうち一番難易度が小さいdの場所を求めた。
そんなことをしなくてもソート後d[N/2] - d[N/2-1]でよい。

Problem, Submissions, Sources

AtCoder ABC132 D

順列。あらかじめパスカルの三角形で${}_nC_r$を求めておく。

まず、赤の間に青を配置するパターン数を求める。
赤と赤の隙間が$n = N - K + 1$つあり、その中に1つ以上の青の塊$r = i$個を並べる。

次に、青をi個の塊に分けるパターン数を求める。
青と青の隙間が$n = K - 1$つあり、それを$r = i - 1$つの壁で分けるイメージ。

この2つを掛けると求める答えとなる。

Problem, Submissions, Sources