n-knuu's logs

憧れ駆動。だいたい競プロ

区間 mex クエリ問題

集合の中に含まれない最小の数を求める操作は mex(minimum exclude に由来) と呼ばれている。

Mex (mathematics) - Wikipedia

区間に対する mex を求める問題を見かけたので備忘録として書いておく。

問題

はじめ、集合 S は空集合であるとする。

Q 個のクエリが与えられ、各クエリは以下の3つの形式のいずれかである。

  1. 1 x: xを集合Sに加える
  2. 2 x: xを集合Sから取り除く
  3. 3 l r: [l, r]である整数xのうち、集合Sに含まれない最小のxを出力する

与えられたQ個のクエリを順に処理せよ。

制約

  • 1 <= Q <= 105
  • -109 <= x <= 109
  • -109 <= l <= r <= 109
  • 2 番目のクエリにおいて、x は必ず S に含まれる
  • 3 番目のクエリにおいて、[l, r] である整数のうち集合 S に含まれないものが必ず存在する。
続きを読む

CODE THANKS FESTIVAL 2017 H. Union Sets

この記事は 解説 Advent Calendar 2017 の10日目の記事です。
昨日は unko08658932 さんで「Code Thanks Festival 2017 F Limited Xor Subset 解説 (ありがとう2017F問題の想定解じゃないのを書きます)」でした。

解法

ほぼ解説の解法1とほぼいっしょなので、その解法を思いついた流れを整理しておく。

Union-Findである頂点aとある頂点bをuniteするとき、aの根をa'、bの根をb'と置くと、以下の二通りが考えられる

1. a'をb'に繋ぐ
2. b'をa'に繋ぐ

図にすると、以下のようになる

f:id:n_knuu:20171210211032p:plain

