読者です 読者をやめる 読者になる 読者になる

裏紙

ほぼ競プロ、たまに日記

CF 798 D - Mike and distribution

問題

Problem - D - Codeforces

問題概要

長さnの数列abが与えられる。

いま、数列のindexをk個選ぶことが出来る。選んだk個のindexをp_1, p_2, \ldots , p_kとするとき、次の条件を満たすようにk個のindexを選べ:

  •  k \le \lfloor \frac{n}{2} \rfloor + 1
  • \displaystyle 2 \sum_{i=1}^{k} a_{p_i} \gt \sum_{i=1}^{n} a_i
  • \displaystyle 2 \sum_{i=1}^{k} b_{p_i} \gt \sum_{i=1}^{n} b_i

このような条件を満たすP = \{ p_1, p_2, \ldots , p_k \}を答えよ。

  •  1 \le n \le 10^5
  •  1 \le a_i \le 10^9
  •  1 \le b_i \le 10^9

イデア

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

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

f:id:imulan:20170422171543p:plain

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

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

実装(C++)

続きを読む

CF 785 D - Anton and School - 2

問題

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 740 D - Alyona and a tree

問題

Problem - D - Codeforces

問題概要

頂点数nの木があり、各頂点には1からnまでの番号が振られている。根の頂点番号は1である。各頂点はそれぞれ整数a_iを持っている。

また、辺には重みがあり、n-1本の辺の情報について、i個目の情報は頂点i+1p_iを結んでおり、その重みはw_iである。

いま、頂点vが頂点u( \neq v)controlしているということを次のように定義する:

  • 頂点uvを根とする部分木に含まれる
  • dist(u,v) \le a_u

各頂点iに対して、その頂点がcontrolしている頂点の個数を求めよ。

  • 1 \le n \le 200000
  • 1 \le a_i \le 10^9
  • 1 \le p_i \le n
  • 1 \le w_i \le 10^9

イデア

controlの条件に関して、uvの距離で定義されているが、今回のグラフは木なので任意の頂点間の距離は根からの距離を利用することで計算できる。根からの各頂点への距離をd_iとすると、controlの定義からuvよりも根から離れていることになるので2番目の条件はd_u - d_v \le a_uとなり、更に変数を揃えるために変形するとd_u - a_u \le d_vということになる。

さて、ここでuを固定して考えてみる。vとしてあり得るのは根からのuへのパス上にある頂点ということになる。根をスタート地点としてd_vは単調増加するので、初めて条件を満たす位置xからuの手前までの区間がこの条件を満たすのでこの区間に+1すればいいということになる。

まず、初めて条件を満たす位置xを探すためには、各頂点からの親をダブリングして保存しておけば二分探索によって探すことが可能になる。

そして、このような区間へのaddはimos法でuの親の頂点に+1,xの親の頂点に-1をしておいて最後に子から親へ足し上げれば答えを出すことが出来る。

実装(C++)

続きを読む