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

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