AGC013F「Two Faced Cards」別解(TLE)

Two Faced Cardsのコンテスト中に書いてた別解です。
O(N√N logN) なのでTLEして悲しいけど紹介しておきます。
(想定解も理解したけどadhocで面白かった)

下ごしらえ

とりあえずC(とA,B)を0~Nに変換しておきます。
Ai<Biのカードは裏で使うメリットがないのでBi=Aiとしておきます。
これでBi≦Aiが保証できます。
ここで、Bi>Nのカードがあるとimpossibleです。
Ai>Nのカードは後々面倒なので、Ai=Biとして後で答えから-1します。

f:id:snuke:20170417220211j:plain
入力例2の図示

クエリが1個

クエリが1個のときは以下のような貪欲法で解けます。

貪欲法

Ci=0のカードから順に相方を決めていきます。
相方は、以下のようなmultiset<int> Sを使って決めます。

  • Ci=xのカードを見ている時、Bi=xのカードがあればSにAiを追加する
  • Ci=xのカードを見ている時、Sに入っているxを全てINFに置き換える
  • Sに入ってる数のうちの最大値を、今見ているカードの相方として取り出す

表として取れるものがあればそれを取り、なければ表も取れるようになるのが最も遅いものを取るというイメージです。
途中でSが空なのに取り出そうとしたら失敗です。

クエリ複数

次に、クエリが複数ある場合に発展させます。

dp[k]=「Ci=kのカードには相方が要らないときの答え」というのをk=0~Nについて全て前計算しておけば、各クエリに高速に答えることができます。
dp[k]の値はどうなっているでしょうか。

まず、k=Nのときに上のような貪欲法を行うと、どこかの時点で(少なくともk=Nでは)失敗します。
失敗したiをtとすると、k>tは全て-1です。
k=tについてはCi=tのカードをスキップしてそのまま貪欲法を続けて答えdp[t]を求めます。

あとはk<tの場合です。
あるkについて、上の貪欲法でSから取り出した値がINFだった場合は、kをスキップしてもk+1をスキップしても答えは変わらないのでdp[k]=dp[k+1]です。(どっちにしろどうせINFを取るだけで、Sの他の部分は変わらないため)
Sから取り出した値がx(≠INF)だった場合はどうでしょうか?
xを取る代わりにスキップをして貪欲法を続けたときにxが取られるようなiをpとします。
pは必ずx以下になります。(i=xになるとxがINFに変化し、S内の最大値になるため)
このとき、kをスキップした時のSの状況はpをスキップした時とほぼ同じです。異なるのはxが取られるタイミングだけです。
したがって、p<xのときはdp[k]=dp[p]、s=xのときはdp[k]=dp[p]+1となります。

pを全てのkについて求めておけば後ろからdpテーブルを埋めていくことができます。

ーーここまでが本質ーー

データ構造パート

pはどうやって求めればいいでしょうか?
xが取られるよりも先に取られうるものというのは以下の2通りです。(kの時点ではINFはSに入っていない点に注意)

  • Sにまだ残っているもの(値をyとすると、k=yでINFに変わって取れるようになる。y<xが成り立つ点に注意)
  • aiがx以上のもの(bi以降なら取れる)

starry sky tree(区間加算と区間minができるsegtree)を用意します。このsegtreeでは「ある区間内で値がhoge以下のものが初めて現れる場所」をO(log N)で求めることもできます。
上記の2通りについて[取れるようになるi, N+1)に+1をしておきます。
さらに、i=0~Nについて[i,N+1)に-1をしておきます。
kの値をvとすると、[k,x)のうちv-1以下の値が初めて現れる場所がpです。(なければp=x)

上の2通りの+1を適切な順で追加したり消したりしながらpを全部求めていきたいのですが、残念ながらMoをするしかないです。
ただ、普通にMoをすると右端を1つずらしたときに増えるものが多かったり少なかったりして壊れるので、右端を「何番目に小さいbiであるか」を基準として√N個ずつのブロックに分けます。しかし、それだけだとbiが全くないゾーンが広過ぎになってしまうことがあるので、biの集合に0~N追加した集合での何番目かを基準にするなどしなければいけません。
左端については1つずらしたときには高々1つしか増減しないのでOKです。

まとめ

というわけで最後の方わりと雑でしたが、O(N√N logN)になりました。
こんな感じで6ケースだけTLEしましたΩ\ζ°)

根付き木のハッシュ

りんごさん方式の記事
正当性を証明するにはユニークな多項式の形にしてmodを素数にしておけば、Schwartz–Zippel lemmaを使えて良いっぽい?
multisetのハッシュ、0になりやすいなぁと思ったけど0になる確率がat most n/modなのか。
記事での根付き木のハッシュの取り方を日本語にまとめておきます。

根付き木のハッシュ

まず、深さ i に対応する乱数  R_i を [0,mod) から取っておきます。
深さ i の頂点 v について、v 以下の部分木のハッシュは「( R_i + 子のハッシュ)の積」として計算します。
特に、葉のハッシュ値は 1 です。

詳細は実際に記事を読んで下さい。


僕は根付き木のハッシュをどのように取っていたかの話と、それは良くなかったという話と、ならどうすれば良かったかの話をします。

計算法

まず素数p,modを用意する。
ある頂点以下の部分木ハッシュ値は「p + 子のハッシュ値の二乗和」として下から計算していく。

