ARC 124 후기

작성일 | In |

결과 및 총평

내 제출현황과 순위는 위와 같다.

참가하기 전에 컨디션이 별로 였는데 이 정도면 훌륭하게 마친 것 같아 개인적으론 만족스럽다. A~D를 모두 거의 막힘 없이 적당히 밀었다. D에서 WA가 난 건 조금만 고민하면 한번에 AC가 가능했을 것 같아서 아까웠다.

문제는 여기에서 확인이 가능하다.

A~D에 대한 간단한 풀이, 리뷰, 코드이다.

A. LR Constraints

처음 읽었을 땐 살짝 당황했던 문제.

먼저 $N < K$일 경우 $0$이 됨은 쉽게 알아낼 수 있다.

그러므로 $N \leq K$인 경우만 생각한다.

우선 조건에 의해서 모든 $k_i$가 다르다. 그러므로 특정 위치에 대해선 써야 하는 수가 정해진다. 그리고 leftmost혹은 rightmost이어야 하므로, 어떤 수 $i$를 쓸 수 있는 범위가 정해진다. 따라서 해당 범위에 쓸 수 있는 수를 +1 해주고, 모든 위치에 써야하는 수가 정해지지 않았다면 쓸 수 있는 수의 개수를 곱해주면 된다.

별로 어렵지 않은 문제였는데도 시간을 약간 쓴 것 같다…

코드는 다음과 같다. 내 코드의 시간 복잡도는 $O(kn)$이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>
#define f first
#define s second
#define MOD 1000000007
#define PMOD 998244353
#define pb(x) push_back(x)
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> plii;
typedef pair<int, pii> piii;
const int INF = 1e9+10;
const ll LINF = 1LL*INF*INF;
const int MAXN = 2e5+10;
const int MAXM = 5e3+10;

priority_queue<int> pq;
vector<vector<int> > graph;
queue<int> que;

int A[MAXN];
char S[MAXN];

int cal[MAXN];

bool chk[MAXN];

int main()
{
    int n,m,k,a,b,x,y,q;
    int sum = 0;
    int cnt = 0;
    int mx = 0;
    int mn = INF;
    int cur = 0, idx = -1;
    int tc;
    char c;

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n>>k;

    for(int i=1;i<=k;i++){
        cin>>c>>x;
        if(c=='L')A[i] = (x<<1);
        else A[i] = (x<<1)|1;
    }

    if(n<k){
        cout<<0<<"\n";
        return 0;
    }

    for(int i=1;i<=k;i++){

        cur = (A[i]>>1);

        chk[cur] = true;

        if(A[i]&1){
            for(int j=1;j<cur;j++){
                cal[j]++;
            }
        }
        else {
            for(int j=cur+1;j<=n;j++){
                cal[j]++;
            }
        }

    }

    ll res = 1;

    for(int i=1;i<=n;i++){
        if(chk[i])continue;

        res = (res*(ll)cal[i])%PMOD;

    }

    cout<<res<<"\n";


    return 0;
}

B. XOR Matching 2

내가 좋아하는 XOR 문제가 나왔다.

문제 조건은 가능하다. $a_{i}, b_{i}$들을 적당히 재배열해서, 모든 $i$에 대해서 $a_{i} \oplus b_{i}$가 같은 값이 되게 할 수 있을 때, 그 값의 개수가 몇개인지, 그리고 어떤 수들이 가능한지 구하는 문제이다.

XOR의 성질 을 이용하면, 어떤 수 $a,x$에 대해서, $a \oplus b = x$가 되는 $b$는 유일하다. 이 성질을 이용하면, 주어진 조건을 만족하는 $x$를 고정했을 때, $a_{i}$에 대해서, $b_{i}$가 유일하게 정해진다는 것이다.

그러므로, 좌표압축을 통해서 $a_{i},b_{i}$ 각각에 서로 다른 수가 몇개 있고, 각각이 서로 다른 수들에 대해 수열 내에 개수가 몇개가 되는지 저장한 배열을 전처리로 저장해둔다. $a_{i}$를 좌표압축한 결과를 $c_{j}$라하고, 비슷하게 $d_{t}$를 $b_{i}$를 압축한 결과라하면, 가능한 $x$값의 후보들은 $c_{j} \oplus d_{t}$이다. 그리고 후보들에 대해서 실제로 가능한지 알아보려면, 우선 어떤 $c_{j}$에 대해 $c_{j} \oplus x = d_{t}$인 $d_{t}$가 존재해야 한다. 그리고 $a_{i},b_{i}$내에 $c_{j},d_{t}$의 개수가 같아야만 한다. 그렇지 않다면 한쪽이 남게 되고, 그 수는 다른 수와 매칭되어 XOR한 값이 $x$가 아니게 된다. 이 조건이 모든 $c_{j}$에 대해서 성립하면, 그 $x$는 문제에서 원하는 $x$가 된다.

