총평 : 셋이 구린 거라고 하고 싶지만.. 내가 너무 말렸다.
Virtual 참가 후기
5문제 / 691min. 실제 대회 12등 팀 기록과 동일하다.
처음에 문제를 쭉 보는데 쉬운 게 하나도 안 보이길래 A를 일단 잡았다가, 좀 아닌 거 같아서 스코어보드를 보니까 L이 쭉 풀리고 있었다. L 처음에 봤을 땐 어려운 줄 알고 넘겼었는데 다시 보니까 쉬웠다. 큰 수 출력이 필요해서 Python으로 짰다.
그 다음에는 A가 NTT로 풀리는 거 같아서 O(nlog^2n) 코드를 짜서 냈는데 (NTT는 물론 복붙) 시간초과가 나길래 일단 접었다.
다른 문제를 쭉 보는데, 쉬워 보이는 게 없어서 (사실 D가 좀 풀리고 있었는데 풀기 싫게 생겼음) 결국 C를 풀기로 했다. 다행히도 풀이는 금방 나왔는데, 구현을 처음에 이상하게 했는지 몇 번 틀렸다.
D는 입력 형식이 좀 구린 단순 구현 문제였다. description을 읽는데 "Genshin Impact"(원신)가 나오길래 뭔가 싶었다. 아무튼 금방 맞음.
이제 F를 봤는데, 대강의 풀이는 금방 나왔지만 예외 케이스 처리가 좀 많았다. 심지어 코딩 편하게 하려고 꼼수 쓰다가 나도 모르게 overflow가 나는 코드를 짜 버려서 시간 좀 버렸다.
여기까지 하고 잠시 나갔다 왔는데, 나머지 문제는 다 너무 어려웠다. J 풀이를 생각하긴 했는데 log^3 짜리라서 짜지는 못했고, I에다가 이상한 코드 좀 내다가 틀린 것을 깨달으면서 또 1시간을 버렸다.
G의 풀이에 필요한 핵심 관찰이 생각나서 G를 풀기로 했는데, 코딩하다가 또 엄청 말렸다. DP 값 갱신을 처음에 한 번 해줘야 되는데 그걸 빼먹어서 한 30분 버렸다. 예제는 다 맞는게 레전드;
나머지 시간에는 I에 이상한 거 한 번 더 내고, A 좀 더 해보다가 계속 TLE나서 그냥 던졌다.
J를 구현하든 I를 풀든 A를 풀든 했어야 좋을 것 같은데.. 많이 아쉽다.
* Official 풀이 슬라이드는 https://www.dropbox.com/s/e1wa94367v7z7wq/2020icpc-macau-analyze.pdf?dl=0 여기.
A
각 단계마다 있는 "+1"에 붙는 계수가 뭔지 생각해 보면, \( p(x) = \Pi (x+a_i) \) 에서 \( x^i \) 의 계수에 \( \frac{i!(n-i)!}{n!} \) 을 곱한 것임을 알 수 있다. p(x)는 수열을 반씩 나눠서 각각 재귀적으로 문제를 풀고, 나온 두 다항식을 FFT/NTT로 빠르게 곱하면 O(nlog^2n)에 구할 수 있다. 근데 내 NTT 코드는 TLE가 났다.
끝나고 풀이 슬라이드를 보니까 똑같은 말이 적혀있어서 화가 났다. TLE났던 코드를 언어 옵션을 64bit G++로 바꿔서 내니까 맞아서 더 화가 났다. (코포 기본 G++ 컴파일러는 32bit이다. 그래서 long long 쓰면 개느리다...)
코드 (NTT는 내가짠거 아님)
#include <iostream>
#include <limits>
#include <iomanip>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <numeric>
#include <utility>
#include <string>
#include <bitset>
#include <functional>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cassert>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vint = vector<int>;
using vll = vector<ll>;
using vld = vector<ld>;
using vpii = vector<pii>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vpll = vector<pll>;
#define x first
#define y second
#define all(v) (v).begin(),(v).end()
#define ints(args...) int args; readln(args);
#define lls(args...) ll args; readln(args);
#define strs(args...) string args; readln(args);
template<typename... Args>
void readln(Args&... args) { ((cin >> args), ...); }
template<typename... Args>
void writeln(Args... args) { ((cout << args << " "), ...); cout << '\n'; }
const ll M = 998244353;
ll _pow(ll a, ll b, ll mod) {
ll ret = 1;
while (b) {
if (b & 1) ret = ret * a % mod;
b >>= 1; a = a * a % mod;
}
return ret;
}
template<ll mod, ll w>
class NTT {
public:
void ntt(vector<ll>& f, bool inv = 0) {
int n = f.size(), j = 0;
vector<ll> root(n >> 1);
for (int i = 1; i < n; i++) {
int bit = (n >> 1);
while (j >= bit) {
j -= bit; bit >>= 1;
}
j += bit;
if (i < j) swap(f[i], f[j]);
}
ll ang = _pow(w, (mod - 1) / n, mod); if (inv) ang = _pow(ang, mod - 2, mod);
root[0] = 1; for (int i = 1; i < (n >> 1); i++) root[i] = root[i - 1] * ang % mod;
for (int i = 2; i <= n; i <<= 1) {
int step = n / i;
for (int j = 0; j < n; j += i) {
for (int k = 0; k < (i >> 1); k++) {
ll u = f[j | k], v = f[j | k | i >> 1] * root[step * k] % mod;
f[j | k] = u + v;
if(f[j | k] >= mod) f[j | k] -= mod;
f[j | k | i >> 1] = u - v;
if (f[j | k | i >> 1] < 0) f[j | k | i >> 1] += mod;
}
}
}
ll t = _pow(n, mod - 2, mod);
if (inv) for (int i = 0; i < n; i++) f[i] = f[i] * t % mod;
}
vector<ll> multiply(vector<ll>& _a, vector<ll>& _b) {
vector<ll> a(_a.begin(), _a.end()), b(_b.begin(), _b.end());
int n = 2;
while (n < a.size() + b.size()) n <<= 1;
a.resize(n); b.resize(n);
ntt(a); ntt(b);
for (int i = 0; i < n; i++) a[i] = a[i] * b[i] % mod;
ntt(a, 1);
return a;
}
};
NTT<M, 3> ntt;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
ints(t);
while(t--) {
lls(n);
vll a(n);
for(int i = 0; i < n; i++) cin >> a[i];
const function<vll(int, int)> f = [&](int l, int r) {
if(l == r) return vll{a[l], 1LL};
int m = (l + r) >> 1;
vll lf = f(l, m);
vll rf = f(m + 1, r);
return ntt.multiply(lf, rf);
};
vll p = f(0, n - 1);
vll fa(n + 1);
fa[0] = 1;
ll ans = 0;
for(int i = 1; i <= n; i++) fa[i] = fa[i - 1] * i % M;
for(int i = 0; i < n; i++) (ans += fa[i] * fa[n - i] % M * p[i]) %= M;
cout << (ans * _pow(fa[n], M - 2, M) % M) << '\n';
}
return 0;
}
B
문제 이해도 제대로 못 했다. solve 수 보니까 어려운 문제인 듯.
C
w[i] ^ w[j] < 2^k 라는 조건은 "w[i]와 w[j]가 맨 아래 k비트를 제외하고 모두 동일하다", 즉 "(w[i] >> k) == (w[j] >> k)"와 동치이다.
(w[i] >> k)가 같은 수끼리 묶었을 때, 각 묶음에 많아야 2개의 수가 들어있는 최대의 k를 잡자. 그러면 답은 2^k 이상이고 2^(k+1) 미만임을 일단 알 수 있다. 같은 묶음에 있는 수를 다른 집합에 넣어 주면 답이 2^k 이상이 되도록 할 수 있고, (w[i] >> (k+1))이 같은 수끼리 묶으면 3개 이상이 들어 있는 묶음이 생겨서 답이 2^(k+1) 이상은 못 되기 때문이다.
이제 답을 정확히 찾아야 하는데, 이것은 아까 잡은 k를 가지고 (w[i] >> (k+1)) 값을 기준으로 수들을 묶어 놓고 보면 구할 수 있다. (w[i] >> (k+1)) 값이 다른 수들은 같은 집합에 있어도 답에 아무 영향이 없으므로, 각 묶음 내에서만 같은 집합의 원소의 XOR값이 최대가 되도록 해 주면 된다. 한 묶음에 많아야 4개의 수가 있으므로, 모든 가능한 경우를 다 해 보아도 충분하다.
여담으로, 풀이 슬라이드에는 XOR MST(이 문제 참고)를 구하고 그 트리에서 인접한 정점을 다른 집합에 넣어주면 그게 답이 된다고 써 있다. 구현은 내 풀이가 더 쉬운 듯 하다.
코드
#include <iostream>
#include <limits>
#include <iomanip>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <numeric>
#include <utility>
#include <string>
#include <bitset>
#include <functional>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cassert>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vint = vector<int>;
using vll = vector<ll>;
using vld = vector<ld>;
using vpii = vector<pii>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vpll = vector<pll>;
#define x first
#define y second
#define all(v) (v).begin(),(v).end()
#define ints(args...) int args; readln(args);
#define lls(args...) ll args; readln(args);
#define strs(args...) string args; readln(args);
template<typename... Args>
void readln(Args&... args) { ((cin >> args), ...); }
template<typename... Args>
void writeln(Args... args) { ((cout << args << " "), ...); cout << '\n'; }
int main() {
ios::sync_with_stdio(0); cin.tie(0);
ints(t);
while(t--) {
ints(n);
vll a(n);
for(int i = 0; i < n; i++) cin >> a[i];
auto aa = a;
sort(all(aa));
int fck = 0;
for(int i = 0, j; i < n; i = j) {
for(j = i + 1; j < n && aa[i] == aa[j]; j++);
if(j - i >= 3) { fck = 1; break; }
}
if(fck) { cout << "0\n"; cout << string(n, '1') << '\n'; continue; }
int L = 0, R = 32;
const auto f = [&](int k) {
map<ll, int> r;
for(ll x : a) r[x >> k]++;
return r;
};
while(L < R) {
int M = (L + R) >> 1;
auto t = f(M + 1);
int mx = 0;
for(auto &i : t) mx = max(mx, i.y);
if(mx <= 2) L = M + 1;
else R = M;
}
L++;
map<ll, vint> mm;
for(int i = 0; i < n; i++) mm[a[i] >> L].push_back(i);
ll ans = ll(1e18);
string as(n, '1');
for(auto &i : mm) {
int k = i.y.size();
ll cur = 0;
for(int j = 0; j < (1 << k); j++) {
ll ccur = ll(1e18);
for(int x = 0; x < k; x++) for(int y = x + 1; y < k; y++) {
if(((j >> x) & 1) == ((j >> y) & 1)) ccur = min(ccur, a[i.y[x]] ^ a[i.y[y]]);
}
if(ccur > cur) {
cur = ccur;
for(int x = 0; x < k; x++) as[i.y[x]] = '1' + ((j >> x) & 1);
}
}
ans = min(ans, cur);
}
cout << ans << '\n' << as << '\n';
}
return 0;
}
D
문제를 잘 읽고, 하라는 대로 구현하면 된다. Python을 쓰면 편하다.
코드
atk = 0
atkr = 0
cridmg = 0.5
crirat = 0.05
for i in range(25):
s = input().split('+')
if s[1][-1] == '%':
s[1] = s[1][:-1]
if s[0] == 'ATK':
atk += float(s[1])
elif s[0] == 'ATK Rate':
atkr += float(s[1]) / 100
elif s[0] == 'Crit Rate':
crirat += float(s[1]) / 100
elif s[0] == 'Crit DMG Rate':
cridmg += float(s[1]) / 100
atk = 1500 * (1 + atkr) + atk
crirat = min(1, crirat)
print('{:.9f}'.format(atk * (1 - crirat) + atk * (1 + cridmg) * crirat))
E
구현이 딱 봐도 더럽게 생겨서 안 봤다.
대회 중에 문제를 잘못 읽었었다는 사실을 대회가 끝나고 깨달았다. 나는 각 x좌표마다 사진 찍는 높이를 선택 가능한 줄 알았는데, 그게 아니고 그냥 x좌표를 정하면 그 때 사진을 찍는 y좌표가 정해져 있는 거였다. 그래서 풀이는 그냥 사진의 W 값이 작음을 이용해서 Bitmask DP를 하는 것이다.......... 뭐 이런 문제를 내나 싶다.
F
N개의 정점을 C개의 컴포넌트로 나눠야 하는데, 각 정점은 정확히 D개의 간선이 연결되어 있어야 한다. Self-Loop나 Multi-Edge는 허용되지 않는다. 우선 N * D가 홀수이면 불가능하다는 것을 알 수 있다.
이제 N * D가 짝수일 때 어떻게 하는지가 문제인데, 일단 각 컴포넌트에 정점을 몇 개씩 배정할지부터 생각해 보자. D는 모든 컴포넌트에 대해 똑같으므로, 한 쪽에 정점을 너무 많이 몰아주면 정점이 가장 적은 컴포넌트에서 D개의 간선을 쓰기가 힘들어지니까 (조건 때문에, 컴포넌트에 M개의 정점이 있으면 D < M을 만족해야 함) 최대한 균일하게 배분하는 것이 좋을 것 같다. 그렇게 배분했는데 D >= M인 컴포넌트가 생기면 역시 불가능.
최대한 균일하게 배분할 때 주의할 점은 D가 홀수이면 각 컴포넌트의 크기 역시 모두 짝수여야 한다는 것이다. D의 홀짝성에 따라 N을 최대한 균일하게 배분하거나 (N/2)를 균일하게 배분하고 나중에 2를 곱할지를 선택하면 된다.
이제 컴포넌트별로 M개의 정점이 있다고 할 때 모든 정점이 D개의 간선에 연결되어 있도록 하는 방법을 생각해 보자. 우선, D가 짝수일 경우에는 (D/2)개의 사이클을 만들어 주면 충분하다. 1 - 2 - ... - M - 1, 1 - 3 - 5 - ... - (M-1) - 1, ... 이런 식으로 사이클을 만들어 주면 (D < M일 경우) 각 사이클의 간선이 겹치지 않으므로 항상 구축이 가능하다.
D가 홀수일 경우에는 M이 무조건 짝수이다. 따라서 번호가 M/2만큼 차이나는 정점 쌍에 간선을 M/2개 추가해 주면 (1 - (M/2 + 1), 2 - (M/2 + 2), ..., M/2 - M) D-1은 짝수이므로 아까 썼던 방법을 쓸 수 있다.
D가 0일 수도 있고 1일 수도 있어서 각각에 대해 예외 처리를 다 해줘야 한다. 정말 화나는 문제다.
코드
#include <iostream>
#include <limits>
#include <iomanip>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <numeric>
#include <utility>
#include <string>
#include <bitset>
#include <functional>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cassert>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vint = vector<int>;
using vll = vector<ll>;
using vld = vector<ld>;
using vpii = vector<pii>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vpll = vector<pll>;
#define x first
#define y second
#define all(v) (v).begin(),(v).end()
#define ints(args...) int args; readln(args);
#define lls(args...) ll args; readln(args);
#define strs(args...) string args; readln(args);
template<typename... Args>
void readln(Args&... args) { ((cin >> args), ...); }
template<typename... Args>
void writeln(Args... args) { ((cout << args << " "), ...); cout << '\n'; }
int main() {
ios::sync_with_stdio(0); cin.tie(0);
ints(n, d, c);
if(n * d % 2 == 1) { cout << "No\n"; return 0; }
if(d == 0) {
if(n != c) cout << "No\n";
else {
cout << "Yes\n";
for(int i = 0; i < n; i++) cout << '\n';
}
return 0;
}
if(d == 1) { if(c != n / 2) { cout << "No\n"; return 0; } }
vector<vint> e(n + 1);
auto add = [&](int l, int r, int d, int div) {
int sz = r - l + 1;
for(int i = 0; i < sz / div; i++) {
int x = i + l, y = (i + d) % sz + l;
e[x].push_back(y);
e[y].push_back(x);
}
};
for(int i = 0; i < c; i++) {
int l, r;
if(d % 2 == 0) { l = 1LL * n * i / c + 1; r = 1LL * n * (i + 1) / c; }
else { l = ll(n / 2) * i / c * 2 + 1; r = ll(n / 2) * (i + 1) / c * 2; }
int sz = r - l + 1;
if(d >= sz || sz * d % 2 == 1) { cout << "No\n"; return 0; }
for(int sp = 1; sp <= d / 2; sp++) add(l, r, sp, 1);
if(sz % 2 == 0 && d % 2 == 1) add(l, r, sz / 2, 2);
}
cout << "Yes\n";
for(int i = 1; i <= n; i++) {
sort(all(e[i]));
for(int j = 0; j < d; j++) cout << e[i][j] << " \n"[j == d - 1];
}
return 0;
}
G
일단 각 쿼리에 대해 답을 어떻게 구하는지 생각해 보자. D[k]를 "k번 위치에서 선공이 시작했을 때 이기면 1, 지면 0" 이라고 정의하면 D[k]의 값은 "k에서 갈 수 있는 j들 중 D[j] = 0인 것이 하나라도 있으면 1, 아니면 0"이다.
여기서 핵심적인 관찰을 하나 할 수 있는데, i<j이고 A[i] = A[j]인 (i,j) 쌍이 있으면 D[i]의 값이 무조건 1이라는 것이다.
(pf) D[j]가 0이면, i -> j로 갈 수 있으므로 D[i] = 1. D[j]가 1이면, j에서 D[k]=0인 k로 갈 수 있다는 뜻인데 그런 k는 i에서도 갈 수 있으므로 역시 D[i] = 1.
이제 DP 값을 실제로 구해야 하는 위치는 0 <= x < 256 인 x에 대해 "A[j] = x인 가장 오른쪽 j"로 줄어든다. 맨 처음에 한 번 DP를 계산해 주고, 이후에 수열 뒤에 원소가 추가될때마다 DP 값을 새로 구해 주면 된다. 한 번 계산할 때 대충 256*8 정도 시간에 구하면 제한 시간 안에 충분히 나온다. 자세한 구현 디테일은 코드를 참고.
참고로 각 배열의 의미는 아래와 같다.
lst[x] : A[j] = x인 가장 오른쪽 j
ord[y] : lst[x] 값이 y번째(0부터 시작)로 큰 x
idx[x] : ord[y] = x인 y (ord[x]와 inverse 관계)
#include <iostream>
#include <limits>
#include <iomanip>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <numeric>
#include <utility>
#include <string>
#include <bitset>
#include <functional>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cassert>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vint = vector<int>;
using vll = vector<ll>;
using vld = vector<ld>;
using vpii = vector<pii>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vpll = vector<pll>;
#define x first
#define y second
#define all(v) (v).begin(),(v).end()
#define ints(args...) int args; readln(args);
#define lls(args...) ll args; readln(args);
#define strs(args...) string args; readln(args);
template<typename... Args>
void readln(Args&... args) { ((cin >> args), ...); }
template<typename... Args>
void writeln(Args... args) { ((cout << args << " "), ...); cout << '\n'; }
int lst[256], ord[256], idx[256], dp[256];
int main() {
ios::sync_with_stdio(0); cin.tie(0);
ints(n, q);
fill(lst, lst + 256, -1);
vint a(n + 1);
for(int i = 1; i <= n; i++) {
cin >> a[i];
lst[a[i]] = i;
}
iota(ord, ord + 256, 0);
sort(ord, ord + 256, [&](int x, int y) { return lst[x] > lst[y]; });
for(int i = 0; i < 256; i++) idx[ord[i]] = i;
for(int i = 0; i < 256; i++) {
dp[ord[i]] = 0;
for(int j = 1; j < 256; j <<= 1) {
if(idx[ord[i] ^ j] < i && !dp[ord[i] ^ j]) { dp[ord[i]] = 1; break; }
}
}
while(q--) {
ints(x, y);
if(x == 1) {
lst[y] = a.size();
a.push_back(y);
for(int i = 0; i < 256; i++) if(idx[i] < idx[y]) idx[i]++;
idx[y] = 0;
for(int i = 0; i < 256; i++) ord[idx[i]] = i;
for(int i = 0; i < 256; i++) {
dp[ord[i]] = 0;
for(int j = 1; j < 256; j <<= 1) {
if(idx[ord[i] ^ j] < i && !dp[ord[i] ^ j]) { dp[ord[i]] = 1; break; }
}
}
}
else {
if(y == lst[a[y]]) cout << (dp[a[y]] ? "Grammy\n" : "Alice\n");
else cout << "Grammy\n";
}
}
return 0;
}
H
풀라고 낸 건지 잘 모르겠다.
풀이 슬라이드에는 다변수 생성함수 G(x,y)가 나온다. 어쩌라고!!
I
삭제 쿼리가 없다면 길이 16384짜리인 D[x] : "XOR한 값이 x가 되도록 pile들을 고르는 방법 중 최소 비용" 배열을 매 쿼리마다 갱신해줌으로써 (새로운 배열을 E라 하면 E[x] = min(D[x], D[x^a] + b)) 시간 제한 내에 풀 수 있는데, 삭제 쿼리 때문에 D[x] 배열의 history를 다 저장하려고 보면 메모리 제한에 걸린다.
append/pop 으로 이루어진 쿼리의 진행 과정은 트리로 모델링할 수 있다. 나는 여기까지만 생각하고 더 나아가지 못했는데, 이렇게 만든 트리에서 HLD를 수행하고 Light Edges -> Heavy Edge 순으로 DFS를 진행하면 light edge를 타고 내려갈 때만 history를 저장하면 돼서 (어떤 노드에서 heavy edge를 타고 내려갔다면, 그 노드에 대한 history는 더 이상 필요가 없다) 메모리를 절약할 수 있다고 한다.
앞에서 안 말렸으면 풀었을까.. 하는 생각이 든다. 이건 좀 아쉬운듯.
J
대회 중에는 O(log^3n) 짜리 이상한 풀이밖에 생각이 안 났는데, 풀이 슬라이드를 보니까 상당히 깔끔한 O(qklogn) 풀이가 적혀 있었다. 또 한 번 슬퍼지는 순간..
각 위치 i에 대해 "내 왼쪽에서 나랑 보석 색깔이 같은 최대 인덱스"를 pre[i]라고 정의하면, "한 번 나왔던 색깔의 보석"이 나올 때까지 쭉 가는 과정을 k번 하면서 답을 계산하면 된다. 중복된 색깔의 보석이 나올 때마다 이번에 본 보석이 더 비싸다면 가져가고(예전 거는 버린 걸로 취급) 아니면 그냥 지나가는 전략을 취하면 된다.
이는 시작 위치가 s라고 할 때 "pre[i] >= s인 최소 i"를 어떤 구간에서 찾는 쿼리를 여러 번 하면 되기 때문에 세그먼트 트리로 어렵지 않게 짤 수 있다. 답 계산 역시 구간 합을 빠르게 구하면 돼서 어렵지 않다.
어떤 위치의 보석이 바뀌면 pre[i] 값은 많아야 세 곳에서 바뀌기 때문에 갱신 역시 빠르게 된다.
K
"2-sat이 안 되겠지?"라고 생각하고 넘어갔는데, "2-sat을 bitset으로 최적화하면 됨"이 풀이였다. 이 뭔..
L
얼핏 보면 어려워 보이는 문제인데, 조금만 생각해 보면 쉽다.
임의의 순열 p에 대해, a가 조건을 만족하도록 뽑힐 확률은 p[i] = 1인 위치부터 p[i] = n인 위치까지 하나씩 생각해 보면 \( \frac{1}{n} \times \frac{2}{n} \times \cdots \times \frac{n}{n} = \frac{n!}{n^n} \) 으로 고정된 값이므로, 답은 그냥 \( \frac{(n!)^2}{n^n} \) 이 된다. 출력할 값이 좀 크므로 Python을 쓰자.
코드
n = int(input())
ans = 1
for i in range(1, n + 1):
ans *= i;
for i in range(1, n + 1):
ans *= i / n
print('{:.9f}'.format(ans))'알고리즘 > 온라인 대회' 카테고리의 다른 글
| 제 3회 소프트콘 후기 (0) | 2021.08.29 |
|---|---|
| Codeforces Round #737 (0) | 2021.08.23 |
| Codeforces Round #736 (0) | 2021.08.20 |
| Codeforces Good Bye 2020 후기 (0) | 2021.01.07 |
| Codeforces Round #691, #692 후기 (0) | 2020.12.21 |