裏紙

ほぼ競プロ、たまに日記

CF 1004 F - Sonya and Bitwise OR

Codeforces programming

問題

Problem - F - Codeforces

問題概要

はじめ、長さnの数列aと整数xが与えられる。次のようなクエリを考える：

  • クエリ1 (i,y) : a_i をyに変更する。
  • クエリ2 (l,r) : l \le L \le R \le rを満たすpair(L,R)について、数列aにおける区間 [L,R] のすべての要素のbitwise ORを取ったときの値がx以上になるようににできるpair(L,R)の個数がいくつあるかを答える。

クエリ1と2が合計でm個与えられるので、順に処理せよ。

  • 1 \le n \le 10^5
  • 1 \le m \le 10^5
  • 0 \le a_i , x \lt 2^{20}

アイデア

区間のvalueをその区間全体に対してbitwise ORを取ったときの値とし、「良い区間」というのを、その区間の全体のbitwise ORを取ったときに、xが部分として含まれているときにその区間が良い区間であると呼ぶことにする。

クエリ2についてどう高速に答えるかを考えたいが、その前に、まずはクエリ2に [ 1 , n ] が来た場合にどうするかを考える。

分割統治のアプローチを考えてみる。区間を、 [ 1 , \frac{n}{2} ] と [ \frac{n}{2} +1 , n ] に分割し、それぞれの区間内で完結するものについては再帰的にそちらで計算してもらうことにして、ここでは、区間の左端が前者にあり、右端が後者にあるものの中で、条件を満たしている区間が何個あるかを数えたい。

さて、区間の左端のindex iに対して、区間 [ i, \frac{n}{2} ] (いわゆるsuffix)のvalueを考えてみると、iが減っていくに従って立つビットの個数は単調増加になっているはずで、立ったビットが戻ることもないので、この\frac{n}{2}個の区間のvalueについて、現れる値の種類数はlog( MAX a_i)個しか無いということが分かる。

ということで、区間のマージを考えるときには、左側に関してはsuffix(各ビットごとに、現れてくる最も右の位置)が欲しくて、右側に関してはprefix(各ビットごとに。現れてくる最も左の位置)が欲しくなる。左側はiを減らす方向に動かすと考えると、右側も同様に、prefixを全部含んでいる状態からスタートして徐々に左に動いていく、みたいな感じで尺取りっぽくやれば区間をまたぐ良い区間の個数がO(log( MAX a_i))で数えることができる。

以上で考えていたことをそのままSegment Treeに乗せて処理することを考える。セグ木の1つのノードに乗せる必要があるものは、上でも述べたようにsuffixの情報とprefixの情報、あとは区間内で完結している答えの個数、の3つの情報である。上でも考察したように、このセグ木のノードとノードのmergeがO(log( MAX a_i))で実現できることが分かっている。つまり、クエリ2に対してO(logn \ * \ log( MAX a_i))で答えることができる、ということである。

では、残ったupdateに関してだが、点更新によって、ノードの更新をしなきゃいけない区間の個数というのは、セグ木の深さを考えるとO(logn)個なので、updateクエリもO(logn \ * \ log( MAX a_i))で実現できる。

以上より、全体の計算量はO( (n+m) \ * logn \ * \ log( MAX a_i))となり、間に合う。

実装(C++)

続きを読む

2018/7 solved(1)

programming solved

7/1

JAG 国内模擬 に参加

6完だった。Gも考察はできてて、サンプルも合ったんだけど、間に合わせられず...国内予選のリハーサルをできて動きを確認した(両面印刷はやめよう)。

ARC 100 に参加

久々に参加した。もっと時間作って参加したいんだけど、どうしても土日の9時はなかなか難しい...。Eが解けてから、CDに時間かかりすぎ。

7/2

7/3

7/4

左上から順に、そのマスに文字を置くか置かないかをきめていくdpをする。そのときに持つべき状態は、(今いるマス, 手前1行分の状態(置いたか置いてないか))があれば十分である。置いたか置いてないかさえわかれば、並べる順番が決まっているのでどこにどの文字が来ているかがわかり、今置こうとしている文字も何行目の何文字目なのかが分かるから、置いたときに得られる点数が計算できる。行が切り替わる瞬間に、文字をちゃんと使い切っていないと遷移してはいけないことに注意(submission)。

7/5

左右と上下を独立にしていいとこまでは分かるけど、そこから条件を満たしつつ動く組み合わせを計算するのが難しい。折り返して考えるというのは賢いと思った(submission)。

z軸方向に対してスキャンしていくときに、連結成分の個数が変わる可能性のあるイベントは、ある球が現れる/消える、球と球がくっつく/離れるのイベントのみである。このイベントの種類はO(n^2)であり、これを順番に処理しながらその都度連結成分の個数を数える。ここは単純なBFSで実装したので、O(n^2)である。よって、全体としてはO(n^4)になっている。また、球が現れ始める瞬間に既に他の球と交わるような場合もある(例えば、内包している時)ので、イベントを1つずつ処理するのはなく、かなり近い座標で起こっているイベントは一度に処理する必要がある(submission)。

