複数のドキュメントがある。各ドキュメントには家系図の情報が複数行書かれている。ドキュメントは正と負の2種類あり、各行はペア(x, y)であり、
を意味する。
各ドキュメントはそれぞれについて、正か負わからない。n個のドキュメントと二人の人p, qが与えられたとき、pがqの祖先であるような無矛盾なドキュメントの正負の割当があるかどうか判定せよ。
虫食い等式が与えられる。数式は2進数で数を表記し、BNFは次のように与えられる。
Q ::= E'='E E ::= T | E'+'T | E'-'T T ::= F | T'*'F F ::= N | '-'F | '('E')' N ::= '0' | '1'B B ::= empty | '0'B | '1'B
演算子の優先順位はBNFと同じ。
虫食いは大文字小文字を区別するアルファベット全て。同じアルファベットは同じ記号に、異なるアルファベットは異なる記号に割り当てなければならない。ただし、虫喰いされていない記号をアルファベットに割り当ててもよい。
正しい等式は何通りあるか答えよ。
長さは31以下。
n本のコンベアラインが平行に並んでいる。各ラインiの左から製品iが右に向かって流れる。またm台のロボットが配置されてある。ロボットjは左からxjの位置にあり、ラインyj, yj+1の製品をそれぞれ反対のラインに移す事ができる。xjは互いに異なる。
ロボットを好きなタイミングで動かしたり止めたりして良いとき、各ラインには何種類の製品を流すことができるか。
一桁の数同士のX演算の定義テーブルが与えられる。iXi = 0が保証されている（i = 0 .. 9）。ある4桁の数 abcd (leading zerosを許す) に対して、e = (((0Xa)Xb)Xc)XdをCheckDigitとして5桁のabcdeについて、書き間違えを判定したい。
「上の任意の書き間違えを1回したら検出できる」とは限らないabcdは何通りあるか求めよ。
始めに数列1 … n がある。「数e_iを先頭に移動させる」と言う操作をm回行う（1 <= i <= m）。最後の数列を出力せよ。
Introduction to Algorithms に載ってる、wikipedia:en:Van_Emde_Boas_tree の記事がある、日本語のslideshare Nazoki がある、のでそこそこ知名度があるvan Emde Boas Trees (vEB)。私の中での解釈はbit vectorを平方分割し、next / prevを付けたデータ構造。
| 赤黒木 (std::set) | vEB | bit vector (std::bitset) | |
|---|---|---|---|
| find | O(log n) | O(log log u) | O(1) |
| insert | O(log n) | O(log log u) | O(1) |
| erase | O(log n) | O(log log u) | O(1) |
| next, prev | O(log n), 平均O(1) | O(log log u) | O(u) |
| min, max | O(1) | O(1) | O(u) |
| メモリ | O(n) | O(u) | O(u) |
vEBとbit vectorは非負整数しかkeyにできない。ここでnは要素数。uはkeyの最大値。整数であるのでO(1)でbit演算も配列の参照もできる、すごい。
setのprevはイテレータ操作が必要でO(log n)保証されてないかもしれないけど普通の実装ならそうでしょう。
n個の非負整数a[0] .. a[n-1] (n <= 1e6, 0 <= a[i] <= 1e6) またはそれ以下のサイズについて、集合の操作 find / insert / erase / next / prev / min / max がstd::setより高速なデータ構造。ついでにemptyとclearができる。
int main() { VEB veb(100); veb.insert(3); veb.insert(5); veb.insert(8); veb.insert(13); if (!veb.empty()) puts("not empty"); if (veb.find(3)) puts("I have 3."); if (veb.next(4) != veb.INVALID) printf("next(4) is %u\n", veb.next(4)); if (veb.next(5) != veb.INVALID) printf("next(5) is %u\n", veb.next(5)); if (veb.prev(4) != veb.INVALID) printf("prev(4) is %u\n", veb.prev(4)); if (veb.prev(3) == veb.INVALID) printf("prev(3) is INVALID (%u)\n", veb.prev(3)); veb.erase(3); puts("erase(3)"); if (veb.min() != veb.INVALID && veb.max() != veb.INVALID) printf("min %u, max %u\n\n", veb.min(), veb.max()); unsigned u = veb.min(); while (u != veb.INVALID) { printf("I have %u\n", u); u = veb.next(u); } veb.clear(); return 0; }
出力
not empty I have 3. next(4) is 5 next(5) is 8 prev(4) is 3 prev(3) is INVALID (4294967295) erase(3) min 5, max 13 I have 5 I have 8 I have 13
wikipediaの資料から辿って読み漁った。
目的を達成するためには、過度な一般化は控えるべき。オリジナルのvEBでは葉が2要素のvEBでその上が4, 16, 256, … だと思う。メモリを節約するために葉を64要素のbit vector実装のvEBとし、その上は4096、16777216。1e7を超えた使いやすいサイズに成るのも嬉しい。
vEBはwikipediaではHeapに分類されている通り、部分木のminの値はノードに保存され、それ以外の値は子が保存する。とにかくこの条件だけ満たすようにinsert / erase を実装する。wikipediaの擬似コードを写すとあまり良くないかも。
余分な値を持たせたくなかったので、高さごとにそれぞれclassを定義する。
vEBはkeyを保存する位置がほぼ固定で、回転もなく、実装は赤黒木に比べかなり易しい印象。
コードはココにある VEB.cpp · GitHub
vEBを実装した。コンストラクタ以外はstd::setよりは高速。1e7程度の非負整数しか扱えないのでsetの代替にはできないが、ありうる問題設定だと思う。ただし多くの場合はstd::setで十分TLEに間に合うだろうが。
今回の実装は拡張が不可能。mapにすることもbagにすることもできない。
ノードを必要になるまで作らなければU = 2^64のvEBを作ることもできるがn = 1e6ではsetのほうがかなり速い。またメモリ制限のため配列は使えずHashMapを使う必要があり、問題によってHashMapを使用してよいかどうかの考察・覚悟が必要になる。適していない。
