UCPC 2021 예선 후기 및 풀이

작성일 | In |

들어가기 전에

어제 UCPC 2021이 본선까지 모두 끝났다. 예선은 더 전인 7월 31일에 끝났지만, 후기를 쓴다는 걸 까먹어서, 대략적인 후기와 풀이를 같이 올리기로 결정했다.

팀을 구성할 때의 이야기를 잠시 하면, 나름 고등학교 부터 PS를 했지만, 서울대 소속으로 ICPC 본선에 나가는 벽은 너무도 높았다. 작년에도 꽤 강한 팀이었고, 예선 때의 컨디션도 좋았지만, 본선에 나가는데 실패했다. 올해에는 반드시 regional 본선에 가고 싶었기 때문에, 강한 팀을 만들고 싶었다. 그래서 팀원을 비교적 빠른 시간부터 물색하던 중, Sait2000님께 연락해봐야겠다고 생각했고, Sait님이 제안을 수락하시면서 ICPC를 같이 하기로 했다.

그리고 UCPC 시즌이 되고, UCPC를 Sait님과 함께 나가게 되서 남은 팀원을 찾고 있었는데, 계절학교 동기인 IHHI와 연락이 닿아서 UCPC를 일단 같이 하기로 했고, 팀연습을 진행하면서 합이 잘 맞아서 ICPC도 같이 하기로 결정했다.

UCPC 예선의 경우 각자 사정으로 따로 치되, discord를 활용해서 소통하기로 하였다. 두 번 정도의 예선 연습을 했다.

팀연습의 결과가 꽤 괜찮았고, 멤버들의 실력도 좋았기 때문에, 예선을 무난하게 통과하리라 기대하며 대회를 준비했다.

대회 진행 과정

팀연습에서 했던 대로 문제 셋을 적당히 3등분에 가깝게 나눠서 처음 문제들은 내가, 중간 문제는 Sait님이, 마지막은 IHHI가 보는 식으로 분할 했다.

총 10문제 였기 때문에 4 - 3 - 3으로 분할 했다.

A를 읽어보니 쉬운 문제 여서 빠르게 구현 후 AC. - 7분 경

B를 읽고 구현하고 있던 중 그리고 IHHI 가 H를 읽고 AC. - 15분 경

Sait님이 G를 2틀 하시고 AC. - 16분 경

이때의 2틀이 대회에서 유일한 AC 외의 결과 였다.

그리고 얼마 안 지나서 내가 B를 구현한 후 맞아서 AC. - 16분 경

여담으로, 이 시점에서 1위를 기록하고 있었다.

C를 읽었는데, 기댓값이라서 일단 넘기고 D를 고민했다.

D를 계속 고민하고 있던 중, 나머지 팀원들도 각자 맡은 문제 읽는게 끝났다.

Sait님이 I를 보고 싶어 하셨고, E가 쉬운 듯 생각이 잘 안 나신 다고 해서 IHHI에게 넘겼다.

C를 빨리 봐야 할 것 같아서 Sait님에게 봐달라고 부탁했고, Sait신이 빠르게 구현해서 맞았다. - 29분 경

C를 AC 받은 후, 난 계속 D를 고민하고, Sait님은 I를, IHHI는 E를 잡았다.

D를 고민해도 계속 안 풀려서, 잠시 점검을 했는데 J가 트리 관련 문제란 제보를 받고

읽어 보기로 했다. 보고 centroid군… 하면서 내가 잡기로 했다.

J로 가기 전에 D에 관한 관찰을 남겨놓고, J를 구현하러 갔다.

그리고 좀 있다가 Sait신이 I를 구현해서 맞았다. - 57분 경

얼마 안 있다가 IHHI가 E를 구현해서 맞았다 - 1시간 3분 경

내가 J를 계속 구현 중이었고, D가 꽤 풀리는 것 같아서 빨리 해치워야 할 것 같았기 때문에, IHHI에게 고민해달라고 부탁했다.

그런데 Sait님이 proof by ac 풀이를 떠올렸고, IHHI가 풀이를 듣고 맞는 것 같다! 라고 해서, 일단 구현. proof by AC 성공 - 1시간 14분 경