위의 유일성 성질 때문에, 각 $c_{j}$에 대해 특정 수 $x$에 대해 조건을 만족하는 $d_{t}$는 모두 달라지므로, 겹칠 염려는 없다.

위의 내용을 코드로 적당히 빠르게 구현하면 AC를 받을 수 있다.

내 코드의 시간 복잡도는 $O(n^{2}logn)$이다. 코드는 다음과 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <bits/stdc++.h>
#define f first
#define s second
#define MOD 1000000007
#define PMOD 998244353
#define pb(x) push_back(x)
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> plii;
typedef pair<int, pii> piii;
const int INF = 1e9+10;
const ll LINF = 1LL*INF*INF;
const int MAXN = 4e6+10;
const int MAXM = 2e3+10;

priority_queue<int> pq;
vector<vector<int> > graph;
queue<int> que;

int A[MAXM];
int B[MAXM];
int calA[MAXM];
int calB[MAXM];
int cal[MAXN];

vector<int> valA;
vector<int> valB;

vector<int> val;

int main()
{
    int n,m,k,a,b,x,y,q;
    int sum = 0;
    int cnt = 0;
    int mx = 0;
    int mn = INF;
    int cur = 0, idx = -1;
    int tc;

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n;

    for(int i=0;i<n;i++)
        cin>>A[i];

    for(int i=0;i<n;i++)
        cin>>B[i];

    for(int i=0;i<n;i++){
        valA.push_back(A[i]);
        valB.push_back(B[i]);
    }
    sort(valA.begin(),valA.end());
    valA.erase(unique(valA.begin(),valA.end()),valA.end());

    sort(valB.begin(),valB.end());
    valB.erase(unique(valB.begin(),valB.end()),valB.end());

    int asz = (int)valA.size();
    int bsz = (int)valB.size();

    for(int i=0;i<asz;i++){
        for(int j=0;j<bsz;j++){
            val.push_back(valA[i]^valB[j]);
        }
    }

    sort(val.begin(),val.end());
    val.erase(unique(val.begin(),val.end()),val.end());

    for(int i=0;i<n;i++){
        idx = lower_bound(valA.begin(),valA.end(),A[i])-valA.begin();
        calA[idx]++;
        idx = lower_bound(valB.begin(),valB.end(),B[i])-valB.begin();
        calB[idx]++;
    }

    for(int i=0;i<asz;i++){
        for(int j=0;j<bsz;j++){
            if(calA[i]==calB[j]){
                cur = valA[i]^valB[j];
                idx = lower_bound(val.begin(),val.end(),cur)-val.begin();
                cal[idx]+=calA[i];
            }
        }
    }

    int vsz = (int)val.size();

    vector<int> ans;

    for(int i=0;i<vsz;i++){
        if(cal[i]==n){
            ans.push_back(val[i]);
        }
    }

    int sz = (int)ans.size();

    cout<<sz<<"\n";

    for(int i=0;i<sz;i++){
        cout<<ans[i]<<"\n";
    }


    return 0;
}

C. LCM of GCDs

여담으로, 2020 Yokohama regional에 같은 제목의 문제가 있다.

링크에서 확인 가능하다.

처음에는 합의 LCM인 줄 알고 삽질 하다가… 문제를 다시 읽고 풀었다.

우선 각 가방 내의 수들의 GCD의 LCM이라는 점을 생각하면, 결국 가능한 $X,Y$들의 후보는 처음에 들어갔던 수들의 약수임을 알 수 있다. 그리고, 현재 $a_{i},b_{i} \leq 1000000000$이므로, 약수의 개수가 아무리 많아봤자 $O(n^{\frac{1}{3}})$에 비례 하고 현재 범위에선 대충 $6$배 정도의 상수가 붙는 다는 것을 감안하면, 대충 $6000$개 안에 들어갈 것이라 생각할 수 있고, 따라서 쌍의 개수는 많아봤자 $36000000$개 정도일 것이다. 그리고 $N \leq 50$이므로, 4초라는 제한시간을 생각하면 $N$번 순회하면서 모든 쌍이 가능한지 dp를 통해 체크하면 시간 안에 돌것이라는 것을 알 수 있다.

만약 dp가 아니라 그리디를 쓰면 WA를 받는다고 한다. 수작업을 한 케이스가 있는 듯.

시간을 아끼기 위해서, 미리 처음 수의 약수들과 현재 수들의 gcd를 미리 계산 해두고, $X,Y$ 값은 새로운 카드를 집어 넣을 때마다 항상 증가하지 않는 다는 점을 이용해서 순회한다. 또, 미리 정렬해서 특정 케이스에서 봐야하는 쌍의 수를 약간 줄이는 (실제론 늘어날 수도 있다.) 처리를 해준다.

