アイデア

まず、 $k$ は多いほうが得だから限界まで増やすことにする。

そして、この $a$ と $b$ のペアを、残っている中で、aが最大→bが最小→aが最大→…と交互にルールを適用していって並べていく。例を示すと、 $n=5$ の時は次のようになる。

このように並べることで、局所的に大小関係が発生するので、奇数番目に現れるものを選んでいけば必ず全体の和の半分より大きい値を得られる。 $n$ が偶数の時は、最後のindexを1つ前に詰めておけばよい。

乱択でも通ってしまうっぽい…(submission)。

問題

Problem - D - Codeforces

問題概要

(と)のみで構成される文字列について、次のような長さ $n$ の文字列をregular simple bracket sequences(RSBS)と呼ぶことにする：

空文字列ではない( $n \neq 0$ )
$n$ は偶数で、前半の $\frac{n}{2}$ 文字は全て(、後半の $\frac{n}{2}$ 文字は全て)

例えば((()))はRSBSで、())や(()())はRSBSではない。

今、(と)のみで構成される文字列 $s$ が与えられる。 $s$ からいくつかの文字を削除してRSBSを作成したいと思う時、その方法は何通りあるか、 $10^9+7$ で割った余りを答えよ。

$|s| \le 200000$

アイデア

要するに、 $s$ の部分文字列の中でRSBSの個数を求めたい。まず、自分で考えたこととしては $s$ を先頭から走査していってその時点で左にある(の合計( $x$ 個とする)と右にある)の合計( $y$ 個とする)がわかっていれば、現在注目している箇所の(を必ず採用すると仮定して $O(|s|)$ で組み合わせの総数を列挙できるなーとは思った。けれど、それを全ての(に対してやるのは間に合わない。

実は、1箇所の(に注目して、それより左にある(の個数が $x$ 個でそれより右にある)の個数が $y$ 個の時のRSBSの構成方法の場合の数はもっと簡単に計算できる。

シンプルな場合として、前半 $x$ 文字が(で後半 $y$ 文字が)のような文字列からRSBSを構成することを考えると、この場合は ${} _{x+y} C_x$ 通りになる。なぜこうなるかを、 $x$ 個の1と $y$ 個0を並べる順列に対応付けて考える。

以下に例を示す：

s:       ((())))
select:  ( ( )) 
convert: 0100110

元の文字列が $s$ であるときに、このように部分文字列を構成すると、01はこのように対応させる。これは具体的に何をやっているかというと、部分文字列として採用された(に0、されない(に1、採用された)に1、されない)に0を付与している。この方法によって、0は $y$ 個、1は $x$ 個になる。

採用された(が $z$ 個とすると、採用された)も $z$ 個。つまり採用されない)は $y-z$ 個。ということで、0は合計で $z + (y-z) = y$ 個になる。前から順番に括弧を対応させていくことで一対一にこの文字列が定まるというわけである。

実際に走査していく時は、一番右にある(は必ず採用する仮定があるので、01の対応で言うと0が1つ減ることになる。よって、 ${} _{x+y-1} C_x$ 通りになる。

あとは、はじめに)の数を数えておいて、操作しながら減らしていき、combinationを計算すれば良い。combinationは階乗を事前に計算して、繰り返し二乗法を利用すれば逆元も計算できる。

実装(C++)

裏紙

ほぼ競プロ、たまに日記

CF 798 D - Mike and distribution

問題

問題概要

アイデア

実装(C++)

CF 785 D - Anton and School - 2

問題

問題概要

アイデア

実装(C++)