문제
BOJ 14458(https://www.acmicpc.net/problem/14458)
이분 그래프 형태로 양 쪽에 정점이 각각 $n$개씩 있고, 각 간선들은 모두 일대일 대응 형태로 주어진다.
양쪽의 정점들은 원형 형태로 회전시킬 수 있으나, 한 쪽만 임의의 $k$만큼 회전시키는게 가능하다.
이 때, 회전을 시킨 후 간선들이 교차되는 최소값을 찾아야 한다.
문제 분석
일대일 대응, 간선의 교차를 보면 가장 먼저 생각나는게 빈도수를 체크하기 좋은 Fenwick Tree이다.
간선의 교차라는 것은 즉, 어떤 간선이 $(u, v)$를 잇고 있을 때
-
$u$ 이전에서 시작한 간선이 $v$ 이후로 간다.
-
$u$ 이후에서 시작한 간선이 $v$ 이전으로 간다.
즉, 다음 두 가지 형태 중 하나로 간선의 교차가 이루어진다.
초기 상태에서의 간선의 교차 세기
우선 $k$만큼 정점을 회전시키는 건 나중에 하고, 처음 상태에서 간선의 교차 수를 세보자.
간선의 교차가 이루어지는 방식은 위에서 말한대로이고, 이것을 토대로 총 교차 수를 세면 되는데, 방법은 각각의 정점을 기준으로 $u$이후의 정점에서 시작해서 $v$이전으로 가는 것을 세서 전부 더할 것이다.
위 두 가지 경우 중 하나만 구한 이유는, 두 가지 모두 세버리면 중복이 생기기 때문이다.
이것을 편하게 구현하는 방법은 바로 Fenwick Tree를 이용하는 것이다.
Fenwick Tree의 “$u$이후에서 시작하는 간선들의 끝점”의 idx에 1을 표기해주면, $v$이전의 정점들의 수를 쉽게 계산 할 수 있다.
k번의 회전
양 쪽 중 하나만 회전시킬 수 있으므로, 우선 오른쪽만 회전시키는 경우를 생각하면 왼쪽을 회전시키는 경우는 같은 방법을 사용하여 쉽게 구할 수 있을 것이다.
현재 상태에서의 교차 간선의 수는 이미 구해져있다고 가정했을 때, 다음 $1$번을 회전하면 그 수가 어떻게 변하는지를 알 수 있으면, $n$번 회전을 시켜보며 그 값을 쉽게 구할 수 있을 것이다.
그런데 잘 보면, 회전을 할 때는 오른쪽의 맨 끝 정점만 맨 앞으로 옮겨짐을 알 수 있다.
현재 회전 대상인 정점을 잇는 간선에 대해서 왼쪽 정점의 idx를 $left$, 오른쪽 정점의 idx를 $right$라고 하면
항상 $right = n-1$ 일 것이고, 이 때 현재 이 간선으로 인해 생긴 교차의 수는 $left$개 라는 것을 알 수 있다.
또한 $right$를 $0$으로 회전시켰을 경우 생기는 새로운 교차의 수는 $n-left-1$개 라는 것을 알 수 있다.
즉, 새로운 총 교차의 수는 이전 교차의 수에서 현재 간선으로 인해 생긴 교차의 수를 뺀 뒤 새로 생기는 교차의 수를 더해주면 구할 수 있다.
소스코드
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL_BOOKNU
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
// ........................macro.......................... //
#define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
#define pb push_back
#define emb emplace_back
#define fi first
#define se second
#define ENDL '\n'
#define sz(A) (int)(A).size()
#define ALL(A) A.begin(), A.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
#define next next9876
#define prev prev1234
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef long long i64;
typedef unsigned long long ui64;
// inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
const i64 MOD = 1e9+7;
inline i64 POW(i64 a, i64 n) {
assert(0 <= n);
i64 ret;
for(ret = 1; n; a = a*a%MOD, n /= 2) { if(n%2) ret = ret*a%MOD; }
return ret;
}
template <class T> ostream& operator<<(ostream& os, vector<T> v) {
os << "[";
int cnt = 0;
for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
return os << "]";
}
template <class T> ostream& operator<<(ostream& os, set<T> v) {
os << "[";
int cnt = 0;
for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
return os << "]";
}
template <class L, class R> ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
// ....................................................... //
struct fenwick {
int n;
vi t;
void init(int _n) {
n = _n;
t.assign(n+1, 0);
}
void add(int u, int x) {
for(++u; u < t.size(); u += (u&-u)) {
t[u] += x;
}
}
int sum(int u) {
int ret = 0;
for(++u; u > 0; u -= (u&-u)) {
ret += t[u];
}
return ret;
}
};
const int MAXN = 1e5+10;
int n, ar[MAXN], br[MAXN], pa[MAXN], pb[MAXN];
fenwick ft;
void input() {
cin >> n;
FOR(i, 0, n) {
int x; cin >> x; --x;
ar[i] = x;
pa[x] = i;
}
FOR(i, 0, n) {
int x; cin >> x; --x;
br[i] = x;
pb[x] = i;
}
}
i64 getans() {
ft.init(n);
FOR(i, 0, n) ft.add(i, 1);
i64 sum = 0;
FOR(i, 0, n) {
ft.add(pb[ar[i]], -1);
sum += ft.sum(pb[ar[i]]);
}
i64 ans = sum;
RFOR(i, n-1, 0) {
sum += pa[br[i]];
sum -= (n-pa[br[i]]-1);
ans = min(ans, sum);
}
return ans;
}
int solve() {
i64 ans = getans();
FOR(i, 0, n) {
int t = ar[i];
ar[i] = br[i];
br[i] = t;
t = pa[i];
pa[i] = pb[i];
pb[i] = t;
}
ans = min(ans, getans());
cout << ans << ENDL;
return 0;
}
// ................. main .................. //
void execute() {
input(), solve();
}
int main(void) {
#ifdef LOCAL_BOOKNU
freopen("input.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
cin.tie(0), ios_base::sync_with_stdio(false);
execute();
return 0;
}
// ......................................... //