読者です 読者をやめる 読者になる 読者になる

ARC070 F「HonestOrUnkind」別解

HonestOrUnkind解いた。
面白かった、と思ってたけど想定解と違ったのでメモ。
想定解の方がシンプルで頭良い。

正直者を1人特定するところが違った。

まず人の組をN/2組作る。Nが奇数なら1人余る。
各組(x,y)について? x yを質問する。
'N'なら正嘘、嘘正、嘘嘘のどれか。(消費される人数は正≦嘘)
'Y'なら正正、嘘正、嘘嘘のどれか。(yを嘘にするためには嘘を2人消費する)
'Y'だった組のyを全部取り出した集合をTとする。
元々のN人では正>嘘である点に注意すると、

  • Nが偶数:Tの中でも正>嘘になる
  • Nが奇数:Tの中では正≧嘘になる

奇数のときも正>嘘にできれば、再帰的にやることにより高々2(N/2)=N回の質問で正直者を1人見つけられる。
奇数のときは「Tのサイズが偶数なら余っていた1人をTに追加する」とすることにより、正>嘘にできる。
いちおう証明↓
Tのサイズが奇数の場合:偶奇の性質上、正=嘘は成り立たないので正>嘘
余りが正だった場合:元が正≧嘘なんだから正を足せば正>嘘になる
余りが嘘だった場合:Nが偶数だった場合を思い出すと、正>嘘になっていてつまり正が嘘より2人以上多いので、嘘を1人足しても正>嘘
どのケースでも正>嘘になっていることが分かる。

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 です。

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

続きを読む

ハッシュの衝突

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

ハッシュを使う場合、以下の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
...
もっと違うのが欲しければこれで生成して下さい。

注意・参考リンク

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

Xmas Contest 2016 B解説

B問題のギャラリーと解説です。

続きを読む