東京工業大学でTarjan教授を拝見した

講義に出席した。顔を拝むのが目的。
f:id:natsugiri:20170518155835j:plain:w500

Tarjan先生

我々が毎日書いているUnion-Findや強連結成分分解(lowlinkのやつ)の証明やらアルゴリズムやら考えたすごい人。
1時間の講義でZip Treeをマスターしよう。

Zip Tree

二分探索木の一つ。詳細な解説は講義に出た人の特権なので避けるがTreapにとても似ている。正直、名前聞いたことなかった。
Treapと比較して2つの違いがある

ランク

Treapはランダムな値を優先度としてノードに割り当てるがzip treeではそれをランクと呼ぶ。Treapでは経験上ノード1つに対してO(log n)ビットの追加メモリが必要だが、Zip TreeはO(log log n)ビット、多分。。。
実装ではこんな感じでいいだろうか?Treapのランクが32ビットなのに対し、Zip Treeは31以下(5ビット)で済んでいる。Treapで乱数の下位5ビットにすると壊滅する。

mt19937 engine;

int zip_tree_rnk() {
    unsigned x = engine() | (1u<<31);
    return __builtin_ctz(x);
}

int treap_rnk() {
    return engine();
}

insert / delete

名にZipを冠するがinsert / deleteの操作から来ているようだ。トップダウンでできるのでループ処理で実装するのが簡単なはず。実装は一番下。

実装・実行

Insert 200000

Treap
Height 42; Ave. depth 21.255840;

Zip Tree
Height 52; Ave. depth 22.656550;

実装量はほぼ同じ。実装安を目指したので値の重複を許してinsertされる再帰関数にしてしまったためZipTreeがやや遅いかもしれない。ランクは結局どちらもintで持たせたので省メモリの恩恵を受けていない。
上記の実装上の2つの違いは独立で、Treapの実装で1つだけ変更を加えてやるとかもできる。

実装は上半分がTreap、下半分がZip Tree。より良い実装はそのうち考える。

#include<climits>
#include<cassert>
#include<set>
#include<random>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;

typedef long long LL;

//////////////////////////////////////////////////
// Common;
//////////////////////////////////////////////////

mt19937 engine(19480430);

struct Node {
    int val;
    int rnk;
    Node *l, *r;
    Node(int val_, int rnk_) : val(val_), rnk(rnk_), l(0), r(0) {}
};

typedef Node* Tree;

Tree find(Tree t, int val) {
    while (t) {
	if (val < t->val) {
	    t = t->l;
	} else if (t->val < val) {
	    t = t->r;
	} else {
	    return t;
	}
    }
    return 0;
}


//////////////////////////////////////////////////
// Treap;
//////////////////////////////////////////////////

// Subfunctions;
Tree rotate_right(Tree x) {
    Tree y = x->l;
    x->l = y->r;
    y->r = x;
    return y;
}

Tree rotate_left(Tree x) {
    Tree y = x->r;
    x->r = y->l;
    y->l = x;
    return y;
}

Tree treap_erase_minimum(Tree t, Tree y) {
    if (!t->l) {
	y->val = t->val;
	y->rnk = t->rnk;
	Tree x = t->r;
	delete t;
	return x;
    } else {
	t->l = treap_erase_minimum(t->l, y);
	return t;
    }
}

Tree treap_balance(Tree t) {
    if (t->l && t->rnk <= t->l->rnk && (!(t->r) || t->l->rnk >= t->r->rnk)) {
	t = rotate_right(t);
	t->r = treap_balance(t->r);
    } else if (t->r && t->rnk < t->r->rnk) {
	t = rotate_left(t);
	t->l = treap_balance(t->l);
    }
    return t;
}

// Main functions;
int treap_rnk() {
    return engine();
}

Tree treap_insert(Tree t, int val, int rnk) {
    if (!t) {
	return new Node(val, rnk);
    } else {
	if (val < t->val) {
	    t->l = treap_insert(t->l, val, rnk);
	    return (t->l->rnk >= t->rnk? rotate_right(t): t);
	} else {
	    t->r = treap_insert(t->r, val, rnk);
	    return (t->r->rnk > t->rnk? rotate_left(t): t);
	}
    }
}

Tree treap_erase(Tree t, int val) {
    if (!t) {
	return 0;
    } else {
	if (val < t->val) {
	    t->l = treap_erase(t->l, val);
	    return t;
	} else if (t->val < val) {
	    t->r = treap_erase(t->r, val);
	    return t;
	} else if (!t->l || !t->r) {
	    Tree x = (t->l?: t->r);
	    delete t;
	    return x;
	} else {
	    t->r = treap_erase_minimum(t->r, t);
	    return treap_balance(t);
	}
    }
}

