概要
カードがN枚ある。i番目のカードの表面には1以上の整数A[i]が、裏面には1以上の整数B[i]がそれぞれ記載されている。
最初、全てのカードが表面を上にして置かれている。この状態から次の操作を好きなだけ繰り返し、見えているカードの数字が広義単調増加となるようにできるとき、操作回数の最小値を求めよ。
- 隣同士となっているカードを選び、それらを交換したのち、それらのカードを裏返す
制約
1 ≦ N ≦ 18
1 ≦ A[i], B[i] ≦ 50
方針
仮に裏表の区別がない場合は、{1, 2, ..., N}のカードが{p(1), p(2), ... p(n)}の位置になった場合、{p(1), p(2), ... p(n)}の転倒数が答えとなる。
転倒数の解説は下記を参考にしました。
ikatakos.com
実は、各カードは最終的な位置により表裏が一意に定まる。具体的には最初の状態でi番目のカードがj番目になるとき、iとjの偶奇が同じ⇒表面 それ以外⇒裏面 となる。
なので、カードの順列を与える⇒裏表が一意に決まる⇒その数列が広義単調増加なら転倒数が答えの候補 と考えることができる。しかし、このままだと順列を与えることになり、計算が間に合わない。
bitDPが使える。dp[bit][j] を次のように定義する。
bit: n桁の2進数、桁iが1⇔i番目のカードがすでに使用される（使用されたカードは未使用のカードより左にあり、かつソートされている）
j :すでに使用されたカードの最大値
dp[bit][j] 上記bit, j の下で、それまでに使用されたカードの転倒数の最小値
dpは配るdpで実装する。
各bitのループの最初にまだ使用されていないカードについてもともとの位置とbit状態での位置（使用されているカードがあるため、最初の状態から位置が変わる）を記憶しておく。
使用されていない全てのカードについて、使用されたカードの最後尾に置くことができる(裏表考慮後のカードの数字がj以上であるならOK)場合は、dpを更新する。このときdpには現在のカードの転倒数が加算される。使用されたカードをcnt枚、そのカードの現在の位置をp.secondとすると、con番目以降のカードは初期状態のままであり、p.secondカードと順位が逆転することになるため、そのカードの枚数分（p.second - con）転倒数に加算される。
感想
けんちょんさんのブログを大いに参考にしました。
drken1215.hatenablog.com
解答
Submission #9948554 - Keyence Programming Contest 2020
#include <bits/stdc++.h> #define rep(i,n) for(int i=(0);i<(n);i++) using namespace std; typedef long long ll; typedef pair<int, int> pii; int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; int a[n], b[n]; rep(i, n) cin >> a[i]; rep(i, n) cin >> b[i]; int max_bit = (1 << n) - 1; int max_a = 52; int dp[max_bit + 1][max_a + 1]; int INF = 1010101; rep(i, max_bit + 1) rep(j, max_a+1) dp[i][j] = INF; dp[0][0] = 0; rep(bit, max_bit + 1){ int cnt = __builtin_popcount(bit); int t = cnt; vector<pii> v; rep(i, n){ if(!((bit >> i) & 1)){ v.push_back({i, t++}); } } rep(j, max_a + 1){ if(dp[bit][j] == INF) continue; for(pii p : v){ int ns; if(abs(p.first - cnt) % 2 == 0){ ns = a[p.first]; }else{ ns = b[p.first]; } if(ns >= j){ dp[bit | (1 << p.first)][ns] = min(dp[bit | (1 << p.first)][ns], dp[bit][j] + (p.second - cnt)); } } } } int ans = INF; rep(i, max_a+1) ans = min(ans, dp[max_bit][i]); if(ans == INF) ans = -1; cout << ans << endl; }
