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

根付き木のハッシュ

りんごさんがちゃんとしたハッシュについての記事を書いてくれたのでそちらを推奨しておきます。
正当性を証明するにはユニークな多項式の形にして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問題のギャラリーと解説です。

続きを読む

Xmas Contest 2016 H解説

H問題の解法と雑な証明です。

まず、計算量無視して貪欲法を考える。
根付き木にして、
最も深い頂点から順に、距離X以内に頂点がないなら取るというのを繰り返す。
そうすると最適解が作れる。
証明
深い順に頂点に昇順に番号をつける。vの番号をf(v)とする。
上記のアルゴリズムで最適解が得られないと仮定する。
上記のアルゴリズムで得られる解において選ぶ頂点の集合をSとする
すべての最適解において選ぶ頂点の集合をTとしたとき、「条件:頂点x,yであって、f(x)<f(y) かつ x∈S かつ x∉T かつ y∈T、となるものが存在する」を満たすはずである。
そのようなx,yであって、f(x)が最小であって、さらにそのうちf(y)が最小であるものをとってくると、yを選ばないことにしてxを選ぶことによって別の最適解が得られ、これを繰り返していくと「条件」を満たさないような最適解が得られることになり、矛盾する。
「yを選ばないことにしてxを選ぶこと」が常に可能であることを証明する必要がある。
f(x)が最小であるから少なくともf(v)<f(x)となるvについてはSとTで状況が同じであるため、xを選ぶ際の障害にはならない。f(y)が最小であることから、f(x)<f(v)<f(y)となるvは選ばれていないはずである。f(y)<f(v)かつv∈Tとなるvに関しては、dist(x,y)<X≦dist(v,y)であるはずで、「f(x)<f(y)<f(v)」「dist(x,y)<X≦dist(v,y)」からX≦dist(v,y)<dist(v,x)が言えるため、障害にならない。
で、また計算量を無視してDFSで集合S(証明内で定義したやつ)を求めてみようとしてみる。
部分木iだけみたときに選ばれる集合をS_iとする。
部分木i内の頂点vがv∈Sならばv∈S_iとなることは明らか。
S_iとS_jをマージするときは、集合に含まれる頂点を深い順に見て、選べるものだけ選ぶとよい。
S_iの性質として「根から距離X/2以下の頂点は高々1つしかない」ということが言える(もし2つ以上あるなら明らかにその2頂点の距離はX以下であるため)。そのような頂点をSa_iと呼ぶことにする。
Sa_iとSa_jの距離も明らかにX以下なので、少なくともどちらかは捨てなければならない。
また、Sa_i,Sa_j以外の頂点はマージした後も全て選ぶことが出来る事も言える。根からの距離がX/2より大きいため、それらの距離はXよりも大きくなるためである。
Sa_iとSa_jの話に戻るが、このうち深い方以外は必ず捨てることになる。f(Sa_i)<f(Sa_j)とすると、Sa_iが選べずSa_jが選べるというケースはありえないためである。
つまりマージの際行うべきことは、以下の通り。
Sa_i,Sa_j以外の頂点を全て採用する。
Sa_i,Sa_jのうち最も深いものをSaとする。
Saから距離X以内の頂点がない場合はSaを採用する。
ここで、「Saから距離X以内の頂点」となりうるものは「根から距離X/2以下の頂点」が存在しない部分木の頂点でもっとも根に近いものしかない点に注意したい。
マージすべき部分木が3つ以上の場合も上と同様の議論ができる。
上記に基いて効率的なアルゴリズムを設計する。
dfsをして、各部分木で選んだ頂点のうち最も根に近いもの(と選んだ頂点の個数)を求めていく。
ある頂点v以下の部分木に関して計算するときは、その子の部分木内で最も根に近いものを深さ順にソートし、深いものから順に選べる限り選んでいく。
選んだもののうち最も根に近いものをdfsの戻り値として返す。
かなりシンプルなアルゴリズムになった。


しかしまだソートのlogがついているので改善する。
実は、マージのときには「X/2以下のもののうちの最大値」と「X/2より大のもののうちの最小値」を求めていくだけでいい。

open all / close all


generated by indenter


以下ソースコードです。マクロ多くてごめんなさい。

#include略
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define gep(i,g,j) for(int i = g.head[j]; i != -1; i = g.e[i].next)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcount
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define df(x) int x = in()
#define dame { puts("-1"); return 0;}
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,vector<T>,greater<T> >
#define bn(x) ((1<<x)-1)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');}
template<typename T>istream& operator>>(istream&i,vector<T>&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(vector<T>&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,vector<T>&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>ostream& operator<<(ostream&o,pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
const int MX = 100005, INF = 1001001001;

int n, m;
vvi to, co;
int cnt;
int dfs(int v, int x, int p=-1) {
  int a = 0, b = INF;
  rep(i,sz(to[v])) {
    int u = to[v][i];
    if (u == p) continue;
    int r = dfs(u,x,v)+co[v][i];
    if (r*2 >= x) {
      mins(b,r);
    } else {
      --cnt;
      maxs(a,r);
    }
  }
  if (a+b < x) return b;
  ++cnt;
  return a;
}
int f(int x) {
  cnt = 0;
  dfs(0,x);
  return cnt;
}

int main() {
  scanf("%d%d",&n,&m);
  to = co = vvi(n);
  rep(i,n-1) {
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    --a; --b;
    to[a].pb(b); co[a].pb(c);
    to[b].pb(a); co[b].pb(c);
  }
  int l = 1, r = INF;
  while (l+1<r) {
    int c = (l+r)>>1;
    if (f(c) >= m) l = c; else r = c;
  }
  cout<<l<<endl;
  return 0;
}