AGC001D: Arrays and Palindrome

https://agc001.contest.atcoder.jp/tasks/agc001_d

これ知識的には誰でも解けるけど結構思考しないといけなくて面白い。

同じにならないといけない文字同士を結ぶグラフを考えると、直線+ループになる。これは各点の次数が2以下であることから示せる。
なので奇数が2つ以上あると、グラフが連結にならず、Impossibleになる。
今奇数が2以下だとする。
全部の点を1本の直線で結びたいのだが、奇数を端に置いて、最初の文字数を1増やして最後の文字数を1減らすとうまくいく。

あとはM=1の時や、最後の文字数が1の時を注意して実装すればいいです。

N=1コーナーケースだと思いましたが、そんなことはなかった…

int N, M;
vi odd, even;

void solve() {
	cin >> N >> M;
	rep(i, 0, M) {
		int a; cin >> a;
		if(a % 2) odd.pb(a);
		else even.pb(a);
	}
	if(sz(odd) <= 2) {
		vector<int> ans;
		vector<int> ord;
		if(sz(odd) == 0) {
			ans.pb(1);
			rep(i, 0, sz(even)) {
				ord.pb(even[i]);
				ans.pb(even[i]);
			}
			ans[M]--;
		}
		else if(sz(odd) == 1) {
			ans.pb(1);
			rep(i, 0, sz(even)) {
				ord.pb(even[i]);
				ans.pb(even[i]);
			}
			ord.pb(odd[0]);
			if(odd[0] != 1) ans.pb(odd[0] - 1);
		}
		else {
			ans.pb(odd[0] + 1);
			ord.pb(odd[0]);
			rep(i, 0, sz(even)) {
				ord.pb(even[i]);
				ans.pb(even[i]);
			}
			ord.pb(odd[1]);
			if(odd[1] != 1) ans.pb(odd[1] - 1);
		}
		rep(i, 0, sz(ord)) {
			cout << ord[i] << " ";
		}
		cout << "\n";
		cout << sz(ans) << "\n";
		rep(i, 0, sz(ans)) {
			cout << ans[i] << " ";
		}
		cout << "\n";
	}
	else {
		cout << "Impossible\n";
	}
}