위의 약수의 개수에 관한 내용은

링크를 통해서 확인 가능하다.

좀 더 엄밀한 bound를 원한다면 이쪽을 참고하라.

좋은 자료를 주신 evenharder님과 rkm0959에게 감사를 표한다.

코드는 다음과 같다. 시간 복잡도는 $O(Nk^{\frac{2}{3}})$이다. 실행시간은 113ms로, 매우 빠르게 돈다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <bits/stdc++.h>
#define f first
#define s second
#define MOD 1000000007
#define PMOD 998244353
#define pb(x) push_back(x)
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> plii;
typedef pair<int, pii> piii;
const int INF = 1e9+10;
const ll LINF = 1LL*INF*INF;
const int MAXN = 2e5+10;
const int MAXM = 6e3+10;

priority_queue<int> pq;
vector<vector<int> > graph;
queue<int> que;

pii A[MAXN];
char S[MAXN];

int AA[MAXM];
int AB[MAXM];
int BA[MAXM];
int BB[MAXM];

int mygcd(int a,int b){
    return a?mygcd(b%a,a):b;
}

bool chk[MAXM][MAXM];

int main()
{
    int n,m,k,a,b,x,y,q;
    int sum = 0;
    int cnt = 0;
    int mx = 0;
    int mn = INF;
    int cur = 0, idx = -1;
    int tc;

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n;

    for(int i=0;i<n;i++){
        cin>>A[i].f>>A[i].s;
        if(A[i].f>A[i].s)swap(A[i].f,A[i].s);
    }

    sort(A,A+n);

    vector<int> fac;
    vector<int> ffac;

    k = A[0].f;

    for(int i=1;i*i<=k;i++){
        if(!(k%i)){
            fac.push_back(i);
            if(i*i<k)fac.push_back(k/i);
        }
    }

    m = A[0].s;

    for(int i=1;i*i<=m;i++){
        if(!(m%i)){
            ffac.push_back(i);
            if(i*i<m)ffac.push_back(m/i);
        }
    }

    sort(fac.begin(),fac.end());
    sort(ffac.begin(),ffac.end());

    int fsz = (int)fac.size();
    int ffsz = (int)ffac.size();

    chk[fsz-1][ffsz-1] = true;

    for(int t=1;t<n;t++){

        a = A[t].f;
        b = A[t].s;

        for(int i=0;i<fsz;i++){
            cur = mygcd(a,fac[i]);
            AA[i] = lower_bound(fac.begin(),fac.end(),cur)-fac.begin();
        }

        for(int i=0;i<ffsz;i++){
            cur = mygcd(a,ffac[i]);
            AB[i] = lower_bound(ffac.begin(),ffac.end(),cur)-ffac.begin();
        }

        for(int i=0;i<fsz;i++){
            cur = mygcd(b,fac[i]);
            BA[i] = lower_bound(fac.begin(),fac.end(),cur)-fac.begin();
        }

        for(int i=0;i<ffsz;i++){
            cur = mygcd(b,ffac[i]);
            BB[i] = lower_bound(ffac.begin(),ffac.end(),cur)-ffac.begin();
        }

        for(int i=0;i<fsz;i++){

            for(int j=0;j<ffsz;j++){
                if(chk[i][j]){
                    chk[i][j] = false;
                    a = AA[i];
                    b = BB[j];
                    chk[a][b] = true;
                    a = AB[j];
                    b = BA[i];
                    chk[b][a] = true;
                }
            }
        }
    }

    ll res = 0;
    ll curv;

    for(int i=0;i<fsz;i++){
        for(int j=0;j<ffsz;j++){
            if(chk[i][j]){
                curv = 1LL*fac[i]*ffac[j];
                curv /= mygcd(fac[i],ffac[j]);
                res = max(res,curv);

            }
        }
    }

    cout<<res<<"\n";

    return 0;
}

D. Yet Another Sorting Problem

$N,M$인 조건만 없다면 굉장히 Well Known인 문제이다. 순열을 그래프로 표현했을 때, 전체 수의 개수 $K$에서 연결 컴포넌트의 개수 $C$를 뺀 $K-C$가 swap에서 제한이 없을 때의 정답이다. (여기서 순열 그래프란, permutaion $p$에 대해서, 정점 $i$에 대해 $i$에서 $p_i$로 가는 edge가 있는 그래프를 의미한다.)

하지만 이 문제에선 $1 \leq i \leq N$인 $i$와 $N+1 \leq j \leq N+M$인 $i,j$에 대해서만 swap을 진행할 수 있다는 제한 조건이 있다.