削除ができるってことは相手の操作を打ち消せるな、と思うと3ターン目以降って無駄なのでは？と思うと、深さ2までの全操作を試せば良いことになる。構文解析パートは、エラーにも対処しないといけないので結構めんどいけどがんばる。あと、0が有効にならないことを考慮し忘れていてバグらせまくった(こういうのはなくそう)(submission)。

7/6

imulan.hatenablog.jp

7/7

構築ゲー。とりあえず、0101か1010を使わなきゃいけない数が多い方から先頭に、x+1個だけ並べておき、残ったものを切り替わりの数が変わらないように同じ数の隣に置いていく(submission)。

区間を全探索。累積和で高速化しておく(submission)。

倍数の関係になっているので、コインは額が大きい方から貪欲に使っていって構わない。コインはO(logA)種類しかないので、全体はO(QlogA)で処理できる(submission)。

7/8

基本的な方針としては、まず直径dになる分を作ってしまう → 端以外の頂点から次数と深さを守りつつ頂点を生やしていく ということだが、木を生やしていくので(親方向の頂点番号, つなげていい次数, 残されている深さ)をqueueに突っ込みながら新しい頂点を生やしていくと実装が楽。ただ、いろいろなコーナーに注意(d=1だとk=1でもいいけど、d>=2だとk>=2じゃないといけないとか、そもそも直径dを作るための頂点数nが少なすぎるとか)(submission)。

とりあえず、どの区間を略語にするかを全探索することにする(O(n^2)通り)。そして、dp[n][3] = 単語i以降に注目、省略をj回使用したときの長さのminを計算することにすると、遷移は2通りなので全体はO(n^3)になる。遷移の省略する方を考えるときに、O(n)かかってしまわないようにdpをする前にiをスタート地点にする今省略として注目する長さのハッシュをmapなりでとっておくと良い(submission)。

Codeforces Round #490 (Div. 3) Virtual

国内予選終わって若干燃え尽き気味だったけどとりあえず簡単目な問題でも継続しようと思ってやった。発想自体はそこまで難しいものがあるわけじゃないけど、実装はそんなに簡単なわけじゃないしいい練習になった。

7/9

7/10

dfsして全パターンを試して、条件を満たしているかをチェック(submission)。

小さい方から貪欲にM個取っていくが、a[i]とa[i+1]の間を高速に処理するようにする必要がある(submission)。

Codeforces Round #495 (Div. 2) Virtual

Dで時間を溶かした(思い思いの枝刈りをしたら通った...)。Eも思いついてたけど、重心をみつけて、そこから使う頂点を見つけて、それがパスになってるかをチェックして...を実装してたら間に合わなかった。

最大値の最小化を見た瞬間に二分探索を考えた。まず、k=1のときを考えると、このときに選ぶべき点は重心だなあと思ったので、重心からパスを伸ばしていくことを考えることにした。重心(最も遠い点までの距離が最小になる頂点)は、全方位木dpで求めることができる。この位置をスタートにして、二分探索をすると、必ず含めなければ行けない頂点が決まるので、あとはそれがパスになっているかをチェックすれば良い(submission)。

7/11

連続する1の区間で、一番長いやつを見つける。

幹線道路のペアを全探索する。

7/12

下限を全探索する。このときの下限の候補はO(n^2)通りを考えれば良い。固定した下限に対して、各区間がこれよりも大きくなるように選んだときに、最大値が最小になるような切り方をdpでO(n^2)で求めることができる。あとは、答えを逐次更新していけば良い(submission)。

一本道になるような進み方以外が最適になることはなさそうなので、一本道を作っていくことを考えると、今いる場所とそこまでの最短距離をペアにして、その一本道を作るために木をどかしきる最小コストをBFSで求められる(submission)。

7/13

Codeforces Round #496 (Div. 3) Virtual

Div.3なのに全完できなかった...

中央値がX以上になる区間がいくつあるかを求める関数をf(X)とすると、答えはf(X)-f(X+1)で求められる。この"""以上"""がミソで、このように考えることで二値化して考えることができ、E1と同じような考え方を適用できる(submission)。

7/14

7/15

求めたい答えがx以下であるかどうかをチェックする二分探索をすることにすると、数列の値をx以下かどうかで二値化でき、BITなどを使ってその区間にx以下の個数がK個以上あるかどうかがチェックできればいいことになり、高速に数えることができる(submission)。

2017 Ho Chi Minh City Regional Contest Virtual

7/16

答えを二分探索することにすると、決め打ちした値に対して、dp[i] = i番目のワードを区間の左端にすることができるかというdpを、尺取りっぽく更新していくことができるようになる。左端は、限界のライン(ワードと必要最低限のスペースで一行に収まるか)、右端は必要最低限ライン(ワードと目一杯のスペースで一行を超える事ができるか)、という2つの値を持ちながら尺取りして、dpを更新していけば良い(submission)。