裏紙

ほぼ競プロ、たまに日記

FHC 2017 R2 C - Fighting all the Zombies

問題

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_i10^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-1ii+1の3種類に限られるということが分かる。

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

続きを読む

CF 749 E - Inversions After Shuffle

問題

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,*)をまとめて計算することを考えてみる。そのために、lnから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個の区間に入ってくることになる。

つまり、b_iを計算するときに、i \lt jなるjを考えて、その中でa_i \gt a_jとなっている位置のみに対してこの上記の反点数カウントをすればよいことになる。これは、まさにBITによって実現される。

(自分の用意してたBITにちょっとバグがあってそれに気づいて直すまでに時間かかった...このBITで何問か通してたはずなんだけど、見つかってよかった)

実装(C++)

続きを読む

2016/12 solved(2)

12/17

Wikipediaの画像ながめて、正方形の周上に移動できるのかーってなったときに、最大のdの内側に入ってるなら2回でどこでもいけるのではという事に気づいてからは場合分けで一瞬だった...

左から順に見て、右から順に見て、何人避難できるかを最大更新していく。

クラスカル法でMSTを構成していき、使った辺のうちの中央値を答えればいい。

とりあえず1日1枚以上は食べるとすると、N日以内に食べ終わる。なので、dp[i][j] = i日目までに合計j枚食べる方法の順列の個数O(N^2)で計算できる。あとは、その正の枚数食べるところがi日あったら、残りのD-i日は0枚ということになり、それをどこに入れていくかは重複組合せによって計算出来る。

まず何桁の数字の位置で来るのかを計算し、その分をnから引いておく。更に、そこから桁数dが決まるとn/dだけ進めれば直前にたどり着けるので、あとはstringのくっつけてsubstrで出した。

12/18

トポロジカルソートしてから、その順番に辺を見ていって最大値更新をしていくDPを先頭からと、後ろからとやっておけばよい。トポロジカルソートはDFSによってO(N+M)で出来る。

まず、1からxまでのFizzBuzz stringの長さがs未満になる限界のxを二分探索によって探すことが出来る。そして、そこからstringを構成してsubstrすればいい。

二部マッチングで解いた。b[i]とr[j]の間に辺をはれるかどうかの判定は、事前に約数列挙をしておけばO(約数の個数)でできる。

dp[i] = i番目の要素が終端になるときの単調増加部分列を考えたときに、合計の荷物の重さの最大値とすると、 dp_i = max(dp_j ) (j \lt i and x_j \lt x_i )で更新していくことが出来る。これはSegtreeを利用して、xの小さい順に更新していくようにすることでO(NlogN)で実現出来る。

12/19

隣接しているスライム同士に辺を張り、連結している個数を調べる。連結が1つだけならn-1が答えになり、2つ以上ある時は壁に寄せることになるので四方のどの壁に寄せるのが良いかを4通り試した。

コストが大きい方から柱を作っていく。閉路ができてしまってはいけないが、できてしまうかどうかはUnion-Findによって検知することが出来るので、結局出来上がるのは木の形になる。

暗い部屋に人がいるかの状態を表すbitDPでBFSで解いた。

12/20

8!通り試す。その際に、回転して同じ状態になりうる24通りを試して、その順列の中で一番小さいもので正規化しておいて種類をカウントすると楽。

BFSすると、根からの距離と訪れる頂点の順番が分かる。それとLCAを利用して、全体の移動にかかる距離を高速に計算出来る。

12/21

(最後に訪れた店,今までに訪れた店の集合)を状態に持ちbitDPをする。この遷移のための準備として、スタート地点と、各店をスタート地点としてダイクストラで最短距離を求めておき、各頂点間の最短距離を予め計算しておく。

取りうる値が0~255までなので、変数に関して全探索をしてその変数を含む計算結果がどのように取りうる値を変化させるかを計算することができる。除算のときに、変数が0を取りうるならerrorを返す。

12/22

答えにたどり着く方法が1通りのみと決まっているので、その都度行ける3通りを試して行き止まりになったらやめる単純な枝刈りで十分間に合う。

12/23

