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

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。

続きを読む

ACM-ICPC 2016 Asia Tsukuba Regional, H 解法

H: Animal Companion in Maze

問題

グラフが与えられる。辺は有向のものと無向(双方向)のものがある。長さは全て1。
無向辺を通ったときにすぐ同じ辺を引き返してはならないとき、最長歩道の長さを出力せよ。
歩道とは頂点・辺の重複を許したパスのこと。
答えを無限に大きくできる場合はInfiniteと出力せよ。

続きを読む

ACM-ICPC 2016 Asia Tsukuba Regional, G 解法

G: Placing Medals on a Binary Tree

問題

深さ10^9の完全二分木がある。根の深さは0、葉の深さは10^9。n個のメダルを順番に頂点に置いていく。このとき、部分木にメダルがある頂点には置くことができない。また頂点の深さはメダルに書かれている数と等しくなければならない。すでに置いてあるメダルを深さを変えずに他の頂点に移してもよい。
メダルを順番に置けるなら置いていく。それぞれ、置いたらYes。そうでないならNoを出力せよ。
n <= 5 * 10^5

続きを読む

ACM-ICPC 2016 Asia Tsukuba Regional, F 解法

F: Three Kingdoms of Bourdelot

問題

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

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

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

続きを読む