読者です 読者をやめる 読者になる 読者になる

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。

続きを読む

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

続きを読む