まずy座標の種類を列挙してソートしておき、平面走査でx座標が小さい順に見ていく。xが窓枠の左に来るとして、最大値を返すsegtreeで、i番目にy_iを枠の下側に来るようにした時の輝きの合計を保存するようにしておく。このような形にすると、区間に対するaddが必要になることが分かるので、いわゆるStarrySkyTreeを実装した。

12/24

Xmas Contest 2016 昼の部に参加

友達と一緒にゆるい感じでやった。ら、Aしかできなかった...Cずっと考えてたけど、O(N^3)から落ちず、辛かった。

12/25

使ってはいけない辺をsetで保存しておく。そして、まだ訪問していない頂点をsetで管理し、スタート地点からBFSしてまだ訪問してない頂点のsetに全探索して、行けるところは行ってsetから取り除くということをすると辺を張るのに失敗するのがO(M)回なので間に合うという、結構シンプルな考え方だった...グラフの直径を求めたりしようとしたけど、木じゃないとそういうのは厳しいっぽいし見当違いだった。

12/26

imulan.hatenablog.jp

座標圧縮して、その区間ごとに何匹の魚がいるかを調べる。区間O(n^3)個になり、区間ごとの判定は線形にできるので全体としてO(n^4)で間に合う。

どのカードを取り除くかを全探索してシミュレーションすれば良い。

距離ごとにシミュレーションしていく。確定する場合は2人と出て両方にいることが分かる時と、1人出るが片方は範囲外になっていている位置が確定するときがある。

100以下の素数を列挙すると25個ある。ただ、合成数かどうかを判定できればいいので50以下の素数を用意しとけば十分。ただ、その素数ごとに聞いていくだけだと9のように1種類しか素因数を持たないものの判定ができないで気をつける。

12/27

mに対してa^3 \le mを満たす最大の整数aとすると、次に選ぶキューブの大きさはaa-1のどちらかが最適であることがわかる(Editorialより)。そして、実験してみると最大でも個数の最大値は18なので、普通に再帰で全探索しても間に合う。

部分文字列にした時にどの文字列だったかわからなくなってしまうパターンを考えてみると、同じ文字の間が全部詰まってしまって 1つになるパターンなので、s[i]とs[j]の距離がK以下で同じ文字のところがあれば不定の例を作れる。それ以外はOK。

Aを何個使うかを全探索することにすると、それに応じて最適なBの配置の方法が決まる。そうして作られたもののうち、長さがN以下になるものがあればそれを答えればよい。

12/28

答えを二分探索していく。そして、高さmの建物が立てられるかの判定は、長さNの配列を用意しておけば簡単に判定できる。

まず、現れる順番は無視していいので、ソートしておく。そして、1つの基準点を作り、その値を動かさないようにしてその前後の値をconsecutiveになるように調節する全探索をすればいい。これで、O(n^3)で実現できる。

まず、滞在の終わりが早い順にソートしておき、前から順番に見ていく。i番目の人がまだspecial promotionの人と繋がっていない時、その人は繋がないといけないが、このときに最も選ぶべきものは「i番目の人をカバーできて、かつ滞在の終わりが遅い人」なので、後ろから見ていって見つかった人をspecial promotionする人に選ぶという貪欲で客の数nに対してO(n^2)でできる。

  • [SRM 644 Div1 Easy - OkonomiyakiParty]

(Unrated回なのか、リンクがなかった)(はじめにそれを確認しておいて問題を選ぶべきと言う感じがある(これ何回やれば気が済むんだ))

お好み焼きのサイズでソートしておく。そうして、i番目とj番目のサイズの差がK以下ならその間からM-2個を選ぶことにする。その組み合わせは、2次元配列を用意して事前に用意しておくことで全体はO(n^2)で実現できる。

12/29

はじめに、それぞれの町を始点としたBFSをして、到達可能な範囲を調べておく(O(nk))。そして、到達可能な町にはコストr_iの有向辺を張る。すると、辺の個数はO(n^2)個になるので、ダイクストラで間に合う。

Oの位置を基準に全探索する。Jの個数を前から累積和で持っておき、Iの個数を後ろからの累積和で持っておき、Jを先頭に置く場合・Iを最後尾に置く場合・Oを置く位置の全探索でO(n)で出来る。