이제 남은 문제가 F, J 밖에 없었기 때문에 Sait님과 IHHI는 F를 잡았고, 난 J를 계속 구현했다.

J구현을 마치고 예제가 나왔기 때문에 일단 제출. AC - 1시간 27분 경

이때 Sait님과 IHHI는 F 풀이를 거의 완성하고 있었다. 그리고 그렇게 구한 풀이를 각자 구현 하기로 하였다. 난 풀이를 정확히 이해하는데 좀 애를 먹고, 좀 늦게 구현 하다가 Sait신이 AC - 1시간 55분 경

이렇게 대회 시작 후 2시간이 되기 전에 올솔브를 했고, 남은 시간은 팀연습 마치고 할 때 처럼 A 부터 순서대로 푼 사람이 풀이를 설명하고 토의 하는 시간을 가졌다.

그렇게 풀이를 다 말하고 나니까 어느 새 예선이 거의 끝나 있었다.

휴식을 취하면서 gravekper님의 방송을 시청하고 있었고, 스코어보드 까는 것을 지켜봤다.

결과는 아래와 같이 무려 4위.

전체적으로 굉장히 좋았다고 생각한다. Sait님이 나와 IHHI가 껄끄러워 하는 구현을 빠르게 처리해주셨고, IHHI도 E를 처리 해주었다. 그리고 나도 J를 처리해서 각자가 어느 정도 역할을 했다

Sait신이 캐리 했다는 것을 부정할 수 없지만, 나머지 팀원들도 0.7인분은 했다는 것이 내 생각이다.

결과도 4위로 무척이나 좋았다.

솔직히 대회 치기 전엔 잘하는 팀이 워낙 많아서, 말 그대로 무난히 본선 가는 정도로 예상했는데 4위를 기록해서 무척이나 기쁘기도 하고, 놀라기도 했다.

결과를 보고 운이 따라준다면 진지하게 UCPC에서도 상을 딸 수 있을 것이라 생각하게 됐다.

문제 풀이 및 구현

아래는 각 문제의 풀이다. 대회가 끝나고 업솔빙을 진행했고, I를 제외한 모든 문제를 풀었다.

I는 나중에 따로 올리던지, 여기에 추가하던지 할 예정이다.

A. 수학은 체육과목 입니다 3

수의 범위가 작으므로 (1이상 999이하) 모든 시작 수에 대해서 다 해봐도 시간 안에 무리 없이 돌아간다.

시작 수를 정해 놓고, 계속 문자열과 매치 시켜가면서 해당 시작 수에 대해 정확하게 매치되는 끝 수가 있는지 확인만 해주면 된다.

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
#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 solve(int n,int x){

    int idx = 0;

    int a,b,c;

    int res = -1;

    for(int i=x;;i++){

        if(i>=1000){
            res = -1;
            break;
        }
        a = (i/100);
        b = (i/10)%10;
        c = (i%10);

        if(a){
            if(idx+3>n){
                res = -1;
                break;
            }
            else if(A[idx]==a&&A[idx+1]==b&&A[idx+2]==c){
                idx += 3;
                if(idx==n){
                    res = i;
                    break;
                }
            }
            else {
                res = -1;
                break;
            }
        }
        else if(b){
            if(idx+2>n){
                res = -1;
                break;
            }
            else if(A[idx]==b&&A[idx+1]==c){
                idx += 2;
                if(idx==n){
                    res = i;
                    break;
                }
            }
            else {
                res = -1;
                break;
            }
        }
        else {
            if(idx+1>n){
                res = -1;
                break;
            }
            else if(A[idx]==c){
                idx++;
                if(idx==n){
                    res = i;
                    break;
                }
            }
            else {
                res = -1;
                break;
            }
        }
    }

    return res;
}

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>>S;

    n = strlen(S);

    for(int i=0;i<n;i++){
        A[i] = S[i]-'0';
    }

    int idy = -1;

    for(int i=1;i<=999;i++){
        cur = solve(n,i);
        if(cur!=-1){
            idx = i;
            idy = cur;
            break;
        }
    }
    cout<<idx<<" "<<idy<<"\n";

    return 0;
}

B. 항체 인식

먼저 이전과 이후에서 달라진 부분이 없으면 그냥 YES이다.

