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は何通りあるか求めよ。

続きを読む

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を使用してよいかどうかの考察・覚悟が必要になる。適していない。

両端優先度付きキューのInterval-Heap実装

ヒープ / Double-Ended Priority Queue

優先度付きキュー、使い勝手が良くヒープ実装も簡単でデータ構造の入門書に書いて有ることも多いと思う。実装したのは勉強しだした最初の頃の1回だけな気がするので復習のために実装する。
G++のstd::priority_queueはmaxを取ることのできるヒープ構造であるが、今回の実装ではmax/minのどちらでもget/popのできる「両端優先度付きキュー」 wikipedia:en:Double-ended_priority_queue を実装したい。
実装はinterval heap が実装量・実行時間・メモリすべて良さそう。
stdにあるヒープは

  • make_heap(first, last): 引数のvectorなどをヒープ構造に成るように並び替える。特に先頭を優先度最大の要素にする。
  • push_heap(first, last): [first, last-1) がヒープのときに、末端の要素をpushして[first, last)をヒープにする。
  • pop_heap(first, last): ヒープから優先度最大（先頭）の要素をpopして残りの要素でヒープにする。

これらをラップするとstd::priority_queueになるが、近いインターフェースで実装したい。両端キューにするのでget/popはget_min, get_max, pop_min, pop_max を実装することにする。

計算量

make_heap O(n)
push O(log n) amortize
pop_min, pop_max O(log n)
get_min, get_max O(1)
メモリ 2 * n * sizeof(T) + c

stdではget_minとpop_minができないのでそこが最大の違い。vectorで実装するためメモリ使用量は最大2倍としているが、データをコピーして複数持つようなことはしない。また、vectorのためpush_heapは償却計算量である。

面白いのはmake_heap、適当なデータ列が与えられたときにヒープを作るのはO(n)であるというところ。1要素づつpushしていくとO(n log n)であるところをmax-heap構造でもinterval-heap構造でもうまく実装するとO(n)に改良できる。

Interval-Heap

ヒープは木構造であるが、配列上でインデックスを操作するだけで親や子に移動できる。Interval-Heapは厳密には木構造ではない気もするがほぼ同じ。
interval-heapでは配列の偶数インデックス上にmax-heapを作り、奇数インデックス上にmin-heapを作る。
f:id:natsugiri:20161010032645p:plain
画像は9要素で作られたinterval-heapの例。矢印の始点が終点より大きい優先度を持つように適切なswapを繰り返す。
この構造はDAGでindex 0から1までの距離がO(log n)、更に次数も少なくpushやpopのときにO(log n)でヒープの条件を満たすように値を置き換えることができる。

コード

template<class T> struct PriorityQueue {
    vector<T> d;

    PriorityQueue() {}

    PriorityQueue(const vector<T> &d_) : d(d_) {
	make_heap();
    }

    template<class Iter> PriorityQueue(Iter first, Iter last) : d(first, last) {
	make_heap();
    }

    void push(const T &x) {
	int k = d.size();
	d.push_back(x);
	up(k);
    }

    void pop_min() {
	if (d.size() < 3u) {
	    d.pop_back(); 
	} else {
	    swap(d[1], d.back()); d.pop_back();
	    int k = down(1);
	    up(k);
	}
    }

    void pop_max() {
	if (d.size() < 2u) { 
	    d.pop_back();
	} else {
	    swap(d[0], d.back()); d.pop_back();
	    int k = down(0);
	    up(k);
	}
    }

    const T& get_min() const {
	return d.size() < 2u ? d[0] : d[1];
    }

    const T& get_max() const {
	return d[0];
    }

    int size() const { return d.size(); }

    bool empty() const { return d.empty(); }

    void make_heap() {
	for (int i=d.size(); i--; ) {
	    if (i & 1 && d[i-1] < d[i]) swap(d[i-1], d[i]);
	    int k = down(i);
	    up(k, i);
	}
    }

    inline int parent(int k) const {
	return ((k>>1)-1)&~1;
    }

    int down(int k) {
	int n = d.size();
	if (k & 1) { // min heap
	    while (2*k+1 < n) {
		int c = 2*k+3;
		if (n <= c || d[c-2] < d[c]) c -= 2;
		if (c < n && d[c] < d[k]) { swap(d[k], d[c]); k = c; }
		else break;
	    }
	} else { // max heap
	    while (2*k+2 < n) {
		int c = 2*k+4;
		if (n <= c || d[c] < d[c-2]) c -= 2;
		if (c < n && d[k] < d[c]) { swap(d[k], d[c]); k = c; }
		else break;
	    }
	}
	return k;
    }

    int up(int k, int root=1) {
	if ((k|1) < (int)d.size() && d[k&~1] < d[k|1]) {
	    swap(d[k&~1], d[k|1]);
	    k ^= 1;
	}

	int p;
	while (root < k && d[p=parent(k)] < d[k]) { // max heap
	    swap(d[p], d[k]);
	    k = p;
	}
	while (root < k && d[k] < d[p=parent(k)|1]) { // min heap
	    swap(d[p], d[k]);
	    k = p;
	}
	return k;
    }
};

終わりに

std::multisetでは同様の操作ができるがそれよりは機能を特化している分、効率のよいデータ構造である。復習のために書いたが両端優先度付きキューは使いどころがなさそう。今まで必要になったことがないので経験上これからも必要にならない。wikipedia先生によれば大量のデータをソートするときにpivotをメモリいっぱい取りキューに突っ込むという応用があるらし。

ACM-ICPC 2016 Asia Tsukuba Regional 国内予選 参加しなかった記

詩

寝食も忘れて、なけなしの社交性も忘れて、プログラミングコンテストに励んでいた1年前の自分、今ではすっかり更生しプログラミングコンテストに出ることも減ってしまった。しかしICPCは解かずには居られない。
※ 私は参加者・選手では無い

リンク

続きを読む