dp[r][s][j] = r行目,s番目の石にいて、一行飛ばしのジャンプの回数がj回の時の最小コストを更新していくDP。行が増える方向にしか遷移しないので結構シンプル。

座標圧縮してO(n^2)個のグリッドに分ける。そして、BFSなどで連結成分の個数をカウントすれば良い。

dp[i][j] = 最後に切った位置i,今の合計の長さjのときにかかるコストの最小値を更新していく。愚直にやるとO(n^3)だが、遷移を上手く保存してまとめるようにすると1つオーダーを落とせる。

12/30

まずはショッピングモールからの距離をダイクストラで求めておく。その次に、辺を1つずつ見ていく。そのときに、辺の両端のダイクストラした最短距離の情報を見ながらどの位置に置くのが最適なのかは簡単な1次方程式を立てることで求めることが出来るので、その最大値を更新していけば良い。これで、全体でO(MlogN)となる。

まず、ダイクストラして始点からの距離を求めておく。すると、Xとして選ぶのはこのいずれかの頂点までの距離にするのが最適なのは明らか(中途半端な値にする意味がない)ので、Xとして選ぶ値はO(n)通りある。これを全探索していく。そのときに残る道の長さの合計がどれくらいになるのかというのは、まず、頂点をスタート地点からの距離順でソートしておくと、その道が撤去されるタイミングは端点のうち距離が大きい方がX以内になるタイミングなので、辺をこの端点のmaxをkeyにしてソートしておくと尺取的にO(n+m)で計算していくことが出来る。

まず、全体で重さが1になると仮定して、各場所にいくらの錘が来るのかを分数で表して計算する。その伝播の方法は、トポロジカルソートで簡単にできる。そのあとで、錘を全部整数に直すために錘の分母のLCMを取って計算してやれば良い。

dp[i][j][IO] = 次に使えるのがsのi文字目,tのj文字目で末尾の文字がI/Oのときに作れる列車の長さの最大値を更新していく。

2周分の累積和をとっておき、1個目の切り込み位置を全探索する。そして、2個目はsum/3あたりに、3個目はsum*2/3あたりをlower_boundで見つけてチェックする。

まず普通にシミュレーションしておく。そして、そのシミュレーションの最中に、各辺でどれとどれを入れ替えているのかを保存しておく。その辺だけを除いた時、そのシャッフルが無効になってその2つの行き着く先が変わるので、横の棒を全探索してスコアを最小化する。

桁DPをする。(B以下の条件に合う数の個数) - (A以下の条件に合う数の個数) + (Aが条件に合うか)で求めた。

CF Good Bye 2016に参加

ABDの3完。Cはケアレスミスで落としてしまったっぽい...本当に反省。気持ちよく2016を締められなかった...

12/31

本当に僅かなミスだった...(ずっとdiv2にいたときでも、最後の1回の後にDiv1に上がりうることを考慮していなかった)

読み終わる時間を最小化したいというのが前提にあることに留意すると、読むのにかかる合計時間のうち、一番時間のかかる本が半分以上を占めているとどうしてもその2倍の時間読み切るのにかかってしまう。また、そうでなければ1人は1番時間のかかる本から読み始め、2,3,4,...と読み、もう1人は2番目に時間のかかる本から読み始めて、3,4,5,...と読んでいけば、nまで読み終わった後に1番時間のかかる本は読み終わっていることになっているのでそれを読むという方針を取ることで、隙間なく時間を詰めることが出来る。なので、この場合はちょうど読む合計+書く合計になる。

ただ、読むのにかかる合計時間のうち、一番時間のかかる本が半分以上を占めている時は、1人がその本を読んでいる間に、もう1人はそれ以外の本を全部読んでも時間を持て余すことになる。その空いている時間に書けるぶんの感想文を書いておくのを、最大時間を求めるためにDPする(dp[i][j] = iまで読んで、時間jぶんの感想文を書けるか)。jが大きくなりそうに見えるが、このDPをするにあたり、そもそも余る時間は一番時間のかかる本以下なので1000以下ということになり、間に合う。

それぞれのLPG stationからダイクストラする。

トポロジカルソートする。