달라진 부분이 하나라도 있으면, 그 셀을 X 라고 하자. X가 이전에는 a,이후에는 b 값을 가진다면, 그 셀과 같은 수(a)를 가지면서 상하좌우 이동을 통해 이동 가능한 모든 셀에 대해 그 값을 b로 바꾼다.

이제 다시 이전과 이후를 비교해서 다른게 하나라도 있는지 판별한다.

없다면, YES이다. 같으면 NO가 된다.

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
#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<pii> que;

int A[110][110];
int B[110][110];
bool vis[110][110];

int gx[10] = {-1,0,0,1};
int gy[10] = {0,-1,1,0};

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,idy = -1;
    int tc;

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

    cin>>n>>m;

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

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

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(A[i][j]^B[i][j]){
                idx = i;
                idy = j;
                break;
            }
        }
        if(idx!=-1)break;
    }

    if(idx==-1){
        cout<<"YES\n";
        return 0;
    }

    vis[idx][idy] = true;
    cur = A[idx][idy];

    que.push(pii(idx,idy));

    while(!que.empty()){

        x = que.front().f;
        y = que.front().s;
        que.pop();

        for(int i=0;i<4;i++){
            a = x+gx[i];
            b = y+gy[i];

            if(a<0||a>n)continue;
            if(b<0||b>m)continue;

            if(vis[a][b])continue;
            if(A[a][b]^cur)continue;

            vis[a][b] = true;

            que.push(pii(a,b));
        }

    }

    int curv = B[idx][idy];

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(vis[i][j])A[i][j] = curv;
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(A[i][j]^B[i][j])cnt++;
        }
    }

    if(cnt)cout<<"NO\n";
    else cout<<"YES\n";


    return 0;
}

C. 헤이카카오

우선 $a$ 는 신경 쓸 필요 없다. 마지막에 $a$를 곱해주면 된다.

$d,k$ 가 중요하다.

$F(d,k)$가 한 판에 진행되는 시간이 1일 때, 끝말잇기를 진행하는 시간의 기댓값을 반환한다고 하면,

$d \geq 100$ 일 때, $F(d,k) = 1$이다. $d < 100$일 때, $F(d,k) = d/100 + (1-d/100)F(d+dk/100,k)$이 성립한다.

이 점화식을 그대로 구현하면 된다. 시간초과가 날 것이라 걱정할 수 있지만, 무난히 돌아간다.

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
#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];

double solve(double d,double k){

    if(d>=1.0){
        return 1.0;
    }

    double res = d;
    double curv = (double)1.0+solve(d*((double)1.0+k),k);

    res += ((double)1.0-d)*curv;

    return res;
}

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>>a>>x>>y;

    double dd = (double)x/(double)100.0;
    double kk = (double)y/(double)100.0;



    double res = solve(dd,kk);

    res*=(double)a;

    cout<<fixed;
    cout.precision(15);

    cout<<res<<"\n";

    return 0;
}

D. 돌 가져가기

일단 관찰할 수 있는 것은, 색깔이 같으면서 연속된 것들을 생각하면, 그 중에 하나만 점수를 얻을 수 있다. 따라서 압축한 후 그 중의 최댓값들만 고려해도 무방하다.

그리고 또 하나는, 양 쪽 끝에 있는 것들은 가져갈 수 없다.

그리고 마지막 관찰은, 가져가는 개수가 정해져 있다는 것이다.

정확히 양 끝을 제외하고 $k$개의 값을 고려한다면, $k = 2m$이면 $m$, $k = 2m+1$이면 $m+1$개를 가져간다. $a$개를 가져 간다고 하면, $k$ 개의 값 중 가장 큰 $a$개의 수들의 합 보다 답이 클 수 없다는 것을 알 수 있다.

그리고 위와 같이 가져가는 방법이 존재하며, 이 내용을 구현하면 맞는다.

자세한 증명은 풀이 슬라이드 참조.

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
#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 = 3e5+10;
const int MAXM = 5e3+10;

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

