2017-02-04

FHC 2017 R2 C - Fighting all the Zombies

programming FHC

問題

Fighting all the Zombies | Facebook Hacker Cup 2017 Round 2

問題概要

RPGをやっている。主人公は魔法使いである。

$N$ 体のゾンビがいる洞窟がある。 $i$ 番目のゾンビの強さは $i$ である。いま、レベリングのために、この洞窟を $M$ 回周回しようと考えている。この時、主人公は洞窟に入るたびに $N$ 体全てのゾンビを倒して洞窟から出てきて、再び洞窟に入ると $N$ 体全てのゾンビが復活している。

主人公は、 $N$ 本の杖を持っている。 $i$ 番目の杖の強さは $i$ である。それぞれの杖は洞窟に入るごとに一度しか使えず、杖を使うと一体のゾンビを倒すことが出来る。

はじめ、主人公は $N$ 種類の呪文を覚えている。 $i$ 番目の呪文は強さ $i$ を持っており、それは $i$ 番目の杖を使うことで発動できる。

さて、主人公は $M$ 回この洞窟にいくことになるが、 $i$ 回目に洞窟に入る前に新たに $S_i$ 個の呪文を覚える。その $S_i$ 個の呪文の強さは全て $W_i$ であり、全て強さ $Z_i$ の杖によって発動可能な呪文である。ただし、呪文の強さと杖の強さに大きな差はなく、具体的には $| W_i - Z_i | \le 1$ を満たす。また、全ての呪文は区別して考える。

この状況で、 $i$ 回目に洞窟にいった時の $N$ 体のゾンビの倒し方が何通りあるか知りたい。この時、少なくとも1体のゾンビに対して別の呪文を使うような組み合わせは区別して数える。

$i$ 回目に洞窟に行った時のゾンビの倒し方の組み合わせが $P_i$ 通りあるとしたときの $\displaystyle \sum_{i=1}^{M} P_i$ を $10^9 + 7$ で割った余りを答えよ。

$1 \le N, M \le 800000$
$1 \le W_i , Z_i \le N$
$1 \le S_i \le 10^9$

アイデア

設定が複雑で分かりにくい。1つずつまとめていく。

まず、 $I$ 番目のゾンビを倒すためには強さ $i$ の呪文しか使えないということなので、初期状態では組み合わせは1通りしかない。また、杖に注目すると、新しい呪文を覚えていったとしても、 $i$ 番目の杖で発動可能な呪文の強さは $i-1$ か $i$ か $i+1$ の3種類に限られるということが分かる。

さて、強さ1の杖から順番に、どの強さの呪文を発動するかを考えていく。1の杖では、(使える呪文が1つ以上あるのなら)強さ1か2の呪文を使うことが出来る。そして、2,3,4,… と弱い方から順に呪文の強さを選んでいき、次に強さ $i$ の杖でどの呪文を発動するかということを考えると、この状況で強さ $i+1$ が埋まっていることは有り得ないが、 $i$ と $i+1$ が埋まっていることはあり得る。このことから次のようなDPを考える。

dp[i][prev][now] = i番目の杖に注目していて、強さi-1の呪文は既に使われたか(prev)、強さiの呪文は既に使われたか(now)という状況の時の組み合わせの個数

初期状態としてはdp[1][0][1]=1ということになり、最終的には求めたいものはdp[N+1][1][0]となる。ただ、このDPの計算を $M$ 回もやろうとすると $O(NM)$ となって間に合わない。ただ、遷移に注目してみると周回している間、その1回1回の間で遷移が変化するのは1箇所だけなので、その無駄をなくしてなんとかしたいと考えられる。

ここで、DPのiとi+1の間の遷移がどうなっているのかを図で書いてみるとこのようになる(はじめはdp[0][0][1]=1から始まっているので、意味のある遷移だけを書いた)。

f:id:imulan:20170202002346p:plain

この図を見て分かる通り、dpとして式を定義したはいいものの、結局dp[*][0][1]とdp[*][1][0]しか必要ないことに気づく。ということで、前者を $a_i$ ,後者を $b_i$ と置く。そして、杖 $i$ が $i-1, i, i+1$ のそれぞれの強さの呪文をいくつずつ使えるのかを $C_{i,0} , C_{i,1}, C_{i,2}$ とすると、次のような漸化式が成り立つ。

$a_{i+1} = b_i * C_{i,2}$

$b_{i+1} = a_i * C_{i,0} + b_i * C_{i,1}$

これらは行列の形に直せて、 $a_1 = 1, b_1 = 0$ という初期値も合わせると、 $N$ 個の行列の積によって途中の遷移が表されることになり、答えは $b_{N+1}$ ということになる。

