MM 93 CrossStitch

TopCoder
Marathon Match 93 CrossStitchに参加した。

問題概要

クロスステッチと呼ばれる刺繍を作る。
入力で模様が与えられる。各色の糸ごとに布の表と裏を交互に移動して一筆書する。
表の糸の長さは入力で固定、裏の糸の長さをなるべく短くせよ。

図１枚目：入力例。図２枚目：出力例。

解答案

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

細部１

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

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

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

細部２

巡回セールスマン問題は簡単なクラスカル法に似た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の頂点順列。

ビジュアライザ

与えられたもので十分。ただ、一色だけ表示できるようにした。