int A[MAXN];
char S[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;

    cin>>S+1;

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

    vector<int> val;

    S[0] = S[1];

    mx = 0;

    for(int i=1;i<=n;i++){
        if(S[i]^S[i-1]){
            val.push_back(mx);
            mx = A[i];
        }
        else {
            mx = max(mx,A[i]);
        }
    }

    val.push_back(mx);

    vector<int> rval;

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

    for(int i=1;i<vsz-1;i++){
        rval.push_back(val[i]);
    }

    sort(rval.begin(),rval.end(),greater<int>());

    int rsz = (int)rval.size();

    m = (rsz+1)>>1;

    ll res = 0;

    for(int i=0;i<m;i++){
        res += (ll)rval[i];
    }

    cout<<res<<"\n";

    return 0;
}

E. 말뚝

우선 할 수 있는 관찰은, 정확히 연속한 $K$개의 높이를 같게 하는 값을 계산해도 된다는 것이다. 이상으로 하면 비용이 더 많이 들었으면 들었지 줄지 않으니까.

그리고 어떤 말뚝에 대해서 조정하는 높이에 따른 비용 함수의 그래프를 그리면, 절댓값 함수와 비슷한 개형의 꺽은선 그래프가 됨을 알 수 있다.

따라서 비용 함수 몇 개를 합한 것을 생각하면, 볼록한 모양임을 알 수 있다. 정확히는 직선 여러개가 이어져 있는데, 기울기가 x 좌표가 커질 수록 증가하는 형태가 된다. 따라서, 어떤 점 x에 대해 x이상인 좌표들에 대해서 그 기울기가 음이 아닌 최소의 지점을 찾고, 그 지점에서의 비용을 구하면 된다는 것을 알 수 있다. 이건 삼분탐색이나, 이분탐색으로 빠르게 찾을 수 있고, 함수의 추가와 삭제를 빠르게 하기 위햇 세그트리 등을 이용한다. 난 세그 트리 (인덱스 트리 ) + 이분탐색으로 구현했다.

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
#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];
int B[MAXN];
int H[MAXN];
char S[MAXN];

ll atree[MAXN*4];
ll btree[MAXN*4];
ll axtree[MAXN*4];
ll bxtree[MAXN*4];

inline void update(int tmp,int a,int b,int x){

    atree[tmp]+=(ll)a;
    btree[tmp]+=(ll)b;
    axtree[tmp]+=(1LL*a*x);
    bxtree[tmp]+=(1LL*b*x);
    tmp>>=1;

    while(tmp){
        atree[tmp] = atree[(tmp<<1)]+atree[(tmp<<1)|1];
        btree[tmp] = btree[(tmp<<1)]+btree[(tmp<<1)|1];
        axtree[tmp] = axtree[(tmp<<1)]+axtree[(tmp<<1)|1];
        bxtree[tmp] = bxtree[(tmp<<1)]+bxtree[(tmp<<1)|1];
        tmp>>=1;
    }

    return;
}

inline ll getans(int base){

    int tmp = 1;

    ll va = 0;
    ll vb = 0;
    ll vax = 0;
    ll vbx = 0;

    while(tmp<base){

        if(va+atree[(tmp<<1)]>=vb+btree[(tmp<<1)|1]){
            vb += btree[(tmp<<1)|1];
            vbx += bxtree[(tmp<<1)|1];
            tmp<<=1;
        }
        else {
            va += atree[(tmp<<1)];
            vax += axtree[(tmp<<1)];
            tmp<<=1;
            tmp|=1;
        }
    }

    ll idx = (tmp-base);

    ll res = (idx*va-vax)+(vbx-idx*vb);

    return res;
}

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>>k;

    for(int i=1;i<=n;i++){
        cin>>H[i];
        mx = max(mx,H[i]);
    }

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

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

    int base = 1;

    for(;base<=mx;base<<=1);

    for(int i=1;i<=k;i++){
        update(base+H[i],A[i],B[i],H[i]);
    }

    ll res = getans(base);

    for(int i=k+1;i<=n;i++){
        update(base+H[i],A[i],B[i],H[i]);
        update(base+H[i-k],-A[i-k],-B[i-k],H[i-k]);

        res = min(res,getans(base));
    }

    cout<<res<<"\n";

    return 0;
}

F. 종이, 펜, 삼각형

