ACM-ICPC 2016 Asia Tsukuba Regional, F 解法

F: Three Kingdoms of Bourdelot

問題

複数のドキュメントがある。各ドキュメントには家系図の情報が複数行書かれている。ドキュメントは正と負の2種類あり、各行はペア(x, y)であり、

  • ドキュメントが正の場合:xはyの祖先である
  • ドキュメントが負の場合:xはyの祖先ではない

を意味する。
各ドキュメントはそれぞれについて、正か負わからない。n個のドキュメントと二人の人p, qが与えられたとき、pがqの祖先であるような無矛盾なドキュメントの正負の割当があるかどうか判定せよ。

続きを読む

ACM-ICPC 2016 Asia Tsukuba Regional, E 解法

E: Infallibly Crack Perplexing Cryptarithm

問題

虫食い等式が与えられる。数式は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以下。

続きを読む

ACM-ICPC 2016 Asia Tsukuba Regional, D 解法

D: Hidden Anagrams

問題

2つの同じ長さの文字列が、各アルファベットの出現数が同じであるとき、互いにアナグラムであると言う(多分同じ文字列もアナグラムという)。
2つの文字列が与えられる。それぞれから部分文字列を取り出して、それらがアナグラムであるようなとき、その部分文字列の長さの最大値を求めよ。
アルファベットはa~z、文字列の長さはそれぞれ4000以下。10sec。

続きを読む

ACM-ICPC 2016 Asia Tsukuba Regional, C 解法

C: Distribution Center

問題

n本のコンベアラインが平行に並んでいる。各ラインiの左から製品iが右に向かって流れる。またm台のロボットが配置されてある。ロボットjは左からxjの位置にあり、ラインyj, yj+1の製品をそれぞれ反対のラインに移す事ができる。xjは互いに異なる。
ロボットを好きなタイミングで動かしたり止めたりして良いとき、各ラインには何種類の製品を流すことができるか。

続きを読む

ACM-ICPC 2016 Asia Tsukuba Regional, B 解法

B: Quality of Check Digits

問題

一桁の数同士のX演算の定義テーブルが与えられる。iXi = 0が保証されている(i = 0 .. 9)。ある4桁の数 abcd (leading zerosを許す) に対して、e = (((0Xa)Xb)Xc)XdをCheckDigitとして5桁のabcdeについて、書き間違えを判定したい。

  • Type1: ある一桁を別の一桁の数に書き間違える (e.g. 20163 -> 00163)
  • Type2: 隣り合う異なる数を逆に書き間違える (e.g. 20163 -> 02163)

「上の任意の書き間違えを1回したら検出できる」とは限らないabcdは何通りあるか求めよ。

続きを読む

ACM-ICPC 2016 Asia Tsukuba Regional, A 解法

A: Rearranging a Sequence

問題

始めに数列1 … n がある。「数e_iを先頭に移動させる」と言う操作をm回行う(1 <= i <= m)。最後の数列を出力せよ。

続きを読む

van Emde Boas Trees を実装する

はじめに

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ができる。

使い方

  • コンストラクタにn <= 2^24の値をあげると0~n-1の整数の集合として扱う
  • 初期値は空
  • sizeやコピーコンストラクタ、デストラクタは無い
  • next / prev / min / max は値が存在しない場合はINVALID (= 2^32 - 1) を返す
  • insert / eraseは要素の有無が変更された場合trueを返す
  • keyはunsignedなのでnext(-1)などやってはならない
  • 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を使用してよいかどうかの考察・覚悟が必要になる。適していない。