//////////////////////////////////////////////////
// Zip Tree;
//////////////////////////////////////////////////

// Subfunctions;
Tree unzip_insert_root(Tree t, int val, int rnk) {
    Tree x = new Node(val, rnk);
    Tree low = x, high = x;
    while (t) {
	if (val < t->val) {
	    high = high->l = t;
	    t = t->l;
	} else {
	    low = low->r = t;
	    t = t->r;
	}
    }
    low->r = high->l = 0;
    swap(x->l, x->r);
    return x; 
}

Tree zip_erase_root(Tree t) {
    bool b = false;
    Tree x = t;
    Tree low = t->l, high = t->r;
    while (low && high) {
	if (low->rnk < high->rnk) {
	    (b? x->r: x->l) = high;
	    x = high;
	    b = false;
	    high = high->l;
	} else {
	    (b? x->r: x->l) = low;
	    x = low;
	    b = true;
	    low = low->r;
	}
    }
    (b? x->r: x->l) = (low?: high);
    x = t->l;
    delete t;
    return x;
}

// Main functions;
int zip_tree_rnk() {
    unsigned x = engine() | (1u<<31);
    return __builtin_ctz(x);
}

Tree unzip_insert(Tree t, int val, int rnk) {
    if (!t) {
	return new Node(val, rnk);
    } else if (val < t->val) {
	if (t->rnk <= rnk) {
	    return unzip_insert_root(t, val, rnk);
	} else {
	    t->l = unzip_insert(t->l, val, rnk);
	    return t;
	}
    } else {
	if (t->rnk < rnk) {
	    return unzip_insert_root(t, val, rnk);
	} else {
	    t->r = unzip_insert(t->r, val, rnk);
	    return t;
	}
    }
}

Tree zip_erase(Tree t, int val) {
    if (!t) {
	return 0;
    } else if (val < t->val) {
	t->l = zip_erase(t->l, val);
	return t;
    } else if (t->val < val) {
	t->r = zip_erase(t->r, val);
	return t;
    } else {
	return zip_erase_root(t);
    }
}

//////////////////////////////////////////////////
// Debug;
//////////////////////////////////////////////////
double depth_sum;
int height(Tree t, int depth=0) {
    if (t) {
	depth_sum += depth;
	return max(height(t->l, depth+1), height(t->r, depth+1)) + 1;
    } else {
	return -1;
    }
}

void show(Tree t, int depth=0) {
    if (t) {
	show(t->l, depth+1);
	for (int i=0; i<depth; i++) printf("..");
	printf("%d\n", t->val);
	show(t->r, depth+1);
    }
}

int last;
void verify(Tree t) {
    if (t && t->l) {
	assert(t->l->val <= t->val);
	assert(t->l->rnk < t->rnk);
	verify(t->l);
    }

    assert(last <= t->val);
    last = t->val;

    if (t && t->r) {
	assert(t->val <= t->r->val);
	assert(t->rnk >= t->r->rnk);
	verify(t->r);
    }
}

const int SIZE = 200000;
int A[SIZE];
int cnt[32];

int main() {
    int cc = 0;
    printf("Insert %d\n", SIZE);
    puts("");

    for (int i=0; i<SIZE; i++) A[i] = engine();

    // Empty Tree;
    Tree treap = 0;

    for (int i=0; i<SIZE; i++) {
	int k = treap_rnk();
	treap = treap_insert(treap, A[i], k);
	cc++;
    }
//    for (int i=0; i<SIZE/2; i++) {
//	treap = treap_erase(treap, A[i]);
//	cc--;
//    }

    last = INT_MIN;
    verify(treap);

    printf("Treap\n");
    int h = height(treap);
    printf("Height %d; Ave. depth %f;\n", h, depth_sum / cc);
    puts("");

    // Empty Tree;
    Tree zipTree = 0;

    cc = 0;
    for (int i=0; i<SIZE; i++) {

	int k = zip_tree_rnk();
	cnt[k]++;
	zipTree = unzip_insert(zipTree, A[i], k);
	cc++;
    }
//    for (int i=0; i<SIZE/2; i++) {
//	zipTree = zip_erase(zipTree, A[i]);
//	cc--;
//    }

    // show(zipTree);

    last = INT_MIN;
    verify(zipTree);

    printf("Zip Tree\n");
    depth_sum = 0;
    h = height(zipTree);
    printf("Height %d; Ave. depth %f;\n", h, depth_sum / cc);
    puts("");
    puts("");

    printf("rnk distribution\n");
    for (int i=0; i<32; i++) printf("%d%c", cnt[i], i==31?'\n':' ');


    return 0;
}