일단 한 점에서 동시에 만나는게 아닌 이상, 충분히 큰 평면에 대해서는 정삼각형을 이룬다는 것을 알 수 있다. 문제는 그것이 기존의 큰 정삼각형 안에 들어가야 한다는 것이다.

편의상 직선의 기울기가 커지는 순서대로 $a$방향, $b$방향, $c$방향이라 하자. 그리고 기존에 있었던 $a$방향, $b$방향, $c$방향 직선 (큰 정삼각형을 이루는 직선들)을 $a0,b0,c0$이라 하자. 그럼 다음과 같은 경우로 나누어 개수를 셀 수 있다.

  • 기존의 큰 정삼각형
  • $a0$와 $b,c$ 방향 직선이 이루는 정삼각형
  • $b0$와 $a,c$ 방향 직선이 이루는 정삼각형
  • $c0$와 $a,b$ 방향 직선이 이루는 정삼각형
  • $a0,b0$와 $c$ 방향 직선이 이루는 정삼각형
  • $b0,c0$와 $a$ 방향 직선이 이루는 정삼각형
  • $a0,c0$와 $b$ 방향 직선이 이루는 정삼각형
  • $a,b,c$ 방향 직선이 이루는 정삼각형

$a,b,c$ 방향 직선이 이루는 정삼각형의 경우를 제외하면 정렬과 세그 트리 등을 이용해 세 줄 수 있다. $a,b,c$ 방향 직선이 이루는 정삼각형의 경우, 세그 트리를 통해서 세어주되, 세 직선이 한 점에서 만나는 경우를 고려해주어야 한다. 이는 fft를 통해 풀 수 있다.

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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
#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;

namespace fft{

typedef complex<double> base;
void fft(vector<base> &a, bool inv){
	int n = a.size(), j = 0;
	vector<base> roots(n/2);
	for(int i=1; i<n; i++){
		int bit = (n >> 1);
		while(j >= bit){
			j -= bit;
			bit >>= 1;
		}
		j += bit;
		if(i < j) swap(a[i], a[j]);
	}
	double ang = 2 * acos(-1) / n * (inv ? -1 : 1);
	for(int i=0; i<n/2; i++){
		roots[i] = base(cos(ang * i), sin(ang * i));
	}
	/* In NTT, let prr = primitive root. Then,
	int ang = ipow(prr, (mod - 1) / n);
	if(inv) ang = ipow(ang, mod - 2);
	for(int i=0; i<n/2; i++){
		roots[i] = (i ? (1ll * roots[i-1] * ang % mod) : 1);
	}
	XOR Convolution : set roots[*] = 1.
	OR Convolution : set roots[*] = 1, and do following:
    if (!inv) {
        a[j + k] = u + v;
        a[j + k + i/2] = u;
    } else {
        a[j + k] = v;
        a[j + k + i/2] = u - v;
    }
	*/
	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/2; k++){
				base u = a[j+k], v = a[j+k+i/2] * roots[step * k];
				a[j+k] = u+v;
				a[j+k+i/2] = u-v;
			}
		}
	}
	if(inv) for(int i=0; i<n; i++) a[i] /= n; // skip for OR convolution.
}

vector<ll> multiply(vector<ll> &v, vector<ll> &w){
	vector<base> fv(v.begin(), v.end()), fw(w.begin(), w.end());
	int n = 2; while(n < v.size() + w.size()) n <<= 1;
	fv.resize(n); fw.resize(n);
	fft(fv, 0); fft(fw, 0);
	for(int i=0; i<n; i++) fv[i] *= fw[i];
	fft(fv, 1);
	vector<ll> ret(n);
	for(int i=0; i<n; i++) ret[i] = (ll)round(fv[i].real());
	return ret;
}
vector<ll> multiply(vector<ll> &v, vector<ll> &w, ll mod){
	int n = 2; while(n < v.size() + w.size()) n <<= 1;
	vector<base> v1(n), v2(n), r1(n), r2(n);
	for(int i=0; i<v.size(); i++){
		v1[i] = base(v[i] >> 15, v[i] & 32767);
	}
	for(int i=0; i<w.size(); i++){
		v2[i] = base(w[i] >> 15, w[i] & 32767);
	}
	fft(v1, 0);
	fft(v2, 0);
	for(int i=0; i<n; i++){
		int j = (i ? (n - i) : i);
		base ans1 = (v1[i] + conj(v1[j])) * base(0.5, 0);
		base ans2 = (v1[i] - conj(v1[j])) * base(0, -0.5);
		base ans3 = (v2[i] + conj(v2[j])) * base(0.5, 0);
		base ans4 = (v2[i] - conj(v2[j])) * base(0, -0.5);
		r1[i] = (ans1 * ans3) + (ans1 * ans4) * base(0, 1);
		r2[i] = (ans2 * ans3) + (ans2 * ans4) * base(0, 1);
	}
	fft(r1, 1);
	fft(r2, 1);
	vector<ll> ret(n);
	for(int i=0; i<n; i++){
		ll av = (ll)round(r1[i].real());
		ll bv = (ll)round(r1[i].imag()) + (ll)round(r2[i].real());
		ll cv = (ll)round(r2[i].imag());
		av %= mod, bv %= mod, cv %= mod;
		ret[i] = (av << 30) + (bv << 15) + cv;
		ret[i] %= mod;
		ret[i] += mod;
		ret[i] %= mod;
	}
	return ret;
}
}

