오랜만에 ARC를 쳤는데, 개인 최고 퍼포먼스를 내서 기쁜 마음에 풀이를 작성한다.
유의: 궁금하신 점은 댓글로 남겨주세요!
Max Mod Min
요약: multiset에서 최소원으로 최대원에 modular를 취해주는 과정을 반복한다. 만약 0이 되면 multiset에서 빠지면 된다. 이 때 연산의 횟수를 구하면 된다.
풀이: modular 취하고 나면 최대원의 값이 최소원보다도 작아지므로 새로운 최소원이 된다. 이는 덱을 이용하면 구현할 수 있다. 시간 복잡도는 modular을 취할 때 항상 크기가 절반 미만으로 감소한다는 사실을 고려하면 $O(N\log \max A)$가 된다는 것을 알 수 있다.
한국 참가자들 중에 가장 늦게 제출해서 망했다고 생각했다. 10분 정도 걸렸나?
항상 보면 나는 첫 문제 제출이 매우 늦다.
#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
const int N = 2e5+3;
int n, a[N];
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
rep(i,1,n) cin >> a[i];
priority_queue<int> pq;
sort(a+1,a+n+1);
int x = a[1];
rep(i,2,n) pq.push(a[i]);
int cnt = 0;
while (not empty(pq)) {
int y = pq.top(); pq.pop();
cnt++;
y %= x;
if (y != 0) {
pq.push(x);
x = y;
}
}
cout << cnt;
}Swap to Sort
요약: 인접 원소 swap으로 정렬하는 방법을 확장한 문제이다. 한 칸 뛰고 인접한 원소끼리 swap하는 연산과 기존 인접 원소 swap 연산이 있는데, 후자를 최소화시키고, 모든 연산의 횟수가 $10^5$ 이내가 되어야 한다.
풀이: 한 칸 뛰고 인접한 원소끼리 swap은 인덱스의 기우성과 값의 기우성이 모두 불변이다. 이 둘이 일치하게 한 뒤 기존 정렬을 수행하면 된다는 사실을 바탕으로 인덱스와 값의 기우성을 일치시키는 작업을 대충 $N$번의 연산에 마쳐야 한다. 이는 기우성이 일치하지 않는 원소들을 뒤로 싹 밀어준 뒤 인접 원소 swap을 하나씩 해주면 된다. 대충 총 $2N$번의 연산 정도 선에서 끝난다. 남은 것은 기존 정렬, $N^2/2$ 정도의 연산이다. 여유롭게 통과한다.
#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
const int N = 403;
int n, p[N];
vector<string> st;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
rep(i,1,n) cin >> p[i];
rep(_,0,n) for (int i = 1; i <= n-2-_; i += 2) {
if (p[i]%2 == 0) {
st.push_back("B "+to_string(i));
swap(p[i],p[i+2]);
}
}
rep(_,0,n) for (int i = 2; i <= n-2-_; i += 2) {
if (p[i]%2 == 1) {
st.push_back("B "+to_string(i));
swap(p[i],p[i+2]);
}
}
for (int i = n-1; i >= 1; i -= 2) {
if (i%2 != p[i]%2) {
st.push_back("A "+to_string(i));
swap(p[i],p[i+1]);
}
}
rep(i,0,n) {
rep(j,1,n-2-i) {
if (p[j] > p[j+2]) {
st.push_back("B "+to_string(j));
swap(p[j],p[j+2]);
}
}
}
// rep(i,1,n) cerr << p[i] << ' ';
cout << siz(st) << '\n';
for (auto &s : st) {
cout << s << '\n';
}
}Min Diff Sum
사실상 D번보다 C번(이 문제)가 더 까다롭다.
요약: 직선 위의 점들에서 모든 쌍간의 거리의 합을 최소화시키면 된다. 그런데 점들은 존재할 수 있는 고유의 연속된 구간이 주어진다. 이걸 잘 조정해서 최소화시키면 된다.
풀이: $x_1\le x_2\le \cdots \le x_{N-1}\le x_N$라면 모든 쌍간의 거리의 합은 $(N-1)(x_N-x_1)+(N-3)(x_{N-1}-x_2)+(N-5)(x_{N-2}-x_3)\cdots$가 된다. 따라서 바깥쪽부터 최대한 좁히게 설정하면서 구성해주면 된다.
#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
const int N = 3e5+3;
int n, l[N], r[N];
vector<int> byL, byR;
bool used[N];
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
rep(i,1,n) cin >> l[i] >> r[i];
byL.resize(n), byR.resize(n);
iota(all(byL),1), iota(all(byR),1);
sort(all(byL),[&](int x, int y) {
// if (l[x] == l[y]) return r[x] < r[y];
return l[x] > l[y];
});
sort(all(byR),[&](int x, int y) {
// if (r[x] == r[y]) return l[x] > l[y];
return r[x] < r[y];
});
auto li = begin(byL), ri = begin(byR);
ll ans = 0;
for (ll c = n-1; c >= 0; c -= 2) {
bool x = false, y = false;
for (;li != end(byL); ++li) {
if (not used[*li]) {
used[*li] = x = true;
break;
}
}
for (;ri != end(byR); ++ri) {
if (not used[*ri]) {
used[*ri] = y = true;
break;
}
}
if (x and y) {
// cerr << l[*li] << ' ' << r[*ri] << '\n';
ans += c*max(l[*li] - r[*ri],0);
}
}
cout << ans;
}Sets Scores
찍맞이 가능할 것 같은 문제..
5~10분만 더 있었어도 어케든 풀었을 것 같음..
문제
길이가 $N$인 정수 집합들의 열 $S=(S_1,S_2,\ldots,S_N)$을 고려하자. 우리는 이 열이 다음의 조건들을 만족할 때 '훌륭하다'고 한다:
- $S_i\subset [1,M]$ ($1\le i \le N$)
- $S_i$와 $S_{i+1}$ 중에서 정확히 하나에만 속하는 정수는 유일하다. ($1\le i\le N-1$)
우리는 훌륭한 열 $S$의 점수를 $\displaystyle \prod ^M _{i=1}(S_1,S_2,\ldots,S_N$ 중 $i$를 포함하는 집합의 수$)$라고 정의한다.
가능한 모든 훌륭한 열들의 점수의 합을 $998244353$으로 나눈 나머지를 구하라.
풀이
공통 원소 표현 바꾸기
$S_i$와 $S_{i+1}$중 정확히 하나에만 존재하는 원소가 유일하다는 표현은 문제를 풀 때 직접적으로 사용하기에는 용이하지 않다.
따라서 '$X_i:=S_i$와 $S_{i+1}$중 정확히 하나에만 존재하는 원소'라고 하자. 어느 쪽에 존재하는지 정확하게 알지 않아도 존재 유무의 전환이 되는 지점이라는 점에서 유의미한 정보이다.
고정된 케이스를 풀기
$X$가 고정된 상태의 점수 합은 구하기 쉬워진다. '존재 유무의 전환이 되는 지점'이기 때문에 $S_1$에서 존재 여부만 파악하면 모든 $S_i$에 대해 존재 유무를 자동 결정할 수 있다.
$S_1$를 고정하면 $S_2,\cdots,S_N$도 자동 결정된다.
'$A_x:=x\in S_1$일 때 $x$를 포함하는 집합의 개수', '$B_x:=x\not \in S_1$일 때 $x$를 포함하는 집합의 개수'라고 하자.
그러면 모든 가능한 $S_1$에 대해서 점수의 합은 $(A_1+B_1)\times \cdots \times (A_M+B_M)$이 된다. 이는 $N^M$인데, 왜냐하면 $A_i+B_i=N$이기 때문이다.
전체 합 구하기
$X$를 결정하는 가짓수는 단순히 $M^{N-1}$이다. 따라서 전체 점수의 합은 $M^{N-1}\times N^M$이다.
코드
ㅋㅋㅋㅋ 이게 어딜 봐서 ARC D?
#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
const int MOD = 998244353;
ll mul(ll x, ll y) { return (x=(x*y)%MOD) >= 0 ? x : x+MOD; }
ll pw(ll x, ll e) {
ll r = 1;
while (e > 0) {
if (e%2) r = mul(r,x);
e /= 2, x = mul(x,x);
}
return r;
}
int main() {
int n, m;
cin >> n >> m;
cout << mul(pw(n,m),pw(m,n-1));
}'PS 기록들' 카테고리의 다른 글
| 2022 서울대학교 프로그래밍 경시대회 Open Contest - Division 2 ★ (2) | 2022.09.17 |
|---|---|
| 2022.09.12 PS 일지 (0) | 2022.09.12 |
| NYPC 2022 Round 2-B 후기 (0) | 2022.09.04 |
| 2022.08.31 PS 일지 (0) | 2022.09.01 |
| 학교 전용 Online Judge 운영 ★ (0) | 2022.08.28 |
