キーエンス プログラミング コンテスト 2020 D - Swap and Flip
0-originで考えます.
制約からメタ読みするとどうせ かけて列挙するので,並べ替えた後の列で表が赤になるカードの集合を 通りを決め打ちます.「このような並べ方が存在するか?存在するならば何回のswapで達成可能か?」という問題が解ければよいことになります.
並べ方が存在するか?
元の列の位置の偶奇と並べ替えた後の列の偶奇が
- 一致する: 赤が表
- 一致しない: 青が表
となります.したがって,各数字が偶数/奇数番目に来る個数が何個になっていればokな並べ方か?ということを求めることができます.実際に を並べ,ソートした列と比較することで判定が可能です.
swapは何回か?
隣接する2項のswapで求める列をつくる回数は,ようするに転倒数です.並べ替えた後, 番目のカードがどこに行くのか?は実際にソートすればわかるので,あとは かけて転倒数を求めればよいです.
#include <bits/stdc++.h> using namespace std; using ll = long long; using PII = pair<ll, ll>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() template<typename T> void chmin(T &a, const T &b) { a = min(a, b); } template<typename T> void chmax(T &a, const T &b) { a = max(a, b); } struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio; #ifdef DEBUG_ #include "../program_contest_library/memo/dump.hpp" #else #define dump(...) #endif const ll INF = 1LL<<60; int main(void) { ll n; cin >> n; vector<ll> a(n), b(n); REP(i, n) cin >> a[i], a[i]--; REP(i, n) cin >> b[i], b[i]--; ll ret = INF; REP(i, 1LL<<n) { vector<ll> v; vector<PII> need(50), v0, v1; REP(j, n) { if(i&1LL<<j) { v.push_back(a[j]); if(j%2==0) { need[a[j]].first++; v0.push_back({a[j], j}); } else { need[a[j]].second++; v1.push_back({a[j], j}); } } else { v.push_back(b[j]); if(j%2==0) { need[b[j]].second++; v1.push_back({b[j], j}); } else { need[b[j]].first++; v0.push_back({b[j], j}); } } } sort(ALL(v)); vector<PII> vp(50); REP(j, n) { if(j%2==0) vp[v[j]].first++; else vp[v[j]].second++; } if(need != vp) continue; // 何手かかるか? sort(ALL(v0)); sort(ALL(v1)); vector<ll> sorted; REP(i, max(v0.size(), v1.size())) { if(i < v0.size()) sorted.push_back(v0[i].second); if(i < v1.size()) sorted.push_back(v1[i].second); } dump(bitset<3>(i)); dump(sorted); ll tmp = 0; vector<ll> num(n); REP(j, n) { FOR(k, sorted[j], n) { tmp += num[k]; } num[sorted[j]]++; } chmin(ret, tmp); } if(ret == INF) cout << -1 << endl; else cout << ret << endl; return 0; }