vector<int> A;
vector<int> B;
vector<int> C;

int AA[MAXN];
int BB[MAXN];
int CC[MAXN];

int tree[MAXN*4];

void update(int tmp){

    while(tmp){
        tree[tmp]++;
        tmp>>=1;
    }

    return;
}

int getans(int L,int R){

    int res = 0;

    while(L<=R){
        if(L&1){
            res += tree[L];
            L++;
        }
        if(!(R&1)){
            res += tree[R];
            R--;
        }
        L>>=1; R>>=1;
    }

    return res;
}


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>>m>>q;

    for(int i=0;i<q;i++){
        cin>>a>>x;

        if(a==0){
            B.push_back(x);
        }
        else if(a==60){
            C.push_back(x);
        }
        else {
            A.push_back(x);
        }
    }

    sort(A.begin(),A.end());
    sort(B.begin(),B.end());
    sort(C.begin(),C.end());

    ll res = 1+q;

    int asz = (int)A.size();

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

        idx = lower_bound(B.begin(),B.end(),A[i])-B.begin();
        res += (ll)idx;

        idx = lower_bound(C.begin(),C.end(),A[i])-C.begin();
        res += (ll)idx;
    }

    int bsz = (int)B.size();
    int csz = (int)C.size();

    for(int i=0;i<bsz;i++){
        idx = lower_bound(C.begin(),C.end(),m-B[i])-C.begin();
        res += (ll)idx;
    }

    for(int i=0;i<asz;i++){
        AA[A[i]] = 1;
    }

    for(int i=0;i<bsz;i++){
        BB[B[i]] = 1;
    }

    for(int i=0;i<csz;i++){
        CC[C[i]] = 1;
    }

    int base = 1;

    for(;base<m;base<<=1);

    ll curv = 0;

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

        if(CC[i]){
            update(base+i);
        }

        if(BB[i]){
            curv += (ll)getans(base,base+m-i);
        }

        if(AA[i]){
            res += curv;
        }
    }

    fill(tree,tree+(base<<1),0);

    curv = 0;

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

        if(CC[i]){
            curv += (ll)getans(base,base+m-i);
        }

        if(BB[i]){
            update(base+i);
        }

        if(AA[i]){
            res += curv;
        }
    }

    vector<ll> vb;
    vector<ll> vc;

    vb = vector<ll> (m);
    vc = vector<ll> (m);

    for(int i=1;i<m;i++){
        vb[i] = BB[i];
        vc[i] = CC[i];
    }

    vector<ll> vres = fft::multiply(vb,vc);

    for(int i=1;i<m;i++){
        if(AA[i]){
            res -= vres[i];
        }
    }

    cout<<res<<"\n";


    return 0;
}

G. 경품 추첨

우선 느낌상 한 상자 내에선 규칙적으로 배열해야 할 것 같다. 수들이 등차수열이라고 하자. 어떤 상자 $a,b$에 대해서, 각 상자의 공차가 $d_{a},d_{b}$라고 두면,

$d_{a} \times v_{a} = d_{b} \times v_{b}$인 $v_{a},v_{b}$가 존재하지 않도록 하고 싶다.

