裏紙

ほぼ競プロ、たまに日記

ARC 068 E - Snuke Line

問題

E: Snuke Line - AtCoder Regular Contest 068 | AtCoder

問題概要

M+1個の駅があり、駅に対して0からMまでの番号が振られている。列車は駅0からd駅ごとに停車する。また、N種類の名産品があり、i番目の名産品は駅l_iから駅r_i区間で売られており、その駅に停まると名産品が買える。d=1,2,3, \ldots ,Mの時に買える名産品の個数をそれぞれ求めよ。

  • 1 \le N \le 300000
  • 1 \le M \le 100000
  • 1 \le l_i \le r_i \le M

イデア

まず間隔dを固定して考えてみる。すると、区間の幅(r_i - l_i +1)がdよりも大きい時は、その区間のどこかしらに必ず訪れることになるので、その名産品を買える。一方で、幅がd以下の時はたかだか1回しか訪れることができないのが分かる。

ここで、幅がdより大きい区間については必ず買えるので無視して、幅d以下の区間についてのみ考えると、この区間についてはたかだか1回しか訪れないことがわかっているから区間の累積和を使ってはじめにその位置に含まれる区間の個数を計算してから、dの倍数の位置を調べていけばよいことになる。これでO(N+M)で実現できる。

問題は、d1からMまで動くので、このままでは間に合わない。ただ、幅d以下の区間dを増加させるごとにその数は単調増加になっているので、1からはじめて、上で行った処理をBIT上で行うことで高速に処理することが出来る。

実装(C++)

続きを読む

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++)

続きを読む