Codechef April Challenge 2017 解法

Chef and Digits

Problem Code: DGTCNT
各数字が出現した回数を覚えるような桁DPで攻めると駄目。
数字の集合S subset {0,...,9}を決めたとき、F(S, N):=#{Sに含まれる数字の出現回数が条件に一致するような0超過N以下の数}を求める。このときSに含まれないものはどうなってもいいとして、包除原理で辻褄があう。
F(S, N)は組合せを駆使して求める。
L以上R以下の条件があるので、solve(N) = \sum_S mu(S) F(S, N)とした時にsolve(R) - solve(L-1)が解。ただしmu(S):=(-1)^|S|。

(CH) Serejs and Billiards

Problem Code: SEABIL
タイブレーク。ビリヤード。衝突すると値を吸収するのでどちらかと言えば雪だるま?
対角線に集める→最後の一突きでポケットに落とす、この方針でよい。
各行に対して、一突きで全てまとめて対角線に移動させる。これでN+1回で全ての玉を落とせる。
負のボールは巻き込まないようにずらすとスコアがよくなる。

Editorialが空。トップスコアの九分九厘九毛取らなければ上位になれない、辛い。

Heavy-Light Decomposition

Problem Code: HLD
知識として、HLDのクエリ計算量がO(log^2 n)なので解の上限はO(log^2 n)である。

dp[v][i] := x; 頂点vの上に長さxのheavy edgeを付けてもスコアはi以下

これを木DP。
iの上限を100で見積もるとWA、200だとTLEした。200で多少の枝刈りしてAC。

つまり、N=1e5のHLDのクエリは100を超えるノードを読む必要があるということ、最小のHLDでなかったり、segment treeを置いたりすると200を超えることもありそう。

MM 93 CrossStitch

TopCoder
Marathon Match 93 CrossStitchに参加した。

問題概要

クロスステッチと呼ばれる刺繍を作る。
入力で模様が与えられる。各色の糸ごとに布の表と裏を交互に移動して一筆書する。
表の糸の長さは入力で固定、裏の糸の長さをなるべく短くせよ。
f:id:natsugiri:20170318151719p:plainf:id:natsugiri:20170318152720p:plain
図1枚目:入力例。図2枚目:出力例。

解答案

色ごとに独立に解く。1セルを頂点として巡回セールスマン問題(TSP)を解き、経路を求める。1セルの2つのステッチ(対角線)は必ず連続で描くことにして、TSPの順に糸を通す。

細部1

糸を直前と同じ位置に通すと抜けてしまうので、布の裏では必ず長さ1以上移動しなければならない制約がある。セル(x, y)について

  • x+y が偶数:左上→右下→右上→左下
  • x+y が奇数:左下→右上→右下→左上

の順で糸を通せばよい。
しかし、もっとスコアの良い方法がある。セルのクロスの向きと順番を、裏の制約を満たすように動的計画法で最適解を求める。

細部2

巡回セールスマン問題は簡単なクラスカル法に似た2-optを採用。

  1. 全ての頂点ペアを列挙、距離昇順にソート
  2. 頂点ペアを順番に見て、枝分かれしない・サイクルを作らないなら繋ぐ。パスが一つになるまで繰り返す。
  3. パスに対して、2辺(u, v), (w, x)を選び、改善するなら(u, w), (v, x)と繋ぎ変える。更新できる限り繰り返す。

2-optを4重ループで書いたが結構速い。頂点が少ないのか、それとも繋ぎ変えの回数が少ないのかわからない。

void refinePath() {
    bool update = false;
    int n = path.size();
    do {
	update = false;
	for (int i=0; i<n-2; i++) for (int j=i+2; j<n-1; j++) {
	    if (dist(path[i], path[i+1]) + dist(path[j], path[j+1]) >
		    dist(path[i], path[j]) + dist(path[j+1], path[i+1])) {
		reverse(path.begin() + i + 1, path.begin() + j + 1);
		update = true;
	    }
	}
    } while (update) ;
}

pathはTSPの頂点順列。

ビジュアライザ

与えられたもので十分。ただ、一色だけ表示できるようにした。
f:id:natsugiri:20170318153142p:plain

データ構造のコンストラクタの書き方

c++0x書き始めた。データ構造書くたびに検索するのも効率悪いので覚える。

実態を持つ

データが小さいときはあり。しかし特にサイズが大きい配列を持つと良くない、局所変数にしづらい。