이는 현재 제한을 생각해보면, 각 공차들이 2000보다 큰 소수일 경우 해결된다.

2000을 넘는 소수 중 작은 것부터 공차들을 정하면 충분히 제한 내에 들어가고, 그대로 해결할 수 있다.

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
#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 is_prime(int x){

    bool judge = true;

    for(int i=2;i*i<=x;i++){
        if(!(x%i)){
            judge = false;
            break;
        }
    }

    return judge;
}

void init(int k){

    int idx = 2001;

    for(int i=0;i<k;i++){
        while(true){
            if(is_prime(idx))break;
            idx++;
        }
        A[i] = idx;
        idx++;
    }

    return;
}

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>>k>>n;

    init(k);

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

        cur = A[i];

        for(int j=1;j<=n;j++){
            cout<<j*cur<<" ";
        }
        cout<<"\n";
    }

    return 0;
}

H. 스키장

제한을 주의 깊게 보지 않으면, 일반 그래프에서 최장경로를 구하는 형태가 되므로, 풀기 어렵다. 하지만, 제한을 본다면 $K <= 10 $으로, 역행 가능 횟수가 굉장히 작음을 알 수 있다.

따라서 역행 횟수와 최장 경로 길이를 함께 저장해 나가는 dp를 하면 된다.

여담으로, IHHI가 제한을 안 보고 어렵네 하고 지나쳤다가 제한을 보고 부랴부랴 코딩했다고…

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
#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];

ll dp[20][MAXN];

vector<pii> val[MAXN];
vector<int> vval[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>>k>>a>>b;

    for(int i=0;i<m;i++){
        cin>>x>>y>>cur;
        val[x].push_back(pii(y,cur));
        vval[y].push_back(x);
    }

    for(int i=1;i<=n;i++){
        dp[0][i] = -LINF;
    }

    dp[0][b] = 0;

    for(int i=b-1;i>=1;i--){
        for(int j=0;j<(int)val[i].size();j++){
            x = val[i][j].f;
            cur = val[i][j].s;
            dp[0][i] = max(dp[0][i],dp[0][x]+(ll)cur);
        }
    }

    ll curv = -LINF;

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

        for(int i=n;i>=1;i--){
            curv = -LINF;
            for(int j=0;j<(int)val[i].size();j++){
                x = val[i][j].f;
                cur = val[i][j].s;
                curv = max(curv,dp[t][x]+(ll)cur);
            }
            for(int j=0;j<(int)vval[i].size();j++){
                x = vval[i][j];
                curv = max(curv,dp[t-1][x]);
            }
            dp[t][i] = curv;
        }
    }

    ll res = dp[k][a];

    if(res<0)cout<<"-1\n";
    else cout<<res<<"\n";

    return 0;
}

I. 흔한 타일 색칠 문제

간단하게나마 풀이를 기술하면, 재귀를 통해서 해결할 수 있다.

사각형을 4등분하고, 비워져 있는 사각형을 제외한 나머지 사각형은 가운데쪽의 귀퉁이를 비우는 식으로 재귀를 하는 것.

자세한 풀이는 공식 풀이를 참고하기 바란다.

J. UCPC 만들기

centorid를 사용하는 유형이다. 결국 경로에서 $UCPC ^ {k}$꼴의 형태가 되기 위해서는, U,P의 개수가 같고, C와 나머지 문자의 개수가 서로 같으면 된다. 현재 보고 있는 트리에 대해 centroid를 root으로 하고, centroid의 자식들을 root로 하는 subtree에 대해서, 루트 부터 각 정점 까지 U,P 개수의 차와 C와 나머지 문자의 개수의 차를 함께 저장하고, 각 순서쌍이 몇 개나 있는지 저장한다. 그리고 각 subtree에 대해 자신을 제외한 나머지 subtree에서 자신이랑 합하면 두 차가 모두 0이 되는 것이 얼마나 있는지 센다. 현재 보고 있는 트리에서 해결하면, 이제 subtree에 대해서 다시 이 문제를 풀면 끝난다.

centroid에 대한 문제를 많이 풀어보면 쉽게 접근 가능한 유형.

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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
#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;
vector<vector<int> >ctree;
queue<int> que;