この形になったところで、 $M$ 回の周回時に毎回この行列積を初めから計算していたのでは間に合わないので、更新されたところだけを計算し直すという方法を取る。

コンテスト本番時は平方分割によって $O(\sqrt{N})$ での実現を図ったが、思った以上にケースごとの処理時間が長く、時間内に提出できなかった。そこで、平方分割ではなく、SegTreeによってこの更新を行っていき、答えを求める。それによって、1回ごとに $O(logN)$ での更新が可能になる。さすがに $N$ が大きくなるとこの2つにも差が出るのだなあという感じがする。

平方分割よりかなり速くなったけど4分くらい入力に対してかかった…まあギリギリか。ただ意外と行列をSegtreeにのせる実装が最大値のSegtreeのテンプレがあったらちょっと書き換えるだけで出来て、意外と大変じゃないのかという感想。

実装(C++)

2017-01-02

CF 749 E - Inversions After Shuffle

Codeforces programming

問題

Problem - E - Codeforces

問題概要

$1$ から $n$ までの数を並べた長さ $n$ の順列がある。1回だけ以下の操作を行う:

全ての区間 $\frac{n(n+1)}{2}$ 個のうち、区間( $l$ から $r$ )をランダムに選ぶ。そして、その区間の長さを $k(=r-l+1)$ とし、その区間に対して、シャッフルを行う(つまり、 $k!$ 通りの並び替え方のうち、ランダムに1つ選ぶ)。

この操作の後にできあがる数列の反点数の期待値を求めよ。

$1 \le n \le 100000$

アイデア

以下、配列は問題に従って1-indexで考えることにする。

考えるべき区間の選び方は $\frac{n(n+1)}{2}$ 個あるわけなので、これが分母になってくるとして考えていくことにする。

考察にあたり、もう一つ重要なことはただ単に順列の全体をシャッフルした時の反転数は $\frac{n(n-1)}{4}$ ということである。これは、1つの配列に対して、それをreverseしたような配列を考えてみると、その2つの配列の反点数の和が $\frac{n(n-1)}{2}$ になっており、そのようなreverseしたもののpairが全ての順列に対して見つかるので、それを2で割ったものということである。

上記の考えから、この問題において求めるべき値は与えられる順列 $a$ の区間 $[ l, r$ ]の反点数を $inv(l,r)$ とおくと、次のようになる:

$\displaystyle \sum_{ 1 \le l \le r \le n} \frac{ inv(1,n) - inv(l,r) + \frac{(r-l+1)(r-l)}{4} }{ \frac{n(n+1)}{2} }$

分子がなぜこのような形になるのか、区間 $[ l, r$ ]をシャッフルした後に、その順列全体の反点数がどのように変化するかを考える。すると、2つのindexに対して、反点数に変化があるかどうかは、どちらかのindexがこのシャッフルの区間の外ならその順番が入れ替わることはないので反点数は変化しないわけである。つまり、反点数が変化しうるのはこの区間内についてのみ注目すればいいということになる。そして、前述の通り長さ $n$ の順列をシャッフルした時の反点数の期待値は $\frac{n(n-1)}{4}$ であるから、その元の反点数を引いてその期待値を足しているという式の形になっている。

さて、ただこれを愚直に計算するのでは間に合わない。分母は $const$ なので、分子をどうするか考えてみると、全体の反点数についてはBITなどをつかうことによって $O(nlogn)$ で計算が可能であり、この分数についても、 $r-l$ に着目すれば $n$ 種類の値がそれぞれ何回ずつ現れるのかが簡単にわかるので $O(n)$ で計算できる。

そして残るは $\sum_{ 1 \le l \le r \le n} inv(l,r)$ の計算である。以下で、これについて考える。

いま、 $inv(l,*)$ をまとめて計算することを考えてみる。そのために、 $l$ を $n$ から $1$ の方向に動かしながら考えていく。そして、配列 $b$ を考えて、 $b_i = \sum_{i \le j \le n} inv(i,j)$ とする。

さて、この $b_i$ の値について計算したいが、この値は $b_{i+1}$ を使って表すことが出来る。それは区間 $[i , j$ ]を $[i , i$ ]と $[i+1 , j$ ]に分けて考えることが出来るからである。

そして、いまは始点を固定しているので、この区間に対して例えば $n$ 番目の値は1つの区間( $[i , n$ ])に入り得る。一方で、 $n-1$ 番目の値に注目すると2つの区間( $[i , n$ ]と $[i , n-1$ ])に入る。つまり、この2つの区間でこの反転がカウントされる。このように $i$ を固定したときに $j$ 番目の値は全部で $n-j+1$ 個の区間に入ってくることになる。