TL 見て面白そうだったから解いてみた!
問題概要
サイズ N の順列が与えられる。これは以下のいずれかによってつくられたものである。
- Petr: (1, 2, ..., N) から出発して、ランダムに 2 要素を選んで swap する操作を 3N 回繰り返す
- Um_nik: (1, 2, ..., N) から出発して、ランダムに 2 要素を選んで swap する操作を 7N + 1 回繰り返す
どちらの方法でつくられたものかを判定せよ。
制約
- 103 <= N <= 106
解法
(7N + 1) - 3N = 4N + 1 より偶奇が異なる。それゆえ、Petr 方式と Um_nik 方式とでは、最終的に得られる順列の転倒数の偶奇が異なることになる。
BIT を用いて転倒数を求める
#include <iostream> #include <vector> using namespace std; template <class Abel> struct BIT { vector<Abel> dat; Abel UNITY_SUM = 0; // to be set /* [1, n] */ BIT(int n) { init(n); } void init(int n) { dat.resize(n + 1); for (int i = 0; i < (int)dat.size(); ++i) dat[i] = UNITY_SUM; } /* a is 1-indexed */ inline void add(int a, Abel x) { for (int i = a; i < (int)dat.size(); i += i & -i) dat[i] = dat[i] + x; } /* [1, a], a is 1-indexed */ inline Abel sum(int a) { Abel res = UNITY_SUM; for (int i = a; i > 0; i -= i & -i) res = res + dat[i]; return res; } /* [a, b), a and b are 1-indexed */ inline Abel sum(int a, int b) { return sum(b - 1) - sum(a - 1); } void print() { for (int i = 1; i < (int)dat.size(); ++i) cout << sum(i, i + 1) << ","; cout << endl; } }; int main() { int n; cin >> n; vector<int> P(n); for (int i = 0; i < n; ++i) cin >> P[i]; BIT<int> bit(n+1); long long tentou = 0; for (int i = 0; i < n; ++i) { long long tmp = bit.sum(P[i]+1, n+1); tentou += tmp; bit.add(P[i], 1); } if (n & 1) { if (tentou & 1) cout << "Petr" << endl; else cout << "Um_nik" << endl; } else { if (tentou & 1) cout << "Um_nik" << endl; else cout << "Petr" << endl; } }