(適当なハッシュ関数 h を用意して、h(子の値)の和とかにしてもよいと思う。h(x)=x^2がうまく行きそうかつ簡単だったので二乗和にしたというだけ。)
(h(x)=hoge*xとかだと、深さの分布が同じで形が違う木を同一視してしまうのでダメ)
↑冷静に考えて、二乗和もあんまりよくないので(おまけ参照)、適当な良質かつ高速なハッシュ関数を使いましょう。
適当なハッシュ関数の例としては、Murmurハッシュとかを聞きました。
CF等のhackありのコンテストで使う場合、p にあたるものとか(あるなら)ハッシュ関数のseedとかをランダムに生成すると良さそう。

妥当性について

結局、根付き木のハッシュというのは、multisetのハッシュをどう取るかという話で、
「適当なハッシュ関数」が本当に良質なら、正当なハッシュの取り方だと思います。

備考

こっちの方式の売りなのですが、いわゆる全方位木DPが簡単に書けて任意の根に対する任意の部分木のハッシュが計算できます。
(全方位木DPについてはそのうち書くかも?)(←書いた。関連記事見て。)

応用編としては、頂点にラベルがある場合は、ラベルに対する乱数的なハッシュをとり、それをpの代わりに使うと良いでしょう。

練習問題:http://codeforces.com/contest/763/problem/D https://atcoder.jp/contests/nikkei2019-2-final/tasks/nikkei2019_2_final_d
mod=1e9+7くらいでハッシュ取ると衝突するので、注意。この記事も参考に。

おまけ

二乗和のハッシュの正当性の証明(または嘘である証明)お待ちしてます。
ちなみに4回くらい使いましたが全部ACしてます。
11頂点の木どうしで撃墜できました。 A - tree hash

おまけ2

りんごさん式の方の全方位化ですが、

  • 深さとハッシュ値のペアを計算していく
  •  R_i を外に出す(下記ツイート参照)

をすると、そこまで大変でもないかもしれません。
積なので左右からの累積積を持つか、logかけて逆元(0除算は確率的に無視して良い)でやるかしないといけない点はマイナスだけど、ハッシュ関数を用意しないで良い点はプラスという感じか。

※ この記事は2019/12/19にわりと加筆修正されました。

ハッシュの衝突

ローリングハッシュや木の同型判定など、競プロでハッシュを使う機会はあるけど、衝突確率とか必要な値域についてあまり考えたことがなかったので計算してみた。

ハッシュを使う場合、以下の2通りではそれぞれ衝突確率がかなり異なる。(少し考えれば当たり前の話だけど、「ハッシュ」という言葉で思考停止しがち)

2つが同じであるかを比較するだけ

2つのハッシュが衝突する確率さえ低ければ良い。
比較を何度かする場合でも、それほど大したことはない。
1回の衝突確率をp (大抵の場合 1/mod とか) として比較回数をNとすると、1回でも衝突する確率は1-(1-p)^N。
N=1e5, mod = 1e9 としたときに1回でも衝突する確率は 0.01% ほど。まぁ十分低いと言えそう?100個テストケースがあっても衝突確率は1%くらい。

種類数を求めたりする

いわゆるお誕生日。かなり衝突しやすい。
少なくとも N=1e5, mod = 1e9 としたときに答えが変わる確率は 99.3% ほど。むしろ衝突しない方がおかしいくらい。
まぁ、2つのハッシュの比較を二乗回やってると考えればわざわざ上の項と別にして書くことも無い気はするが、でもやっぱり衝突のしやすさには有意差がある。
ちなみに、1組でも衝突が起きる確率が50%を超えるようなNはだいたいO(√mod)くらいらしい。
とりあえず各N,modごとの衝突確率の表は以下の通り。(値は適当に丸めてある)
O(√mod)くらいというのも納得できる。

mod\N 103 104 105 106 107
109 0.05% 4.9% 99.3% 100% 100%
1010 0.005% 0.5% 39.3% 100% 100%
1011 5e-4% 0.05% 4.9% 99.3% 100%
1012 5e-5% 0.005% 0.5% 39.3% 100%
1013 5e-6% 5e-4% 0.05% 4.9% 99.3%
1014 5e-7% 5e-5% 0.005% 0.5% 39.3%
1015 5e-8% 5e-6% 5e-4% 0.05% 4.9%
1016 5e-9% 5e-7% 5e-5% 0.005% 0.5%
1017 eps% 5e-8% 5e-6% 5e-4% 0.05%
1018 eps% 5e-9% 5e-7% 5e-5% 0.005%

まぁmodを1e18くらいにしとけばそうそう落ちることはないって感じかな。
ただ、それだと掛け算がオーバーフローするからバイナリ法とかで計算しないといけなくなって重そうだしなぁ。
とりあえず僕は1e9くらいのmodのpairにすることにしてライブラリを作ってみました。

1e9くらいの素数
999999797
999999883
999999893
999999929
999999937
1000000007
1000000009
1000000021
1000000033
1000000087
...
1e18くらいの素数
999999999999999829
999999999999999863
999999999999999877
999999999999999967
999999999999999989
1000000000000000003
1000000000000000009
1000000000000000031
1000000000000000079
1000000000000000177
...
もっと違うのが欲しければこれで生成して下さい。

注意・参考リンク

上記はハッシュが良質なものだと仮定した時の話なので、いい加減なハッシュだとこの限りではないでしょう。
いい加減ハッシュといえば、これは知っておくと良いと思います。
あとは、これの解説とか詳しいです。
あと、根付き木のハッシュについての記事を書きました。