AtCoder Regular Contest 147 ★

오랜만에 ARC를 쳤는데, 개인 최고 퍼포먼스를 내서 기쁜 마음에 풀이를 작성한다.

유의: 궁금하신 점은 댓글로 남겨주세요!

 

C 솔브 직후

1. Max Mod Min

요약: multiset에서 최소원으로 최대원에 modular를 취해주는 과정을 반복한다. 만약 0이 되면 multiset에서 빠지면 된다. 이 때 연산의 횟수를 구하면 된다.

풀이: modular 취하고 나면 최대원의 값이 최소원보다도 작아지므로 새로운 최소원이 된다. 이는 덱을 이용하면 구현할 수 있다. 시간 복잡도는 modular을 취할 때 항상 크기가 절반 미만으로 감소한다는 사실을 고려하면 $O(N\log \max A)$가 된다는 것을 알 수 있다.

한국 참가자들 중에 가장 늦게 제출해서 망했다고 생각했다. 10분 정도 걸렸나?

항상 보면 나는 첫 문제 제출이 매우 늦다.

      

      

      

    
    

      <cpp />
    
#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;
}

2. Swap to Sort

요약: 인접 원소 swap으로 정렬하는 방법을 확장한 문제이다. 한 칸 뛰고 인접한 원소끼리 swap하는 연산과 기존 인접 원소 swap 연산이 있는데, 후자를 최소화시키고, 모든 연산의 횟수가 $10^5$ 이내가 되어야 한다.

풀이: 한 칸 뛰고 인접한 원소끼리 swap은 인덱스의 기우성과 값의 기우성이 모두 불변이다. 이 둘이 일치하게 한 뒤 기존 정렬을 수행하면 된다는 사실을 바탕으로 인덱스와 값의 기우성을 일치시키는 작업을 대충 $N$번의 연산에 마쳐야 한다. 이는 기우성이 일치하지 않는 원소들을 뒤로 싹 밀어준 뒤 인접 원소 swap을 하나씩 해주면 된다. 대충 총 $2N$번의 연산 정도 선에서 끝난다. 남은 것은 기존 정렬, $N^2/2$ 정도의 연산이다. 여유롭게 통과한다.

      

      

      

    
    

      <cpp />
    
#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';
    }
}

3. 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$가 된다. 따라서 바깥쪽부터 최대한 좁히게 설정하면서 구성해주면 된다.

      

      

      

    
    

      <cpp />
    
#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;
}

4. Sets Scores

찍맞이 가능할 것 같은 문제..

5~10분만 더 있었어도 어케든 풀었을 것 같음..

4.1. 문제

길이가 $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$으로 나눈 나머지를 구하라.

4.2. 풀이

4.2.1. 공통 원소 표현 바꾸기

$S_i$와 $S_{i+1}$중 정확히 하나에만 존재하는 원소가 유일하다는 표현은 문제를 풀 때 직접적으로 사용하기에는 용이하지 않다.

따라서 '$X_i:=S_i$와 $S_{i+1}$중 정확히 하나에만 존재하는 원소'라고 하자. 어느 쪽에 존재하는지 정확하게 알지 않아도 존재 유무의 전환이 되는 지점이라는 점에서 유의미한 정보이다.

4.2.2. 고정된 케이스를 풀기

$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$이기 때문이다.

4.2.3. 전체 합 구하기

$X$를 결정하는 가짓수는 단순히 $M^{N-1}$이다. 따라서 전체 점수의 합은 $M^{N-1}\times N^M$이다.

4.3. 코드

ㅋㅋㅋㅋ 이게 어딜 봐서 ARC D?

      

      

      

    
    

      <cpp />
    
#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));
}