裏紙

ほぼ競プロ、たまに日記

CF 809 C - Find a car

問題

Problem - C - Codeforces

問題概要

 10^9 \times 10^9のグリッドがある。上からi行目、左からj列目のセルを(i,j)と表す( 1 \le i,j \le 10^9)。各グリッドには、条件に従って数字が書き込まれている。その条件とは、

  • (i,j)に書き込むのは、このマスより左側一直線((i,y) (1 \le y \lt j))と上側一直線((x,j) (1 \le x \lt i))の中に現れていない正の整数の中で最小の値(MEX)。

さて、次のようなクエリがある:

  • クエリ (x_1 , y_1 , x_2 , y_2 , k) : 左上 (x_1 , y_1 )、右下 (x_2 , y_2 )の長方形の中でk以下の値についてのみ和を取って、その値を10^9 + 7で割った余りを答えよ。

以上のクエリがq個与えられるので答えよ。

  •  1 \le q \le 10^4
  •  1 \le x_1 \le x_2 \le 10^9
  •  1 \le y_1 \le y_2 \le 10^9
  •  1 \le k \le 2 \dot 10^9

イデア

まず、各グリッドには一体どのような数が入るのかという疑問があるが、結論は(i-1)^(j-1) + 1になる。もうこれは経験則というか知識っぽい感じになってしまうが、(i,j)が依存する位置に注目してみると、これは石山の数が2つのNimと同じだと見なすことができ、またこのMEXがgrundy数と共通する性質を持っているように感じられれば気づけるんだろうか...という気持ちになる。結論ありきだが、帰納的に示すことも出来る。

各グリッドにはどのような値が入るかわかったところで、これらのクエリに答えていく。まず、この長方形の形のクエリは、いつものようにprefixに分解して左上を(1,1)で固定し、4つの領域に分けて足したり引いたりするやつをすることにする。

1スタートで(i-1)^(j-1) + 1  1 \le i \le x , 1 \le j \le yを考えるのは分かりにくいので、i^j + 1  0 \le i \le x-1 , 0 \le j \le y-1を考えることにする。更に、i^j+1を分けて考えると、これは桁dpによって求めることが出来る。

  • cnt[bit][small_x?][small_y?][small_k?] : 上位bit個のビットを決定、それぞれx,y,kよりも小さいことが確定しているかという状態で、グリッドの値がk以下になっているグリッドの個数
  • dp[bit][small_x?][small_y?][small_k?] : 上記の状態で、グリッドの値がk以下になっているグリッドの実際の和

この2つを持つことによって、cntを利用してdpが更新でき、最終的に+1の部分でこのcntを利用することができる。このdpは桁数のオーダーでできるので、クエリ上限が10^4なら十分間に合うと考えられる。

実装(C++)

続きを読む

CF 813 E - Army Creation

問題

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を作る。bi番目の要素の値は、a[i]と同じ値で、k個前にあるindex(b=なければ-1)というものである。すると、i番目の要素が選ばれるということはb_i \lt lであることと、と言える。

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

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

実装(C++)

続きを読む

CF 712 E - Memory and Casinos

問題

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)を求める。これは、kk+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)を求める。これも上で考察したことと同様に、kk+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++)

続きを読む