各操作でa'とb'の間に枝を張って木を作っておき、さらに繋げた側がいつ繋げたかを覚えておく。
(つまり、a'をb'に繋いだ場合、a'を何回目の操作で繋げたかを配列などに記憶しておく)

ここで、あるx, yについてのクエリを考える。
まず、Union-Find で頂点 x と y が同じ集合にない場合は -1 を返す。
それ以外の場合、まず先程作った木の上で LCA*1 を行うと、下の図のようにオレンジの頂点を求めることができる*2
知りたいのは、下の図の緑の頂点が何回目の操作でオレンジの頂点と繋がったかである。

f:id:n_knuu:20171210211028p:plain

ここで、木の頂点vの深さをdepth[v]とする*3
緑の頂点は、x から (depth[オレンジの頂点] - depth[x] - 1) 回親を辿った頂点(これを頂点 u とする)か、もしくは y から (depth[オレンジの頂点] - depth[y] - 1) 回親を辿った頂点(これを頂点 v とする)のいずれかである。
ただ、u, v のどちらが緑の頂点になるかが問題である。ここで、u, v のうち、緑の頂点ではない方の頂点を赤の頂点とする(下図参照)。

f:id:n_knuu:20171210211020p:plain

赤の頂点がオレンジの頂点と繋がる操作は、緑の頂点がオレンジの頂点と繋がる操作よりも必ず先に行われているという性質を考えると、頂点 u, v の両方求めておいて、それらがオレンジの頂点と何回目の操作で繋がったかについて求めて、その大きい方を答えればよい。
これはUnion-Findで木を作る途中で記憶してあるので、容易に答えられる。(ただし、u, v のいずれかがオレンジの頂点に一致する場合は、そのための処理が必要なので注意)

計算量

O(Mα(N) + (N + Q) log(N))

コード


感想

Union-Find + LCAという解法自体は割とすぐに求まったけど、LCAのライブラリがバグっており、散々だった。
ライブラリをちゃんと整備しておくことは大事。
おそらく人生最後のこどふぇす*4でパーカーを逃したため、非常に辛かった。

最後に

明日は ferin_tech15 さんで「何か書く」です。
一体何が書かれるのか楽しみですね。

*1:第二版 p.293 あたりに載っている。蟻本を読もう!

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

*2:全ての操作を終えた後にできるのは森であるが、適当な根 r を設定し、ある頂点の属する木の根が自分自身である場合に頂点 r と繋ぐと森を一つの根付き木にすることができるので、その上で LCA の前処理をダブリングで行っておく

*3:LCAをダブリングで求めた場合、これは既に求まっている

*4:社会人Dとかに行けば出られるが、そこまでAtCoderが存在しているのかとか、こどふぇす自体がなくなってないかとかが考えられる

AtCoder Regular Contest 075 E. Meaningful Mean

以下のことを考えて、やっぱり解説を書くことにした

  • 復習のときに思いつかなかったので、ちゃんと記憶に残すために書いておくべき
    • 自分用のメモは残したりしているけど、人に読んでもらうために文章を考えることは、記憶に残す上でも文章を書く練習上でも重要だと思う
  • どうせnim-langで解いているからコード貼ってもわからないでしょ、みたいなのが解説を書かない言い訳になっている状況は良くない
続きを読む

CODE FESTIVAL 2016 Elimination Tournament Round 1 B. 数字列をカンマで分ける問題

続きを読む

DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 C. アメージングな文字列は、きみが作る!

Suffix Arrayのライブラリ整備のために解いた

続きを読む

AOJ2328 Mobile Network

Mobile Network | Aizu Online Judge

問題

無向フローが与えられるので頂点1からNへの最大フローを求めよ。
ただし、枝の重みがxの多項式で与えられるものとする。

制約

2 <= 頂点数 <= 50
0 <= 枝数 <= 500
多項式の次数 <= 50
0 <= 係数 <= 100 (ただし係数が0の項は与えられる多項式に含まれない)

続きを読む

yukicoder No.177 制作進行の宮森あおいです!

8月後半〜9月末まではインターンとかで忙しくて中々書けなかったが、そろそろCodeFestival2016本戦に向けて再開していきたい。

続きを読む

SRM696 div.1 300 Gperm

寝坊したので出れなかった。

問題

50個の頂点とM個の枝を持つグラフ(単純グラフとは限らない)が与えられる。初め、各頂点は全て塗りつぶされていないとする。毎回、どこか1つの頂点を塗りつぶした後に、枝の両端の頂点がともに塗りつぶされている枝の数だけコストを支払う。支払うコストの合計が最小になるような順番で頂点を塗りつぶしたときのコストを求めよ。

制約

1 <= M <= 20

続きを読む

Codeforces Round #367 (div. 2)

Codeforces Round #367 (div. 2)に参加した。
officialだと230位くらいでレートが下がりそうな順位だった。

A. Beru-taxi

  • 問題

タクシーiが(x_i, y_i)にいて、速度v_i(1 <= i <= N)で走ることができる。(a, b)に向かってまっすぐ走ったとき、(a, b)に最も速く着くタクシーの着く時間を求めよ。

  • 解法

距離/速度を計算するだけ

  • 計算量

O(N)

  • コード


B. Interesting drink

  • 問題

N個の商品が与えられ、その値段がx_1, x_2, ..., x_Nであるとする。これに対して、Q個の金額m_1, ..., m_Qが与えられるので、各m_iで買える商品の種類数を答えよ。

  • 解法

数列をソートすると、m_i で upper bound を取ったときのインデックスが答えとなる。

  • 計算量

O((N+Q)logN)

  • コード


C. Hard problem

  • 問題

N個の文字列が与えられ、各文字列を逆順にするためのコストc_iが与えられる。幾つかの文字列を逆順にして、文字列を先頭から辞書順になるようにするとき、逆順にするコストの合計を最小化せよ。どのように逆順にしても辞書順にならない場合は-1を出力せよ。

  • 制約

2 <= N <= 10^5
0 <= c_i <= 10^9
文字列の長さの合計 <= 10^5

  • 解法

DP。dp[i][j] := (i-1番目までを辞書順にして、i番目が(j=0→逆順にしない/j=1→逆順にする)場合の最小のコスト)とおくと、
dp[i+1][0] = min(dp[i][0], dp[i][1]) (if (i番目の文字列) < (i+1の文字列) かつ (i番目の逆順の文字列) < (i+1番目の文字列))
dp[i+1][1] = min(dp[i][0], dp[i][1]) + 逆順にするコスト (if (i番目の文字列) < (i+1の逆順の文字列) かつ (i番目の逆順の文字列) < (i+1番目の逆順の文字列))
とする(片方しか逆順になっていない場合はそちらだけで更新する。詳しくはコードを参照)

  • 計算量

O(N+sum(文字列の長さ))

  • コード


D. Vasiliy's Multiset

  • 問題

初め、multisetには0が1つ入っている。これに対して、1. xをmultisetに追加する、2. xをmultisetから削除する、3. xとmultisetの要素yの中で、x^yが最大になるものを出力する、という3種類のクエリがQ個与えられるので処理せよ。

  • 解法

xとXORを取ったときに、上位bitを立てるようなものがmultisetに入っている場合は、下位ビットがどうなろうとそれを取った方がいいということが分かる。
よって、上位からビットを立てるか決めていく二分探索を行う。

0. left = 0, right = INFとする
1. for i in 30 to 0 do
1.1 multisetに対して、mid=left + 2^iのlower boundを求める
1.2 xのiビットが0の場合、mid以上の値がmultisetにある場合は、iビット目を立てることができるので、left = midとする。もしない場合は、right = midとする。
1.3 xのiビットが1の場合、midより小さくなる値がmultisetにある場合は、iビット目を立てることができるので、right = midとする。もしない場合はleft = midとする。
2 答えをx xor leftとする

  • 制約

1 <= Q <= 2×10^5
1 <= x <= 10^9

  • 計算量

O(QlogQlogx)

  • コード


感想

Dはもっと複雑なことをしないといけないと思って詰まっていたのがダメだった。
想定解はTrieを使うらしい。