裏紙

ほぼ競プロ、たまに日記

CF 813 E - Army Creation

Codeforces programming

問題

Problem - E - Codeforces

問題概要

長さnの数列aと整数kが与えられる。次のようなクエリがq個与えられるので、それに答えよ：

  • クエリ(l,r) : 区間 [l , r] について、同じ値はk個までしか選べない時に、最大で何個まで選べるか

(問題を読んでもらうと分かるが、オンラインクエリになっている)

  • 1 \le n \le 100000
  • 1 \le a_i \le 100000
  • 1 \le q \le 100000
  • 1 \le l_i \le r_i \le n

アイデア

オフラインクエリだったら、クエリを先読みしてMoを使ってmapで頻度数えて終わりだったのに...と思った。

クエリごとに、各値について先頭からk個を選ぶということを考えよう。i番目の要素が選ばれるには、そもそも l \le i \le rでないといけないし、lからスタートしてそれまでの間にa_iと同じ値がk個現れていてはいけないということになる。

ここで、新たな数列bを作る。bのi番目の要素の値は、a[i]と同じ値で、k個前にあるindex(ｂ＝なければ-1)というものである。すると、i番目の要素が選ばれるということはb_i \lt lであることと、と言える。

あとは、区間 [l , r] について、b_i \lt lである要素がいくつあるかを数えれば良い。これは、mergesortの過程を保存したようなSegmentTreeなどで各ノードで二分探索をすればできたりする。

今回は(SegmentTreeの実装をサボりたかったので)平方分割した。

実装(C++)

続きを読む

CF 712 E - Memory and Casinos

Codeforces programming

問題

Problem - E - Codeforces

問題概要

n個のカジノが一列に並んでいる(左からi番目のカジノをカジノiと呼ぶ)。カジノiで遊んだ時に、勝つと1つ右に移動する。このときに勝つ確率はp_i (= \frac{a_i}{b_i})である。負けると1つ左に移動する(勝率は1 - p_i)。1番目の左側とn番目の右側は出口である。

また、区間 [ i, j ] に対して、次の条件を満たしている時、区間をdominateすると呼ぶ：

  • i番目のカジノからスタートする。
  • i番目のカジノでは絶対に負けない。
  • j番目のカジノで勝ち、右に移動して終了する。

次の2種類のクエリを考える：

  • クエリ1 : i,a,bが与えられるので、 p_iを\frac{a}{b}にセットする。
  • クエリ2 : l,rが与えられるので、区間 [ l , r ] をdominateできる確率を答える。

以上のクエリが合計でq個与えられるので順に処理せよ。

  • 1 \le n \le 100000
  • 1 \le a_i \lt b_i \le 10^9
  • 1 \le q \le 100000
  • 1 \le a \lt b \le 10^9
  • 1 \le l \le r \le n
  • どの状況でも、 p_i \le p_{i+1}が成り立つ。

アイデア

区間を管理するために、SegmentTreeを使って高速に処理することを考える。区間のマージをどうするかを考える。

  • X(i,j) : 区間 [ i, j ] をdominateできる確率
  • Y(i,j) : 区間 [ i, j ] に対して、jからスタートして、iを超えてしまうこと無く、最終的にはjで勝ち、右に移動できる確率

この上の2つの確率を定義して、区間 [ i, k ] と区間 [ k+1, j ] をマージして区間 [ i, j ] の結果を得ることを考える。x_1 = X(i,k), x_2 = X(k+1,j) , y_1 = Y(i,k), y_2 = Y(k+1,j)とおくと、この4つを使ってX(i,j), Y(i,j)の値を表すことが出来る。

まず、X(i,j)を求める。これは、kとk+1の間を何回またぐことになるかで場合分けをすることが出来る。1回またぐのは、ストレートに両区間でdominateできれば良いのでx_1 x_2となる。次は、3回またぐパターンだが、これは([i,k]をdominate) → ([k+1,j]でdominate失敗) → ([i,k]でkスタートで耐えてk+1へ) → ([k+1,j]でdominate)という流れになる。この確率は、x_1 (1- x_2) y_1 x_2である。以降またぐ回数が5, 7, 9, ... 回と無限に続き、これは初項x_1 x_2、公比 (1- x_2) y_1の無限等比級数であるから、X(i,j) = \frac{x_1 x_2}{1 - (1- x_2) y_1}である。

次に、Y(i,j)を求める。これも上で考察したことと同様に、kとk+1の間を何回またぐことになるか(0, 2, 4, 6, ...回)で場合分けをすることが出来る。0回のときだけは特別で、y_2で、2回以降は初項(1- y_2) y_1 x_2、公比 (1- x_2 ) y_1の無限等比級数であるから、Y(i,j) = y_2 + \frac{(1- y_2) y_1 x_2}{1 - (1- x_2 ) y_1}である。

実装(C++)

続きを読む