CSAcademy Foxes on a Wheel

csacademy.com

＜問題＞
の頂点をもつグラフがある。
頂点は頂点と繋がっていて、
頂点 は頂点とつながっている。
また、グラフは円状になっていて、頂点と頂点はつながっている。

このグラフの頂点上に、匹のキツネの居場所と個の隠れ家が与えられる。
それぞれのキツネを隠れ家と対応させたとき、その距離の和が最小になる時の値はいくらか。

＜解説＞
出来る限り隣接しているキツネと家を割り当てて（距離１）
のこりは適当に割り当てます。（すべて距離２なので）
単純なループで割り当てればよいですが、
index1にキツネがいた際に、
家キツネ(index1)家キツネ
のような場合には、左のキツネは左の家をとるようにする必要があるため、
キツネ家キツネ(index1)家
の場合には右の家をとる必要があります。
そこで、頂点１で左右の場合分けを行います。

＜コード＞

int main() {

	int n, k;
	cin >> n >> k;

	vi f(n + 1), h(n + 1);
	rep(i, k) {
		int a;
		cin >> a;
		f[a] = 1;
	}
	rep(i, k) {
		int a;
		cin >> a;
		h[a] = 1;
	}

	int pair = 0;
	for (int i = 1; i < n; i++) {
		if ( (f[i] && h[i+1]) || (f[i+1] && h[i])) {
			i++;
			pair++;
		}
	}

	int pair2 = 0;
	if ((f[1] && h[n]) || (f[n] && h[1]))pair2++;
	for (int i = n - 1; i > 2; i--) {
		if ( (f[i] && h[i - 1]) || (f[i - 1] && h[i]) ) {
			i--;
			pair2++;
		}
	}

	P(2 * k - max(pair, pair2));
	return 0;
}

＜感想＞
×思考停止フロー流すだけ