template<int SIZE> struct Array {
    int d[SIZE];

    Array() { 
	// primitive型の場合はmemsetでもいい
	fill(d, d+SIZE, 0);
    }

    Array(const Array &y) {
	// primitive型の場合は memcpy でもいい
	for (int i=0; i<SIZE; i++) d[i] = y.d[i];
    }

    // yは変更可能。ポインタが無いので特に必要ない
    Array(Array &&y) {
	for (int i=0; i<SIZE; i++) {
	    d[i] = y.d[i];
	    y.d[i] = 0;
	}
    }

    // メモリを動的に確保してないので不要
    ~Array() {}

    Array& operator=(const Array &y) {
	for (int i=0; i<SIZE; i++) d[i] = y.d[i];
	return *this;
    }
};

ポインタで持つ NULLを許さない

大分stlに近くて良い。

template<int SIZE> struct Array {
    int *d;

    Array() : d(new int[SIZE]()) {}

    Array(const Array &y) : d(new int[SIZE]) {
	for (int i=0; i<SIZE; i++) d[i] = y.d[i];
    }

    Array(Array &&y) : d(new int[SIZE]) {
	// yはゴミが入ることになるが有効
	swap(*this, y);
    }

    ~Array() {
	delete[] d; 
	d = nullptr;
    }

    Array& operator=(Array y) {
	swap(*this, y);
	return *this;
    }

    friend void swap(Array &x, Array &y) {
	swap(x.d, y.d);
    }
};

ポインタで持つ NULLを許す

NULLでも問題ない場合や可変長なデータ構造なら良い。そうでない場合はメモリ確保を利用者に任せる。運用でカバー。
デフォルトコンストラクタと右辺値代入が効率良くなる可能性があるが計算量は変わらない。

template<int SIZE> struct Array {
    int *d;

    Array() : d(nullptr) {}

    Array(const Array &y) : d(nullptr) {
	if (y.d) {
	    reserve();
	    for (int i=0; i<SIZE; i++) d[i] = y.d[i];
	}
    }

    Array(Array &&y) : d(nullptr) {
	// yはNULLになる
	swap(*this, y);
    }

    ~Array() { clear(); }

    void clear() {
	if (d) {
	    delete[] d;
	    d = nullptr;
	}
    }

    void reserve() {
	clear();
	d = new int[SIZE]();
    }

    Array& operator=(Array y) {
	swap(*this, y);
	return *this;
    }

    friend void swap(Array &x, Array &y) {
	swap(x.d, y.d);
    }
};

チェックリスト

  1. コンストラクタ
    1. Array() デフォルトコンストラクタ
    2. Array(const Array &) コピーコンストラクタ
    3. Array(Array &&) moveコンストラクタ。swapだけで実装し、O(1)であると嬉しい。
  2. デストラクタ
  3. void swap(Array &, Array &) はO(1)。
  4. Array&operator=(Array)はswapするだけ。引数のコピーはコンストラクタに任せる。
  5. sizeof (Array) は空間計算量O(1)であるべき。配列を直接持っていなければOK。配列はポインタ・std::vectorに。

ACM-ICPC 2016 Asia Tsukuba Regional, 解法目次

ACM-ICPC 2016 Asia Tsukuba Regional Informal Solutions

はじめに

2016/10/16にICPC地区予選つくば大会が開催された。出題された問題に興味がある、と言うより部外者なので問題を解くしかやることがないので問題のことだけ書く。1週間経ってオンサイト参加者はすでに復習を終わらせているだろうが、来年以降の地区予選を目指すチームの手助けになれば幸いだし、ならなくても幸い。
オンサイトでは解説があったはずだが見ることができなかったので非公式解法ということで。

続きを読む

ACM-ICPC 2016 Asia Tsukuba Regional, K 解法

K: Black and White Boxes

問題

アリスとボブがゲームをする。
箱が縦に一列に積み上げられており、各箱の色は白か黒である。この一列を山と呼び、山が複数ある。二人で交互に箱を取り除く。

  • アリスは黒箱を1つ選んで、その箱とその上に積んであるすべての箱を取り除く。
  • ボブは白箱を1つ選んで、その箱とその上に積んであるすべての箱を取り除く。
  • 自分の手番で取り除くことができなくなったら負け。
  • 二人は勝つために最適な行動をする。

先手のプレイヤーを任意にした場合、アリスにもボブにも勝つ可能性があるようなゲームはfairであるという。

n個の山が与えられるのでその中から0個以上選択してfairなゲームを見つけ、fairなゲームの初期状態の箱の数の最大値を求めよ。

続きを読む

ACM-ICPC 2016 Asia Tsukuba Regional, J 解法

J: Cover the Polygon with Your Disk

問題

円と凸多角形が与えられる。凸多角形の頂点は10個以下。それぞれ自由に平行移動・回転移動させて、共通部分の面積の最大値を出力せよ。
入力は整数で座標は0~100、円の半径は1~100。

続きを読む