우선 원래 문제에서 swap operation이 그래프 상에서 어떤 작업과 같은지 한번 보자. 위에서 언급한 제한이 없는 경우에서, swap operation은 현재 그래프 상에서 인접한 두 indices에 대해 적용하는게 최선이다. 좀 더 formal하게 말하면, 어떤 $i$에 대해 $i$가 가리키는 정점이 $j$이면, $i,j$에 대해 swap을 적용시켜 나가는 것이 최적이다.

이 연산이 그래프 상에서 어떤 식으로 구현되는지 보면, $i,j$에서 swap을 할 때 $j$가리키는 정점을 $k$라 할 때, $j$는 이제 자기 자신을 가리키게 되고, $i$가 $k$를 가리키게 된다. 이것에 집중하면 문제를 해결할 실마리를 잡을 수 있다.

이제 다시 제한이 있는 경우로 돌아와서, 제한에 의해서 swap을 적용할 수 있는 경우는, $i$가 $N$이하이고, $j$가 $N$초과이거나, 또는 그 반대여야만 한다. 이는 그래프 상에서 인접한 정점이 한쪽은 $N$이하고, 다른 한쪽은 그렇지 않은 경우만 바꿀 수 있다는 것이다. 이 성질을 이용하면, 순열 그래프에서 어떤 연결 컴포넌트에 대해, 컴포넌트 내에서 $N$이하인 점과 $N$초과인 점이 모둔 들어 있는 컴포넌트는 변함 없이 컴포넌트 내의 정점 개수를 $A$라 하면 $A-1$번 만에 모두 해결할 수 있다.

어느 한쪽만 있는 경우가 문제 인데, 만약 컴포넌트 내의 정점 개수가 1개라면, 이미 제자리에 있으니 신경 쓰지 않아도 된다. 만약 $N$이하인 수들만 포함하고, 정점 개수가 2 이상인 컴포넌트가 $W$개, $N$초과인 수들만 있고 정점 개수가 2 이상인 컴포넌트가 $B$개 있다고 하자. 컴포넌트 내에선 정렬이 불가능하니, 적절히 병합한 후 해결해야 함을 어렵지 않게 알 수 있다. 이때, $W,B$개의 컴포넌트들을 최대한 짝지어 병합한다. 그러고 어느 한쪽이 남는다면, 아무 컴포넌트에 적절히 병합한다. 그후 정렬 시키면 답을 얻는다. 따라서 병합 시의 비용을 계산하면 되는데, 이는 코드를 참고해도 충분할 것이라 생각한다.

순열 그래프에 대한 감은 이 문제를 풀면 대략적으로 알 수 있을 것이다.

순열 그래프는 그 여러 가지 성질 때문에, 자주 나오니 공부해두자.

코드는 다음과 같다. 시간 복잡도는 $O(N+M)$이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>
#define f first
#define s second
#define MOD 1000000007
#define PMOD 998244353
#define pb(x) push_back(x)
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> plii;
typedef pair<int, pii> piii;
const int INF = 1e9+10;
const ll LINF = 1LL*INF*INF;
const int MAXN = 2e5+10;
const int MAXM = 5e3+10;

priority_queue<int> pq;
vector<vector<int> > graph;
queue<int> que;

int A[MAXN];
char S[MAXN];

bool vis[MAXN];
int cycle[MAXN];
int cal[MAXN];
int bb[MAXN];

int main()
{
    int n,m,k,a,b,x,y,q;
    int sum = 0;
    int cnt = 0;
    int mx = 0;
    int mn = INF;
    int cur = 0, idx = -1;
    int tc;

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n>>m;

    for(int i=1;i<=n+m;i++)
    {
        cin>>A[i];
    }

    int num = 0;

    for(int i=1;i<=n+m;i++){
        if(vis[i])continue;
        cnt = 0;
        cur = i;

        num++;

        while(!vis[cur]){
            vis[cur] = true;
            cycle[cur] = num;
            cnt++;
            cur = A[cur];
        }

        cal[num] = cnt;
    }

    for(int i=1;i<=n;i++){
        cur = cycle[i];
        bb[cur]|=1;
    }

    for(int i=n+1;i<=n+m;i++){
        cur = cycle[i];
        bb[cur]|=2;
    }

    int cntb = 0;
    int cntw = 0;

    int cnto = 0;
    int res = 0;

    for(int i=1;i<=num;i++){
        if(cal[i]==1)continue;
        if(bb[i]==3){
            res += (cal[i]-1);
            continue;
        }

        assert(bb[i]);

        cnto+=cal[i];

        if(bb[i]==1)cntw++;
        else cntb++;
    }

    cur = max(cntb-cntw,cntw-cntb);
    cnto+=cur;

    cout<<res+cnto<<"\n";

    return 0;
}