pii curval[MAXN];
vector<pii> val[MAXN];
vector<int> cal[MAXN];

int chk[MAXN];
int subtree[MAXN];
char S[MAXN];

ll ans = 0;

void dfs(int here,int p)
{
    int there;

    subtree[here] = 1;

    for(int i=0;i<graph[here].size();i++){
        there = graph[here][i];
        if(there==p)continue;
        if(chk[there])continue;
        dfs(there,here);
        subtree[here]+=subtree[there];
    }

    return;
}

int mysearch(int here,int p,int sz)
{
    int there;
    int idx = -1;
    int mx = 0;

    for(int i=0;i<graph[here].size();i++){
        there = graph[here][i];
        if(there==p)continue;
        if(chk[there])continue;
        if(mx<subtree[there]){
            mx = subtree[there];
            idx = i;
        }
    }

    if(idx==-1){
        return here;
    }

    if((mx<<1)<=sz)return here;

    return mysearch(graph[here][idx],here,sz);
}

int cent;

void ddfs(int here,int p){

    int there;

    if(S[here]=='U'){
        curval[here].f--;
        curval[here].s++;
    }
    else if(S[here]=='P'){
        curval[here].f--;
        curval[here].s--;
    }
    else {
        curval[here].f++;
    }

    val[cent].push_back(curval[here]);

    for(int i=0;i<graph[here].size();i++){
        there = graph[here][i];
        if(there==p)continue;
        if(chk[there])continue;
        curval[there] = curval[here];
        ddfs(there,here);
    }

    return;
}

int va,vb;

void getans(int here,int p){

    int there;

    int x = -curval[here].f;
    int y = -curval[here].s;

    x+=va;
    y+=vb;

    int idx = lower_bound(val[cent].begin(),val[cent].end(),pii(x,y))-val[cent].begin();

    if(idx<(int)val[cent].size()){
        if(val[cent][idx].f==x&&val[cent][idx].s==y){
            ans += (ll)cal[cent][idx];
        }
    }

    for(int i=0;i<graph[here].size();i++){
        there = graph[here][i];
        if(there==p)continue;
        if(chk[there])continue;
        getans(there,here);
    }

    return;
}


void update(int here,int p){

    int there;

    int idx = lower_bound(val[cent].begin(),val[cent].end(),curval[here])-val[cent].begin();
    cal[cent][idx]++;

    for(int i=0;i<graph[here].size();i++){
        there = graph[here][i];
        if(there==p)continue;
        if(chk[there])continue;
        update(there,here);
    }

    return;
}

void solve(int here,int sz,int num)
{
    if(sz==1){
        chk[here] = num;
        return ;
    }

    dfs(here,0);

    int res = mysearch(here,0,sz);

    chk[res] = num;

    cent = res;

    curval[res] = pii(0,0);

    ddfs(res,0);

    sort(val[res].begin(),val[res].end());
    val[res].erase(unique(val[res].begin(),val[res].end()),val[res].end());

    int vsz = (int)val[res].size();

    cal[res] = vector<int> (vsz);

    int idx = lower_bound(val[res].begin(),val[res].end(),curval[res])-val[res].begin();
    cal[res][idx]++;

    if(S[res]=='U'){
        va = -1;
        vb = 1;
    }
    else if(S[res]=='P'){
        va = -1;
        vb = -1;
    }
    else {
        va = 1;
        vb = 0;
    }

    int there;

    for(int i=0;i<graph[res].size();i++){
        there = graph[res][i];
        if(chk[there])continue;
        getans(there,res);
        update(there,res);
    }

    int nxtsz;
    int nxt;

    for(int i=0;i<graph[res].size();i++){
        there = graph[res][i];
        if(chk[there])continue;

        if(subtree[res]>subtree[there])nxtsz = subtree[there];
        else nxtsz = sz-subtree[res];

        solve(there,nxtsz,num+1);
    }

    return;
}

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;

    cin>>S+1;

    graph = vector<vector<int> > (n+1);
    ctree = vector<vector<int> > (n+1);

    for(int i=1;i<n;i++){
        cin>>x>>y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    solve(1,n,1);

    cout<<ans<<"\n";

    return 0;
}