4번 문제를 5시가 되기 직전에 해결했다. 사진은 7시 쯤 찍었다.

5번은 긁기는 쉬운데 만점을 받는 사람이 없길래 그냥 건드리지 않았다. 4번도 풀었고 ^__^

 

1번 : 원 안의 점 

naive 하게 $-R \le x, y \le R$인 점을 모두 시도하면 $\mathcal{O}(R^2)$ 풀이가 나온다. 

답을 $\mathcal{O}(R)$에 구하기 위해서는, $x$ 하나를 고정하고 가능한 $y$의 개수를 $\mathcal{O}(1)$에 구하면 된다.

$x^2+y^2 \le R^2-1 \iff -\sqrt{R^2-1-x^2} \le y \le \sqrt{R^2 -1-x^2}$임을 계산하면, 가능한 $y$의 개수가 $$2 \lfloor \sqrt{R^2 - 1 - x^2} \rfloor + 1$$임을 알 수 있다. 이는 sqrt 함수를 사용하거나 이분탐색을 해서 빠르게 계산할 수 있다. 

 

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
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
const ll mod = 1e9 + 7;
 
ll calc(ll x)
{
    ll lef=0, rig=1e9, best=0, mid;
    while(lef<=rig)
    {
        mid = (lef + rig) / 2;
        if(mid * mid <= x) 
        {
            best = mid;
            lef = mid + 1;
        }
        else rig = mid - 1;
    }
    return best;
}
 
void solve(void)
{
    ll R, ans=0cin >> R;
    for(ll i=-R+1 ; i<=R-1 ; i++)
        ans += 2 * calc(R * R - 1 - i * i) + 1;
    cout << ans << endl;
}
 
 
int main(void)
{
    fio; ll i, tc; cin >> tc;
    for(i=1 ; i<=tc ; i++
    {
        cout << "Case #" << i << endl;
        solve(); // endl in solve
    }
    return 0;
}
cs

 

2번 : 직8각형

점 $(x_1, y_1), \cdots (x_8, y_8)$이 있을 때, 적당한 $X, Y$를 골라서 이 점들을 $$(X, Y), (X, Y+K), (X+K, Y+2K), (X+2K, Y+2K)$$ $$(X+3K, Y+K), (X+3K, Y), (X+2K, Y-K), (X+K, Y-K)$$와 같도록 해야 한다. 각 8개의 점을 직8각형의 8개의 점에 대응시키는 방법에는 총 $8!$가지가 있다. 이러한 방법을 하나 고정시키고 생각하자.

 

예를 들어, $(x_1, y_1), \cdots , (x_8, y_8)$이 위 8개의 점과 순서대로 대응된다고 가정하자. 이 경우, 움직여야 하는 총 거리는 $$|x_1 - X| + |y_1 - Y| + |x_2 - X| + |y_2 - (Y+K)| + |x_3 - (X+K)| + |y_3 - (Y+2K)|$$ $$+|x_4 - (X+2K)| + |y_4 - (Y+2K)| + |x_5 - (X+3K)| + |y_5 - (Y+K)| + |x_6 - (X+3K)| + |y_6 - Y|$$ $$+|x_7 - (X+2K)| + |y_7 - (Y-K)| + |x_8 - (X+K)| + |y_8 - (Y-K)|$$가 되며, 우리의 목표는 이 식의 최솟값을 구하는 것이다.

첫 번째 관찰은 위 식에서 $X, Y$가 각각 독립적으로 나온다는 것이다. 위 식에서 $X$가 등장하는 부분만 살펴보면, $$|X-x_1| + |X-x_2| + |X - (x_3-K)| + |X - (x_4-2K)|$$ $$+ |X - (x_5-3K)| + |X - (x_6-3K)| + |X - (x_7 - 2K)| + |X - (x_8 -K)|$$ 두 번째 관찰은, $x_i$들과 $K$가 이미 알고 있는 값이므로, 이 식은 이미 알고 있는 값 $c_1, c_2, \cdots, c_8$에 대해 $$\sum_{i=1}^8 |X - c_i|$$ 형태로 쓸 수 있다는 것이다. 이 식은 $X$가 $c_i$들의 "중간"에 있을 때 최솟값을 가진다.

확인하고 싶다면, 위 식을 그래프로 그려보자. 또한, 이 때 최솟값은 $c_i$들 중 최대 4개에서 최소 4개를 뺀 값이 됨을 확인할 수 있다.

$Y$에 대한 부분도 이렇게 최솟값을 구할 수 있으며, 두 결과를 합치면 식의 최솟값을 구할 수 있다. 이를 $8!$번 반복하면 해결.

 

시간복잡도는 $n$이 점의 개수라고 하면, $\mathcal{O}(n! \cdot n \log n)$ 정도로 볼 수 있을 것이다.

 

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
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
const ll mod = 1e9 + 7;
 
pair<ll, ll> pts[8]; ll K;
ll x[8], y[8];
ll difx[8= {00123321};
ll dify[8= {012210-1-1};
 
void solve(void)
{
    ll i, ans=1e18cin >> K; 
    for(i=0 ; i<8 ; i++cin >> pts[i].first >> pts[i].second;
    sort(pts, pts+8);
    do
    {   
        for(i=0 ; i<8 ; i++) x[i] = pts[i].first - difx[i] * K;
        for(i=0 ; i<8 ; i++) y[i] = pts[i].second - dify[i] * K;
        sort(x, x+8); sort(y, y+8);
        ll cur = 0;
        for(i=4 ; i<8 ; i++) cur += (x[i] + y[i]);
        for(i=0 ; i<4 ; i++) cur -= (x[i] + y[i]);
        ans = min(ans, cur);
    } while(next_permutation(pts, pts+8));
    cout << ans << endl;
}
 
int main(void)
{
    fio; ll i, tc; cin >> tc;
    for(i=1 ; i<=tc ; i++
    {
        cout << "Case #" << i << endl;
        solve(); // endl in solve
    }
    return 0;
}
cs

 

3번 : 산탄총

정말 피곤한 문제였다. 진짜 부분합만 알면 풀 수 있는데, 깔끔하게 안 풀어서 그런지 계산이 너무 귀찮았다.

이제부터 모든 것을 수식으로 설명한다. 하지만 실제로 문제를 풀거나 이 풀이를 읽을 때는 그림을 그려가면서 생각하는 것이 좋을 것이다.

 

배열은 1-index를 사용하여, $1 \le i, j \le N$에 배열 $a$가 채워졌다고 생각하도록 하겠다.

 

우선, 목표로 하는 함수인 $$ \text{score}(Y, X) = \sum_{|y-Y| + |x-X| \le K-1} (K-|y-Y|-|x-X|) \cdot a[y][x]$$를 정의하면, 우리의 목표는 $\text{score}$의 최댓값을 찾는 것이다. 우선 $Y$ 또는 $X$가 $-K$ 미만이거나 $N+K$ 초과면, $\text{score}$ 함수가 $0$이 됨을 확인할 수 있다.

그러니 $-K \le X, Y \le N+K$인 경우만 계산하면 된다. 우리의 궁극적인 목표는 $\text{score}$ 함수를 이 범위 전체에 대해서 $\mathcal{O}((N+K)^2) = \mathcal{O}(N^2)$ 시간에 계산하는 것이다. 이를 위해서는 $\text{score}$ 함수가 $(Y, X)$가 한 칸 움직였을 때 어떻게 변화하는지 알아볼 필요가 있다. 

$$\text{score}(Y, X) - \text{score}(Y, X-1)$$ $$= \sum_{|y-Y| + |x-X| \le K-1} (K-|y-Y|-|x-X|) \cdot a[y][x] - \sum_{|y-Y| + |x-X+1| \le K-1} (K - |y-Y| - |x-X+1|) \cdot a[y][x]$$

이 값을 분석하는 가장 좋은 방법은 각 $(y, x)$에 대해 $a[y][x]$의 계수를 찾는 것이다. 그림을 그려 풀 때도 비슷하다.

 

우선 생각해보면 $|y-Y|+|x-X|$와 $|y-Y|+|x-(X-1)|$이 모두 $K$ 이하인 경우, $a[y][x]$의 계수는 $$|x-X+1| - |x-X|$$가 된다. 이 값은 $x \ge X$에서 $1$이고 $x \le X-1$에서 $-1$임을 알 수 있다. 

$|y-Y|+|x-X|$나 $|y-Y|+|x-(X-1)|$ 중 하나라도 $K+1$ 이상인 경우, 둘 다 $K$ 이상이 되어 계수는 $0$이다. 즉,

$$\text{score}(Y, X) - \text{score}(Y, X-1) = \sum_{|y-Y| + |x-X| \le K-1, x \ge X} a[y][x] - \sum_{|y-Y| + |x-X+1| \le K-1, x \le X-1} a[y][x] $$가 되고, 비슷한 원리로 계산하면 $$\text{score}(Y, X) - \text{score}(Y-1, X) = \sum_{|y-Y|+|x-X| \le K-1, y \ge Y} a[y][x] - \sum_{|y-Y+1|+|x-X| \le K-1,  y \le Y-1} a[y][x]$$를 얻는다. 그러니까 이제 필요한 것은 네 종류의 "삼각형 부분합"이며, 이들 역시 같은 방법으로 계산이 가능하다.

 

예를 들어, "1사분면에 대한 삼각형 부분합"을 $$Q1(Y, X) = \sum_{|y-Y| + |x-X| \le K-1, y \le Y, x \ge X} a[y][x]$$라 하자. 이 값을 계산하기 위하여, 다시 인접한 $Q1$ 값의 차이를 계산해보면, $$Q1(Y, X) - Q1(Y, X-1) = \sum_{|y-Y| + |x-X| \le K-1, y \le Y, x \ge X} a[y][x] - \sum_{|y-Y| + |x-X+1| \le K-1, y \le Y, x \ge X-1} a[y][x]$$인데, $a[y][x]$의 계수를 생각해보면 다음과 같은 결과를 얻을 수 있다. 그림을 그려서 생각하는 게 편하다.

  • $x \ge X, y \le Y$이고 $(Y-y) + (x-X) = |y-Y|+|x-X| = K-1$이면 계수가 $+1$
  • $x = X-1$이고 $Y-K+1 \le y \le Y$면 계수가 $-1$
  • 나머지 경우에 대해서는 전부 계수가 $0$

첫 번째 경우에 대한 합은 "대각선 부분합"이고, 두 번째 경우에 대한 합은 "일직선 부분합"이니, 전부 부분합 테크닉으로 빠르게 구할 수 있다.

그러니 $Q1(Y, X-1)$이 있으면 $Q1(Y, X)$를 구할 수 있고, 비슷한 계산으로 $Q1(Y-1, X)$이 있으면 $Q1(Y, X)$를 빠르게 구하는 식을 얻을 수 있다.

 

$Q1(-K, -K)$를 naive 하게 직접 구한 후 위 방법을 적용하면 모든 $Y, X$에 대해 $Q1(Y, X)$를 $\mathcal{O}(N^2)$에 구할 수 있다.

이를 각 4개의 사분면에 대해서 적용할 수 있고, 이제 $\text{score}$ 역시 전부 $\mathcal{O}(N^2)$에 구할 수 있다. 

 

당연하지만 이 문제에서는 index가 범위를 벗어나는 것에 대한 처리가 매우 귀찮고 중요하다.

 

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
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
const ll mod = 1e9 + 7;
 
ll K, N;
ll val[1811][1811];
ll DIAG1[1811][1811]; // NW SE
ll DIAG2[1811][1811]; // NE SW
ll WE[1811][1811];
ll NS[1811][1811];
ll CALC[1811][1811];
ll QUAD[4][1811][1811];
 
void rset(void)
{
    memset(val, 0sizeof(val));
    memset(DIAG1, 0sizeof(DIAG1));
    memset(DIAG2, 0sizeof(DIAG2));
    memset(WE, 0sizeof(WE));
    memset(NS, 0sizeof(NS));
    memset(CALC, 0sizeof(CALC));
    memset(QUAD, 0sizeof(QUAD));
}
 
ll NS_p(ll Y1, ll Y2, ll X)
{
    Y1 = min(Y1, N + 2 * K);
    Y2 = max(Y2, 0LL);
    return NS[Y1][X] - NS[Y2][X];
}
 
ll WE_p(ll Y, ll X1, ll X2)
{
    X1 = min(X1, N + 2 * K);
    X2 = max(X2, 0LL);
    return WE[Y][X1] - WE[Y][X2];
}
 
ll getdiag1(ll Y1, ll X1)
{
    if(Y1 < 0 || X1 < 0return 0;
    else if(Y1 <= N+2*&& X1 <= N+2*K) return DIAG1[Y1][X1];
    else
    {
        ll offset = max(Y1 - (N + 2 * K), X1 - (N + 2 * K));
        Y1 -= offset; X1 -= offset;
        if(Y1 < 0 || X1 < 0return 0;
        else return DIAG1[Y1][X1];
    }
}
 
ll DIAG1_p(ll Y1, ll X1, ll Y2, ll X2)
{
    return getdiag1(Y1, X1) - getdiag1(Y2, X2);
}
 
ll getdiag2(ll Y1, ll X1)
{
    if(Y1 < 0 || X1 > N + 2 * K) return 0;
    else if(Y1 <= N+2*&& X1 >= 0return DIAG2[Y1][X1];
    else 
    {
        ll offset = max(Y1 - (N + 2 * K), -X1);
        Y1 -= offset; X1 += offset;
        if(Y1 < 0 || X1 < 0 || X1 > N + 2 * K) return 0;
        else return DIAG2[Y1][X1];
    }
}
 
ll DIAG2_p(ll Y1, ll X1, ll Y2, ll X2)
{
    return getdiag2(Y1, X1) - getdiag2(Y2, X2);
}
 
ll getval(ll Y, ll X)
{
    if(X<=0 || X>N+2*|| Y<=0 || Y>N+2*K) return 0;
    return val[Y][X];
}
 
void finish_QUAD0(void)
{
    ll i, j;
    for(i=0 ; i<=K-1 && i<=1 ; i++)
        for(j=0 ; i+j<=K-1 ; j++)
            QUAD[0][1][1+= getval(1-i, 1+j);
    for(i=1 ; i<=N+2*K ; i++)
    {
        for(j=1 ; j<=N+2*K ; j++)
        {
            if(i == 1 && j == 1continue;
            if(j == 1// get from top
            {
                QUAD[0][i][j] = QUAD[0][i-1][j] 
                               + WE_p(i, j+K-1, j-1)
                               - DIAG1_p(i-1, j+K-1, i-K-1, j-1);
 
            }
            else // get from left
            {
                QUAD[0][i][j] = QUAD[0][i][j-1]
                               + DIAG1_p(i, j+K-1, i-K, j-1
                               - NS_p(i, i-K, j-1);
            }
        }
    }
}
 
void finish_QUAD1(void)
{
    ll i, j;
    for(i=0 ; i<=K-1 && i<=1 ; i++)
        for(j=0 ; i+j<=K-1 && j<=1; j++)
            QUAD[1][1][1+= getval(1-i, 1-j);
    for(i=1 ; i<=N+2*K ; i++)
    {
        for(j=1 ; j<=N+2*K ; j++)
        {
            if(i == 1 && j == 1continue;
            if(j == 1// get from top
            {
                QUAD[1][i][j] = QUAD[1][i-1][j]
                              + WE_p(i, j, j-K)
                              - DIAG2_p(i-1, j-K+1, i-K-1, j+1);
            }
            else // get from left
            {
                QUAD[1][i][j] = QUAD[1][i][j-1]
                              + NS_p(i, i-K, j)
                              - DIAG2_p(i, j-K, i-K, j);
            }
        }
    }
}
 
void finish_QUAD2(void)
{
    ll i, j;
    for(i=0 ; i<=K-1 ; i++)
        for(j=0 ; i+j<=K-1 && j<=1 ; j++)
            QUAD[2][1][1+= getval(1+i, 1-j);
    for(i=1 ; i<=N+2*K ; i++)
    {
        for(j=1 ; j<=N+2*K ; j++)
        {
            if(i == 1 && j == 1continue;
            if(j == 1// get from top
            {
                QUAD[2][i][j] = QUAD[2][i-1][j]
                              + DIAG1_p(i+K-1, j, i-1, j-K)
                              - WE_p(i-1, j, j-K);
            }
            else // get from left
            {
                QUAD[2][i][j] = QUAD[2][i][j-1]
                              + NS_p(i+K-1, i-1, j) 
                              - DIAG1_p(i+K-1, j-1, i-1, j-K-1);
            }
        }
    }
}
 
void finish_QUAD3(void)
{
    ll i, j;
    for(i=0 ; i<=K-1 ; i++)
        for(j=0 ; i+j<=K-1 ; j++)
            QUAD[3][1][1+= val[1+i][1+j];
    for(i=1 ; i<=N+2*K ; i++)
    {
        for(j=1 ; j<=N+2*K ; j++)
        {
            if(i == 1 && j == 1continue;
            if(j == 1// get from top
            {
                QUAD[3][i][j] = QUAD[3][i-1][j]
                              + DIAG2_p(i+K-1, j, i-1, j+K)
                              - WE_p(i-1, j+K-1, j-1);
            }
            else // get from left
            {
                QUAD[3][i][j] = QUAD[3][i][j-1]
                              + DIAG2_p(i+K-1, j, i-1, j+K)
                              - NS_p(i+K-1, i-1, j-1);
            }
        }
    }
}
 
void solve(void)
{
    ll i, j; rset(); cin >> N >> K;
    for(i=1 ; i<=N ; i++)
        for(j=1 ; j<=N ; j++)
             cin >> val[K+i][K+j];
    for(i=0 ; i<=N+2*K ; i++)
    {
        for(j=0 ; j<=N+2*K ; j++)
        {
            if(i!=0 && j!=0) DIAG1[i][j] = DIAG1[i-1][j-1+ val[i][j];
            if(i!=0) DIAG2[i][j] = DIAG2[i-1][j+1+ val[i][j];
            if(j!=0) WE[i][j] = WE[i][j-1+ val[i][j];
            if(i!=0) NS[i][j] = NS[i-1][j] + val[i][j];
        }
    }
    finish_QUAD0(); finish_QUAD1(); finish_QUAD2(); finish_QUAD3();
    for(i=1 ; i<=K ; i++)
    {
        for(j=1 ; j<=K ; j++)
        {
            ll dist = abs(i-1+ abs(j-1);
            if(dist <= K-1) CALC[1][1+= (K - dist) * val[i][j];
        }
    }
    for(i=1 ; i<=N+2*K ; i++)
    {
        for(j=1 ; j<=N+2*K ; j++)
        {
            if(i == 1 && j == 1continue;
            if(j == 1// get from top
            {
                CALC[i][j] = CALC[i-1][j];
                CALC[i][j] += (QUAD[2][i][j] + QUAD[3][i][j] - NS_p(i+K-1, i-1, j));
                CALC[i][j] -= (QUAD[0][i-1][j] + QUAD[1][i-1][j] - NS_p(i-1, i-K-1, j));
            }
            else // get from left 
            {
                CALC[i][j] = CALC[i][j-1];
                CALC[i][j] += (QUAD[0][i][j] + QUAD[3][i][j] - WE_p(i, j+K-1, j-1));
                CALC[i][j] -= (QUAD[1][i][j-1+ QUAD[2][i][j-1- WE_p(i, j-1, j-K-1));
            }
        }
    }
    ll ans = 0;
    for(i=1 ; i<=N+2*K ; i++)
        for(j=1 ; j<=N+2*K ; j++)
            ans = max(ans, CALC[i][j]);
    cout << ans << endl;
}
 
int main(void)
{
    fio; ll i, tc; cin >> tc;
    for(i=1 ; i<=tc ; i++
    {
        cout << "Case #" << i << endl;
        solve(); // endl in solve
    }
    return 0;
}
cs

 

4번 : 패턴 매칭

부분문제 2까지는 최근 IOI 선발고사에서 나온 문제와 같고, 이 아이디어를 확장하면 문제를 해결할 수 있다.

 

저 동치 조건을 깔끔하게 나타낼 방법을 찾는 것이 이 문제를 해결하는 핵심이다.

결론부터 말하자면, 각 문자열의 각 문자에 대해서 "마지막으로 그 문자가 나온 위치까지의 거리"를 생각하면 동치 조건이 깔끔해진다. 예를 들어, 

 

superguesser의 경우 순서대로 마지막으로 그 문자가 나온 위치까지 거리가 -1, -1, -1, -1, -1, -1, 5, 4, 8, 1, 3, 7가 된다.

abcdefbdaade도 역시 순서대로 마지막으로 그 문자가 나온 위치까지 거리가 -1, -1, -1, -1, -1, -1, 5, 4, 8, 1, 3, 7가 된다.

 

단, -1은 이전에 그 문자가 나오지 않았음을 의미한다.  

또한, 이 두 문자열은 동치임을 직접 확인할 수 있으며, 일반적으로도 이렇게 두 문자열의 동치 여부를 확인할 수 있음을 증명할 수 있다.

 

이제 가장 "자연스러운" 접근은, 문자열을 위와 같이 숫자 형태로 전환시킨 다음, KMP를 쓰는 것이다. 

이 접근은 다 좋은데, -1을 처리하는 것에 약간의 신경을 써야 한다. 예를 들어, KMP를 쓰면 기본적으로 하는 접근이 $[i-fail[i]+1, i]$가 전체 문자열의 prefix와 같다는 것이다. 여기서 다음 문자를 확인하여 이 prefix를 연장시킬 수 있는지 확인해야 한다. 만약 실제 prefix에서 $fail[i]$번째 문자에 대응되는 값이 -1이라면, 이는 이 문자가 prefix에서 지금까지 등장하지 않은 문자임을 의미한다. 이를 확인하기 위해서는 단순히 $i+1$번째 문자에 대응되는 값이 -1임을 확인하면 안되고, 그 값이 -1이거나 $fail[i]$를 초과하는지 확인해야 한다. 즉, KMP에서 지금 확인하고 있는 suffix의 범위를 넘어가는 경우를 역시 고려해주어야 한다.

 

여기까지 생각하면 KMP 코드를 거의 그대로 가져와서 부분문제 2까지 해결할 수 있다.

 

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
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
const ll mod = 1e9 + 7;
 
string s; ll N, K;
string pat[31111];
ll pogs[2222222];
ll fail[511], pog[511];
ll rec_s[26], rec_p[26];
 
void precompute(void)
{
    ll i;
    for(i=0 ; i<26 ; i++) rec_s[i] = -1;
    for(i=0 ; i<s.length() ; i++)
    {
        int cur = s[i] - 'a';
        if(rec_s[cur] == -1) pogs[i] = -1;
        else pogs[i] = i - rec_s[cur];
        rec_s[cur] = i;
    }
}
 
ll calc(ll idx)
{
    ll i, j=0
    for(i=0 ; i<26 ; i++) rec_p[i] = -1;
    memset(fail, 0sizeof(fail));
    for(i=0 ; i<pat[idx].length() ; i++)
    {   
        int cur = pat[idx][i] - 'a';
        if(rec_p[cur] == -1) pog[i] = -1;
        else pog[i] = i - rec_p[cur];
        rec_p[cur] = i;
    }
    for(i=1 ; i<pat[idx].length() ; i++)
    {
        while(1)
        {
            if(j == 0break;
            if(pog[i] == pog[j]) break;
            if(pog[j] == -1 && pog[i] > j) break;
            j = fail[j-1];
        }
        if((pog[i] == pog[j]) || (pog[j] == -1 && pog[i] > j)) fail[i]=++j;
    }
    ll ret=0; j=0;
    for(i=0 ; i<s.length() ; i++)
    {
        while(j>0 && !(pogs[i] == pog[j] || (pog[j] == -1 && pogs[i] > j))) j=fail[j-1];
        if((pogs[i] == pog[j]) || (pog[j] == -1 && pogs[i] > j))
        {
            if(j==pat[idx].length()-1) { ret++; j=fail[j]; }
            else j++;
        }
    }
    return ret;
}
 
void solve(void)
{
    cin >> N >> K; ll i, ans = 0cin >> s; precompute();
    for(i=1 ; i<=K ; i++cin >> pat[i];
    for(i=1 ; i<=K ; i++) ans += i * calc(i);
    cout << ans << endl;
}
 
int main(void)
{
    fio; ll i, tc; cin >> tc;
    for(i=1 ; i<=tc ; i++
    {
        cout << "Case #" << i << endl;
        solve(); // endl in solve
    }
    return 0;
}
cs

 

이제 패턴이 여러 개 존재하니, KMP를 Aho-Corasick으로 바꾸어주면 된다. Trie의 각 노드에는

  • 기본적인 정보인 failure link, output link, count, 끝 정점인지 여부 
  • 현재 보고 있는 문자열의 길이 (-1을 처리하기 위함이다)
  • 그리고 각 경우에 대응되는 다음 노드의 포인터

를 저장한다. 이때, 다음 노드를 확인하기 위해 사용하는 것은 알파벳 자체가 아니라 해당 알파벳의 마지막 등장 위치까지의 거리다. 

각 노드에 저장되어 있는 문자열의 길이 정보에 따라서, 내가 -1을 사용해야 하는지 실제 등장 위치까지의 거리를 사용해야 하는지가 달라진다.  

 

위 KMP 풀이와 Aho-Corasick 알고리즘을 잘 이해하고 있다면, 풀이를 변형하는 것은 어렵지 않다. 코드는 https://blog.myungwoo.kr/101를 참고했다. 

 

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
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
const ll mod = 1e9 + 7;
 
string s; ll N, K;
string pat[31111];
struct Trie
{
    map<ll, Trie*> S;
    Trie* fail;
    Trie* output;
    ll cur_len;
    ll count; bool is_end;
    Trie() { S.clear(); fail=nullptr; output=nullptr; count=0; cur_len=0; is_end=false; }
    ~Trie() { S.clear(); }
};
Trie* end_node[31111];
queue<Trie*> Q;
vector<Trie*> ord;
 
ll rec_p[26], rec_s[26];
ll pog[31111], pogs[2222222];
map<ll, Trie*>::iterator it;
 
void solve(void)
{
    ord.clear(); cin >> N >> K; ll i, j, ans = 0cin >> s;
    memset(pog, 0sizeof(pog));
    memset(pogs, 0sizeof(pogs));
    for(i=1 ; i<=K ; i++cin >> pat[i];
    Trie *root = new Trie;
    // Step 1 : Build the Trie
    for(i=1 ; i<=K ; i++)
    {
        Trie *now = root;
        for(j=0 ; j<26 ; j++) rec_p[j] = -1;
        for(j=0 ; j<pat[i].length() ; j++)
        {   
            int cur = pat[i][j] - 'a';
            if(rec_p[cur] == -1) pog[j] = -1;
            else pog[j] = j - rec_p[cur];
            rec_p[cur] = j;
        }
        for(j=0 ; j<pat[i].length() ; j++)
        {
            if(now->S.find(pog[j]) == now->S.end()) {
                now->S[pog[j]] = new Trie;
            }
            now->S[pog[j]]->cur_len = now->cur_len + 1;
            now = now->S[pog[j]];
        }
        now->is_end = true;
        end_node[i] = now;
    }
    // Queue Setup
    for(it = root->S.begin() ; it != root->S.end() ; it++) {
        it->second->fail = root;
        Q.push(it->second);
    }
    // Fail Setup
    while(!Q.empty())
    {
        Trie *cur = Q.front(); Q.pop();
        if(cur->is_end) cur->output = cur;
        else cur->output = cur->fail->output;
        for(it = cur->S.begin() ; it != cur->S.end() ; it++) {
            ll cur_step = it->first;
            Trie *nxt = it->second;
            nxt->fail = cur->fail;
            while(1)
            {
                if(nxt->fail == root) break;
                ll len = nxt->fail->cur_len;
                ll true_step = cur_step;
                if(true_step > len) true_step = -1;
                if(nxt->fail->S.find(true_step) != nxt->fail->S.end()) break;
                nxt->fail = nxt->fail->fail;
            }
            ll true_step = cur_step;
            ll len = nxt->fail->cur_len;
            if(true_step > len) true_step = -1;
            if(nxt->fail->S.find(true_step) != nxt->fail->S.end()) 
                nxt->fail = nxt->fail->S[true_step];
            Q.push(nxt);
        }
    }
    // start finding
    Trie *now = root;
    for(i=0 ; i<26 ; i++) rec_s[i] = -1;
    for(i=0 ; i<s.length() ; i++)
    {
        int cur = s[i] - 'a';
        if(rec_s[cur] == -1) pogs[i] = -1;
        else pogs[i] = i - rec_s[cur];
        rec_s[cur] = i;
    }
    for(i=0 ; i<s.length() ; i++)
    {
        ll cur_step = pogs[i];
        while(1)
        {
            if(now == root) break;
            ll true_step = cur_step;
            if(true_step > now->cur_len) true_step = -1;
            if(now->S.find(true_step) != now->S.end()) break;
            now = now->fail;
        }
        ll true_step = cur_step;
        if(true_step > now->cur_len) true_step = -1;
        if(now->S.find(true_step) != now->S.end()) now=now->S[true_step];
        if(now->output) now->output->count++;
    }
    // finish
    Q.push(root);
    while(!Q.empty())
    {
        Trie *cur=Q.front(); Q.pop();
        ord.push_back(cur);
        for(it = cur->S.begin() ; it != cur->S.end() ; it++) Q.push(it->second);
    }
    reverse(ord.begin(), ord.end());
    for(i=0 ; i<ord.size() ; i++)
        if(ord[i]->is_end && ord[i]->fail->output)
            ord[i]->fail->output->count+=ord[i]->count;
    for(i=1 ; i<=K ; i++) ans += i * end_node[i]->count;
    delete root;
    cout << ans << endl;
}
 
int main(void)
{
    fio; ll i, tc; cin >> tc;
    for(i=1 ; i<=tc ; i++
    {
        cout << "Case #" << i << endl;
        solve(); // endl in solve
    }
    return 0;
}
cs

 

'PS > 대회 후기' 카테고리의 다른 글

SCPC 2021 2차 예선 풀이  (1) 2021.08.07
SCPC 2021 1차 예선 풀이  (0) 2021.07.16
ACM-ICPC Seoul Regional 2020  (0) 2020.11.20
SCPC 2020 본선 후기  (5) 2020.11.09
ACM-ICPC Seoul Regional Preliminary 2020  (0) 2020.10.19
SCPC 2020 2차 예선 풀이  (1) 2020.09.05
  1. zxcvber 2021.08.15 15:21 신고

    대회는 안쳤지만... 정말 존경스럽습니다...

대충 1시간 30분 정도 쓴 것 같다.

 

1번. 친구들

친구 관계가 일부 주어졌고, 친구의 친구 역시 친구로 간주할 때 "친구 관계인 maximal 그룹"의 개수를 구하는 문제다.

이는 사람을 정점으로, 친구 관계를 간선으로 볼 때 연결 컴포넌트의 개수를 구하는 문제와 같다. disjoint set 자료구조로 쉽게 해결할 수 있다.

 

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
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
const ll mod = 1e9 + 7;
 
int n;
int d[111111];
int par[111111];
 
int find(int x)
{
    if(par[x] == x) return x;
    return par[x] = find(par[x]);
}
 
void unite(int u, int v)
{
    u = find(u);
    v = find(v);
    if(u == v) return;
    par[u] = v;
}
 
void solve(void)
{
    int i, ans = 0cin >> n;
    for(i=1 ; i<=n ; i++cin >> d[i];
    for(i=1 ; i<=n ; i++) par[i] = i;
    for(i=1 ; i<=n ; i++)
        if(i+d[i]<=n) unite(i, i+d[i]);
    for(i=1 ; i<=n ; i++if(i == find(i)) ans++;
    cout << ans;
}
 
int main(void)
{
    fio; int tc; cin >> tc;
    for(int i=1 ; i<=tc ; i++
    {
        cout << "Case #" << i << endl;
        solve(); cout << endl;
    }
    return 0;
}
cs

 

2번. 이진수

$b_i = a_{i-t} | a_{i+t}$로 정의된 bit string $b$가 주어졌을 때, 사전순으로 가장 앞선 $a$를 구하는 문제다.

단, index가 가능한 범위 밖인 경우 값은 $0$이라고 생각하도록 한다. 또한, 조건을 만족하는 $a$가 존재함은 보장된다. 

 

먼저 $b_i = 0$이면 $a_{i-t} = a_{i+t} = 0$임이 강제되며, 이렇게 둘 경우 $b_i = 0$ 역시 만족함을 알 수 있다. 

이에 해당되는 $a$의 bit에 0을 넣는 것을 확정하고 나면, 이제 $b_i = 1$ 형태의 조건들만 남았다. 

이들은 결국 $a$의 두 bit 중 적어도 하나가 1이라는 의미고, 이는 직관적으로 봤을 때 1을 더 넣으면 넣을수록 만족하기 쉬운 조건이다.

그러니, 앞서 0으로 확정된 bit가 아닌 임의의 bit에 대해서는 그냥 1로 두면 조건을 만족하는 $a$가 될 것이다.

 

이제 문제는 사전순으로 가장 앞선 $a$를 구하는 건데, 이런 문제가 그렇듯 앞부터 보면서 0을 넣을 수 있는지 판별하면 된다.

$a_i = 0$이 가능한지 고려해보자. 먼저 $a_i = 0$이 앞서 확정되었다면 굳이 고려를 할 필요도 없다.

만약 $i-t$가 범위에 있고 $b_{i-t} = 1$이라면, $a_{i-2t}$ 또는 $a_i$가 $1$이 되어야 한다. $a_{i-2t}=0$이라면, 여기서 $a_i = 1$이 강제된다. 

만약 $i+t$가 범위에 있고 $b_{i+t}=1$이라면, $a_i$ 또는 $a_{i+2t}$가 $1$이 되어야 한다. $a_{i+2t}$가 이미 $0$으로 확정되었다면, 여기서 $a_i = 1$이 강제된다.

이를 제외한 경우에서는, $a_i = 0$을 해도 문제가 되지 않는다. $a_i$가 영향을 주는 $b$의 값은 $b_{i-t}$, $b_{i+t}$이며, 이들의 값을 $a_i = 0$으로 두면서도 정확하게 맞춰줄 수 있기 때문이다. 특히, 마음에 걸릴 수 있는 유일한 부분이 $a_i = 0$으로 두면서 후에 $a_{i+2t}$를 $1$로 둔 것인데, 애초에

  • $a_i = 1$로 두면 무조건 $a_i = 0$으로 두는 것보다 사전순으로 뒤고, 그러니 $a_i = 0$인게 이득이고
  • $a_{i+2t}$는 확정되지 않은 bit이므로 $a_{i+2t} = 1$으로 두었다고 해서 조건을 만족하는 게 "어려워지지 않는다"

애초에 이 경우에는 $a_i = 0$으로 두고 확정된 bit를 제외한 뒤의 모든 bit를 1로 두면 조건을 만족하게 되어있다.

어쨌든 이런 식으로 bit를 계산하면 $\mathcal{O}(n)$에 모든 계산을 할 수 있다. 2번 문제인 것 치고는 약간 까다로웠다. 

 

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
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
const ll mod = 1e9 + 7;
 
// b[i] = a[i-t] | a[i+t]
 
int n, t, a[55555], b[55555];
string s;
 
void solve(void)
{
    int i; cin >> n >> t >> s;
    for(i=1 ; i<=n ; i++) b[i] = s[i-1- '0';
    for(i=1 ; i<=n ; i++) a[i] = -1;
    for(i=1 ; i<=n ; i++)
    {
        if(b[i] == 0)
        {
            if(i+t<=n) a[i+t] = 0;
            if(i-t>=1) a[i-t] = 0;
        }
    }
    for(i=1 ; i<=n ; i++)
    {
        if(a[i] != -1continue;
        if(i-t>=1 && (i<=2*|| a[i-2*t] == 0)) a[i] = 1;
        else if(i+t<=&& (i+2*t>|| a[i+2*t]==0)) a[i] = 1;
        else a[i] = 0;
    }
    for(i=1 ; i<=n ; i++cout << a[i];
}
 
int main(void)
{
    fio; int tc; cin >> tc;
    for(int i=1 ; i<=tc ; i++
    {
        cout << "Case #" << i << endl;
        solve(); cout << endl;
    }
    return 0;
}
cs

 

3번. No Cycle

사이클이 생기지 않도록 간선의 방향을 결정하는데, 사전순 조건이 있다. 즉, 앞쪽에서 입력받은 간선들은 최대한 입력받은 순서를 유지하도록 해야한다. 

이 문제 역시 사전순 문제에서 항상 등장하는 방법인, 앞부터 보면서 답을 맞춰나가는 방법을 사용한다. 결국 우리가 풀어야하는 문제는 

  • 방향 그래프 $G$와 지금 당장 방향을 정해야 하는 간선 $e$, 그리고 뒤에 추가할 무방향 간선의 배열 $E$가 주어져있다.
  • $e$를 입력받은 순서로 방향을 줄 때, $E$의 간선들의 방향을 잘 설정하여 $e, E$를 전부 추가한 뒤에도 그래프에 사이클이 없도록 할 수 있는가? 

이 문제를 해결할 수 있다면, 본 문제 역시 위 문제를 각 간선에 대하여 해결하는 것을 반복하여 해결할 수 있다.

즉, 입력으로 방향 그래프 $G$와 무방향 간선 $e_1, e_2, \cdots, e_k$가 들어온다면,

  • $G, e_1, [e_2, \cdots, e_k]$에 대해 문제를 해결. 그 후 결정된 방향에 맞게 $G_1 \gets G + \vec{e_1}$.
  • $G_1, e_2, [e_3, \cdots , e_k]$에 대해 문제를 해결. 그 후 결정된 방향에 맞게 $G_2 \gets G + \vec{e_2}$.
  • 반복하면서 최종적으로 $G_{k-1}, e_k, []$에 대하여 문제를 해결하는 것으로 마무리.

물론, 위 과정에서 각 간선은 그리디하게 가능하면 입력 순서대로 방향을 잡아야 한다. 

 

Claim : $G$가 DAG고, $E$가 추가할 무방향 간선들이라고 하자. $E$의 간선들의 방향을 잘 정하여 $E$를 추가한 뒤에도 $G$가 DAG이도록 할 수 있다.

Proof of Claim : $G$를 위상정렬하고, 위상정렬 순서로 방향을 주면 된다. 증명 끝.

 

결국 위에서 논의한 $G, e, E$에 대한 문제는 사실 $G + e$가 DAG인지, 즉 사이클이 없는지 판별하는 문제와 같다.

$G$ 역시 DAG이므로, $G + e$에 사이클이 있는지 판별하는 문제는 $G$에 특정 경로가 존재하는지 판별하는 문제와 같다.

즉, $e$가 $u$에서 $v$로 가는 간선이라면, $G + e$의 사이클 존재 유무는 $G$에서 $v$에서 $u$로 가는 경로의 존재 여부와 같다.

 

결론적으로, 간선 $u \rightarrow v$가 주어졌다면 현재 그래프에서 $v \rightarrow u$ 경로가 존재하는지 보고,

  • 존재한다면 순서를 뒤집어서 $v \rightarrow u$로 두고 이 간선을 그래프에 추가
  • 그렇지 않다면 순서를 그대로 두고 간선을 그래프에 추가

하는 것을 반복하면 된다. 대충 $\mathcal{O}(K(N+M+K))$ 정도에 돌 것이다. 아마 자료구조 빡세게 쓰면 subquadratic 될듯? 아니면 말고

 

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
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
const ll mod = 1e9 + 7;
 
vector<int> edge[511];
pair<intint> E[4333];
queue<int> Q;
int vis[555];
int n, m, k;
 
int work(int u, int v)
{
    int i; for(i=1 ; i<=n ; i++) vis[i] = 0;
    vis[v] = 1; Q.push(v); 
    while(!Q.empty())
    {
        int c = Q.front(); Q.pop();
        for(i=0 ; i<edge[c].size() ; i++)
        {
            if(vis[edge[c][i]] == 0)
            {
                vis[edge[c][i]] = 1;
                Q.push(edge[c][i]);
            }
        }
    }
    if(vis[u]) return 1;
    return 0;
}
 
void solve(void)
{
    int i, u, v;
    cin >> n >> m >> k;
    for(i=1 ; i<=n ; i++) edge[i].clear();
    for(i=1 ; i<=m ; i++)
    {
        cin >> u >> v;
        edge[u].push_back(v);
    }
    for(i=1 ; i<=k ; i++)
    {
        cin >> u >> v;
        E[i] = make_pair(u, v);
    }
    for(i=1 ; i<=k ; i++)
    {
        u = E[i].first;
        v = E[i].second;
        int res = work(u, v);
        cout << res;
        if(res == 0) edge[u].push_back(v);
        else edge[v].push_back(u);
    }
}
 
 
int main(void)
{
    fio; int tc; cin >> tc;
    for(int i=1 ; i<=tc ; i++
    {
        cout << "Case #" << i << endl;
        solve(); cout << endl;
    }
    return 0;
}
cs

 

4번. 예약 시스템

$2 \times m$ 직사각형에 사람들을 배치한다. 사람들은 총 $n$개의 그룹으로 나뉘어 있으며, 각 그룹에는 5명 이상이 있다. 

각 사람들은 스트레스 지수 $w$를 갖는데, 자신의 이웃에 자신과 다른 그룹에 속하는 사람이 있다면 그런 사람의 수와 $w$의 곱만큼 스트레스가 오른다.

우리의 목표는 스트레스 지수의 총합을 최소화하는 것이다. 제한은 전체적으로 큰 편이다. 

 

동적계획법을 쓰기 어렵게 생긴 제한인만큼, 한방에 문제를 푸는 방법이 필요해보인다. 

 

그룹 $S$ 하나를 고정해보자. $S$의 사람들이 스트레스를 느낄 때는, $S$와 $S^C$가 한 변을 공유할 때다.

그러니까 $S$의 둘레의 (단, 직사각형의 둘레는 제외한다) 길이가 길면 길수록 $S$ 전체의 스트레스가 커진다.

이는 $S$의 사람들이 뭉쳐있어야 스트레스가 적을 것 같다는 직관과도 거의 같은 결과다. 

 

"$S$의 둘레"를 생각해보면, 전체 직사각형의 길이 2의 세로변을 잠깐 무시하고 생각해보면

  • $S$의 크기가 짝수인 경우, 직사각형 형태를 이루도록 하면 둘레가 4가 된다.
  • 특히, 이 경우 $S$에서 서로 다른 4명의 사람들이 정확히 $S^C$의 한 사람과 만나게 된다. 이 사람들은 스트레스 지수가 작을수록 좋다.
  • $S$의 크기가 홀수인 경우, 직사각형에 하나 튀어나온 형태를 만들면 둘레가 5가 된다.
  • 특히, 이 경우 $S$에서 서로 다른 4명의 사람들이 $S^C$의 사람과 만나게 된다. 4명 중 정확히 한 명은 $S^C$를 두 명 만나고, 나머지는 한 명 만난다.
  • 물론, 두 명 만나는 사람의 스트레스 지수가 가장 작아야하며, 나머지의 스트레스 지수 역시 작을수록 좋다.

그리고 조금 열심히 생각해보면 이게 진짜 최적임을 납득할 수 있다. 또한, 홀수 크기의 그룹이 짝수개 존재하므로, 홀수 크기의 그룹끼리 서로 맞닿아 직사각형을 이루도록 하면 배치 역시 어렵지 않다. 이제 문제는 길이 2의 세로변을 처리하는 것이다. 길이 2의 세로변에 걸쳐서 $S$를 배치한다면, $S$에서 스트레스를 받는 4명 중 2명은 (이들은 4명 중에서 스트레스가 많은 두 명일 것이다) 전체 직사각형의 세로변의 도움을 받아 스트레스를 받지 않아도 된다. 

 

단순하게 생각하면, 여기서도 "가장 이득을 보는 그룹"을 양쪽 끝에 배치하여 세로변의 도움을 받을 수 있도록 하면 된다.

그런데 이게 이렇게 단순하지는 않은 게, 배치를 양쪽 끝에 하면 앞서 언급한 최적의 배치를 만드는 것이 어려울 수 있기 때문이다.

홀수 크기의 그룹이 정확히 2개 있고, 짝수 크기의 그룹이 여러 개 있다고 하자. 만약 홀수 크기의 그룹 2개가 양쪽 끝에 놓인다면, 짝수 크기 그룹을 직사각형 형태로 사용할 수 없고, 직사각형에서 양쪽에 한 개씩 튀어나온 형태로 사용해야 한다. 이때 짝수 크기 그룹에서 희생을 더 해야한다. 나머지 경우에서는 어떤 크기의 그룹을 양쪽에 배치해도, 우리가 생각하는 "최적의 배치"가 (직사각형 최대한 사용, 홀수 크기 2개 직사각형으로 만들기) 가능하다. 이제 열심히 케이스 분류.

 

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
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
const ll mod = 1e9 + 7;
 
 
ll n, m;
vector<ll> even_save;
vector<ll> odd_save;
 
void solve(void)
{
    int i, j; 
    ll sz, val, ans=0, subt=0, odd=0, even=0, saved, ex = 0
    cin >> n >> m;
    vector<ll> cc;
    for(i=1 ; i<=n ; i++)
    {  
        cin >> sz; cc.clear(); cc.resize(sz);
        for(j=0 ; j<sz ; j++cin >> cc[j];
        sort(cc.begin(), cc.end());
        if(!(sz & 1))
        {
            val = cc[0+ cc[1+ cc[2+ cc[3];
            saved = cc[2+ cc[3];
            ex += cc[0+ cc[1];
            ans += val; even++;
            even_save.push_back(saved);
        }
        else
        {
             val = 2 * cc[0+ cc[1+ cc[2+ cc[3];
            saved = cc[2+ cc[3]; 
            ans += val; odd++
            odd_save.push_back(saved);   
        }
    }
    sort(even_save.begin(), even_save.end());
    reverse(even_save.begin(), even_save.end());
    sort(odd_save.begin(), odd_save.end());
    reverse(odd_save.begin(), odd_save.end());
    if(even >= 2) subt = max(subt, even_save[0+ even_save[1]);
    if(even >= 1 && odd >= 1) subt = max(subt, even_save[0+ odd_save[0]);
    if(odd >= 2 && (odd >= 4 || n == 2)) subt = max(subt, odd_save[0+ odd_save[1]);
    if(odd == 2 && n >= 3)
        subt = max(subt, odd_save[0+ odd_save[1- ex);
    even_save.clear(); odd_save.clear();
    cout << ans - subt;
}
 
int main(void)
{
    fio; int tc; cin >> tc;
    for(int i=1 ; i<=tc ; i++
    {
        cout << "Case #" << i << endl;
        solve(); cout << endl;
    }
    return 0;
}
cs

 

5번. 차이

주어진 조건을 두 변수 사이의 간선이라고 보면, 연결 컴포넌트에 안에서는 모든 차이 계산이 가능하다. 

문제가 되는 것은 사이클, 특히 한바퀴 돌았는데 합이 0이 되지 않는 사이클이다. 이 경우, 사이클에 도달할 수 있는 모든 정점들은 모순된 상태가 된다.

 

그러니, disjoint set 자료구조를 가져왔을 때 대강

  • 두 정점이 같은 disjoint set에 속하지 않으면 Not Connected
  • 두 정점이 같은 disjoint set에 속하는데 여기에 모순된 cycle이 있으면 Conflict
  • 두 정점이 같은 disjoint set에 속하고 모순도 없으면 계산이 가능

함을 알 수 있다. 연결관계 자체만 봤을 때 disjoint set은 자명하고, 모순을 찾거나 계산을 하는 것이 문제다.

 

계산을 하기 위해서, 각 disjoint set의 대표 노드를 하나 두고 각 원소가 그 대표 노드의 값보다 얼마나 큰지 저장한다. 

원소들 사이의 차이는 알지만 원소 자체의 값은 모르니, 대표 노드의 값을 하나의 변수로 보고 차이만 저장하자는 의미다. 

 

이제 간선, 즉 하나의 등식이 추가되었다고 가정하자. 

  • 만약 두 정점이 같은 disjoint set에 있다면, 모순이 있는지 바로 확인할 수 있다. 저장된 값의 차이가 입력된 값과 다르면 모순이다.
  • 두 정점이 다른 disjoint set에 있다면, 이번에 추가된 등식은 두 disjoint set의 대표 노드 값 사이의 차이를 제공하는 정보가 된다. 이 경우, 두 disjoint set 중 하나의 대표를 전체의 새로운 대표로 정한다. 그 후, 흡수되는 집합의 각 원소들에 대해서 새로운 대표의 값과의 차이를 계산해야 한다. 이는 새로 얻어진 등식을 활용하여 할 수 있을 것이다. 물론, 두 disjoint set 중 이미 모순된 집합이 있다면 새로운 집합 역시 모순이 있다. 

두 disjoint set을 합치는 과정에서 걸리는 시간이 흡수되는 집합의 크기에 비례함을 알 수 있다. 그러므로, 작은 집합을 큰 집합에 흡수시키는 small-to-large 알고리즘을 사용하면 빠른 시간에 문제를 해결할 수 있다. 또한, 각 집합을 std::set 자료구조로 저장해야 집합의 순회가 쉽다. 

 

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
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
const ll mod = 1e9 + 7;
 
ll ans[111111];
int par[111111];
int sz[111111];
int doom[111111];
set<int> idx[111111];
set<int>::iterator it;
ll n, k;
 
int find(int x)
{
    if(par[x] == x) return x;
    return par[x] = find(par[x]);
}
 
void unite(int uu, int vv, int u, int v, ll val)
{
    if(sz[uu] < sz[vv])
    {
        swap(uu, vv);
        swap(u, v);
        val = -val;
    }
    sz[uu] += sz[vv];
    doom[uu] |= doom[vv];
    ll dif = -val - ans[v] + ans[u];
    for(it = idx[vv].begin() ; it != idx[vv].end() ; it++)
    {
        int loc = (*it);
        ans[loc] += dif;
        par[loc] = uu;
        idx[uu].insert(loc);
    }
    idx[vv].clear();
}
 
void solve(void)
{
    int i, whi, u, v, uu, vv; ll val;
    cin >> n >> k;
    for(i=1 ; i<=n ; i++) idx[i].clear();
    for(i=1 ; i<=n ; i++) ans[i] = 0, par[i] = i, sz[i] = 1, doom[i] = 0;
    for(i=1 ; i<=n ; i++) idx[i].insert(i);
    for(i=1 ; i<=k ; i++)
    {
        cin >> whi >> u >> v;
        if(whi == 1)
        {
            cin >> val;
            uu = find(u);
            vv = find(v);
            if(uu == vv && ans[u] - ans[v] != val) doom[uu] = 1;
            if(uu != vv) unite(uu, vv, u, v, val);
        }
        else if(whi == 2)
        {
            uu = find(u);
            vv = find(v);
            if(uu != vv) cout << "NC\n";
            if(uu == vv && doom[uu] == 1cout << "CF\n";
            if(uu == vv && doom[uu] == 0cout << ans[u] - ans[v] << "\n";
        }
    }
}
 
int main(void)
{
    fio; int tc; cin >> tc;
    for(int i=1 ; i<=tc ; i++
    {
        cout << "Case #" << i << endl;
        solve(); cout << endl;
    }
    return 0;
}
cs

'PS > 대회 후기' 카테고리의 다른 글

SCPC 2021 2차 예선 풀이  (1) 2021.08.07
SCPC 2021 1차 예선 풀이  (0) 2021.07.16
ACM-ICPC Seoul Regional 2020  (0) 2020.11.20
SCPC 2020 본선 후기  (5) 2020.11.09
ACM-ICPC Seoul Regional Preliminary 2020  (0) 2020.10.19
SCPC 2020 2차 예선 풀이  (1) 2020.09.05



그래도 후기를 쓰기는 해야 할 것 같아서 ㅋㅋㅋㅋㅋ 아쉽지만 작년에 비해서 좋은 결과가 나오지는 못했다. 이유는

  • 작년처럼 팀연습을 10번 이상 열심히 굴리지를 않았음 (올해 팀연습 0회)
  • 팀들이 작년보다 전반적으로 강해지고 센 팀들도 더 등장함
  • 일단 내가 작년에 비해서 간절함이 없었음 (애초에 작년에 뽑은 성과가 너무 좋았음) 

그래서 솔직히 결과에 아쉬움이 있어도 "이거 이상을 바라면 그건 그거대로 양심 X"라고 생각하고 있다.

아쉽다고 쳐도 9등이면 동상이고 이정도면 꽤 깔끔한 CP 대회 마무리 아닐까 싶기도 하고 ^__^ 

  • 열었더니 B가 쉬워서 빠르게 풀었음
  • A가 풀이 자체는 쉽다는 콜이 나옴. C 문제 해석에서 약간의 뇌절
  • E가 풀만하다는 콜과 G도 쉽다는 콜이 나옴. G에서 함정 빠짐
  • E 맞추고 G는 계속 맞왜틀. J 풀이 나옴. H가 simple FFT인거 보고 바로 구현, AC
  • C도 풀이 나오고 L 준비 시작. J 짜서 AC. G 다른 풀이도 짜봤는데 또 틀림.
  • G 함정 발견 및 C 구현 후 C, G 모두 AC. L은 DnC 콜이 나왔는데 틀리는 중.
  • L DM 돌리면서 틀린 이유 발견. Money For Nothing 생각하면서 풀이 고쳐서 맞음
  • 이제 junie가 A 구현하면서 다른 풀 거 찾아 떠남. I 보는게 맞는 판단인데 F가 할만해보여서 (ㅋㅋ) 시작
  • F 문제 잘못 이해해서 SCC 문제인줄 알았음 ㅋㅋ
  • junie가 A를 개고통받으면서 결국 AC 성공. 8솔해서 대충 이정도면 그래도 나쁘지 않다고 생각했음
  • F 예제 만들어보다가 결국 문제 이해를 못해먹겠다는 결론을 얻고 그대로 사망

이제 내년부터 ICPC 판 재밌어질텐데 팝콘각이나 열심히 재야겟다 ^____^

'PS > 대회 후기' 카테고리의 다른 글

SCPC 2021 2차 예선 풀이  (1) 2021.08.07
SCPC 2021 1차 예선 풀이  (0) 2021.07.16
ACM-ICPC Seoul Regional 2020  (0) 2020.11.20
SCPC 2020 본선 후기  (5) 2020.11.09
ACM-ICPC Seoul Regional Preliminary 2020  (0) 2020.10.19
SCPC 2020 2차 예선 풀이  (1) 2020.09.05




2등상을 받았다. 실제 실력에 비해 너무 높은 상이다.


UPD: 상금과 트로피까지 전달 받았다. 이제 수상 소감이 올라오면 끝인데 얼굴 팔릴 생각에 걱정이다 ㅜㅜ

UPD: 수상 소감까지 올라왔습니다. 얼굴도 팔렸네요 ㅋㅋ;


대회 과정

  • 1번 열었더니 쉬워서 빠르게 풀었다. 새로고침하니 퍼솔 같아서 기분이 좋았음 ^~^
  • 2번 열고 일단 SCC를 짤 줄 알면 $\mathcal{O}(m^2)$이 뚝딱임을 파악했다
  • 그런데 뇌절해서 그 풀이가 $\mathcal{O}(nm)$인 것으로 착각을 했다.
  • 아무튼 $\mathcal{O}(m^2)$ 풀이를 짜서 긁으려고 했는데 틀리더라. 멘붕 옴
  • 나중에 내 풀이가 $\mathcal{O}(nm)$이 아님을 깨달았다. 그래서 목표를 $\mathcal{O}(nm)$ 풀이 찾는 거로 잡았다.
  • 그러다가 문제에 오류가 있다는 공지를 받고, $\mathcal{O}(nm)$ 풀이 찾기에 착수했다.
  • 풀이 자체는 빠르게 나왔는데, 2번 문제치고 너무 복잡해서 뇌절이었나 걱정했다.
  • 그런데 2번 데이터가 수정된 이후에도 만점자가 4명 뿐이더라. 시간이 꽤 지난 것 치고 적은 수였다.
  • 그래서 맞는 풀이라는 확신을 할 수 있었고. 빠르게 짜서 바로 AC. 5번째 솔브로 기억한다. 이때가 1시간 정도 지났을 때.
  • 3번을 열었는데 일단 문자열에다가 드럽게 복잡한 것 같아서 일단 걸렀다. 전날에 연습을 좀 했는데 힘겨워서 ㅋㅋ
  • 그래도 3번은 풀어야 한다고 생각을 했고, 그 전에 4, 5번에서 빠르게 긁을 수 있는 것을 긁어오는 게 좋다고 판단했다.
  • 4번을 열었는데, 일단 마음 속으로 $\mathcal{O}(n^3 \log n \log MAX)$ 쯤 되는 풀이가 나왔다. 4-2까지 긁힐 것으로 예상했다.
  • 짜는 것도 별로 어렵지 않아서 빠르게 짰는데, 예제 1이 안나오네? 사실 상당히 큰 가정을 기반으로 한 풀이였다.
  • 예제가 안 나온다는 것은 가정이 틀렸다는 거고, 결국 간단하게 고치는 것 자체가 쉽지 않다는 것이다. 똑떨...
  • 5번을 열었더니 뭔 이상한 트리가 튀어나와서 바로 걸렀다. 결국 소득 없이 3번으로 돌아왔다.
  • 3번의 풀이 자체는 스트링 티피컬 짬뽕 국밥 든든 그 자체여서 빠르게 찾을 수 있었다. 문자열 관련 대비도 꽤 했고.
  • 그런데 아무리 생각해도 코드가 300줄 뽑히게 생겨서 마음을 굳게 먹어야 했다. 다행히 이때도 2번 만점자 수가 20명인가 그랬다.
  • 3번을 풀면 매우 큰 상을 받을 가능성이 높다고 생각해서, 뇌절하지 말자고 생각하고 짜기 시작했다
  • 대충 한 파트 짜고 -> 스코어보드 확인하면서 안도하고 -> 한 파트 짜고 -> 안도하고를 반복
  • 다 짰더니 에러가 조금 났는데, 인덱스 실수 하나여서 금방 고쳤다. 예제 나와서 제출했더니 한 방에 맞더라 ㅋㅋ
  • 이때가 4시 15분. (3시간 15분 지났을 때) 이제 긁을 것을 찾아서 떠났고 5-1이 긁기 쉽다는 결론을 얻었다.
  • 사실 긁기 별로 안 어려운데, 뇌가 극도의 흥분상태여서 뇌절도 꽤 해서 40분 정도 걸렸다. 이때가 5시.
  • 4번을 긁으면 진짜 2등상에 못 박는 느낌이어서 무리를 좀 했다. 뚫으려고 별 짓을 다하다가 사망하고 패배를 인정했다. 


문제 풀이


1. 더도 말고 덜도 말고


매우 쉬운 문제. 백준에도 비슷한 문제가 많을 것으로 생각한다. std::map 사용하면 뚝딱.


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
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef long long int ll;
typedef long double ldb;
mt19937 rng(4672627);
 
ll n, k, ans;
map<ll, ll> M;
 
void solve(void)
{
    ans=0; ll i, tot=0, x; cin>>n>>k;
    M.clear(); M[0]++;
    for(i=1 ; i<=n ; i++)
    {
        cin>>x; tot+=x;
        ans+=M[tot-k];
        M[tot]++;
    }
    cout<<ans<<"\n";
}
 
int main(void)
{
    fio; int i, tc;
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    cin>>tc;
    for(i=1 ; i<=tc ; i++)
    {
        cout<<"Case #"<<i<<"\n";
        solve(); // reset here
    }
    return 0;
}
cs


2. 영원한 휴가


작년 2번에 비해서 상당히 난이도가 올라간 문제. solved.ac 기준 플레 1 ~ 다이아 5 정도라고 개인적으로 생각한다.

$\mathcal{O}(m^2)$ 풀이는 간단한데, 그냥 SCC를 모든 경우에 대해서 다 구해주면 된다. 이러면 섭테 2까지 긁힌다.

본 문제를 해결하려면 SCC를 압축하여 DAG를 만드는 과정을 생각할 필요가 있다. 이제 기존 간선 $u \rightarrow v$를 뒤집었다고 생각하자.

  • $u, v$가 같은 SCC에 포함되었다면, 그 간선을 뒤집어서 SCC 크기가 증가하지는 않을 것이다. 그러니 무시해도 된다.
  • $u, v$가 다른 SCC에 포함되었다면, DAG 상에서 $u$의 SCC에서 $v$의 SCC로 가는 간선이 있다는 것이다.
  • 만약 이 간선을 뒤집는다면, 어떻게 될까? 만약 해당 간선이 $u$의 SCC에서 $v$의 SCC로 가는 유일한 경로라면, 무시해도 된다.
  • 하지만 $u$의 SCC에서 $v$의 SCC로 가는 경로가 2개 이상이라면, $u$의 SCC와 $v$의 SCC "사이"에 있는 모든 SCC가 묶인다.
  • 여기서 "사이"에 있다는 것은, $u$의 SCC -> ??? -> $v$의 SCC 형태의 경로가 존재하는 ??? 들을 의미한다.

이제 문제를 해결할 수 있다. SCC 압축 DAG를 만든 후, $dp[u][v]$를 $u$번 SCC에서 $v$번 SCC로 가는 경로의 개수가 0개인지, 1개인지, 아니면 2개 이상인지로 정의하자. 이 값은 DAG에서 위상정렬 DP를 하듯이 계산할 수 있으며, 시간복잡도는 $\mathcal{O}(nm)$이다. 이 값을 잘 계산해놓으면 위 관찰을 통해서 답을 얻는 것 역시 쉽게 할 수 있다. 구현을 효율적으로 해야 AC를 얻는다는 말이 있으니, 잘 구현해야한다. $dp$ 계산에서 오버플로우에 주의하자.


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
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef long long int ll;
typedef long double ldb;
mt19937 rng(4672627);
 
int n, m, cnt, gr, org;
int ord[1111];
vector<int> cedge[1111];
vector<int> redge[1111];
int vis[1111], whi[1111], sz[1111];
pair<intint> E[11111];
int forw[1111][1111];
int cntw[1111][1111];
int indeg[1111];
queue<int> Q;
 
void dfs1(int v)
{
    vis[v]=1;
    for(int i=0 ; i<cedge[v].size() ; i++)
        if(!vis[cedge[v][i]]) dfs1(cedge[v][i]);
    ord[++cnt]=v;
}
 
void dfs2(int v)
{
    vis[v]=1; whi[v]=gr; sz[gr]++;
    for(int i=0 ; i<redge[v].size() ; i++)
        if(!vis[redge[v][i]]) dfs2(redge[v][i]);
}
 
int calc(void)
{
    int u, v, i, j, ret=0; gr=0; cnt=0;
    // can be optimized
    for(i=1 ; i<=n ; i++) ord[i]=0;
    for(i=1 ; i<=n ; i++) cedge[i].clear();
    for(i=1 ; i<=n ; i++) redge[i].clear();
    for(i=1 ; i<=m ; i++)
    {
        u=E[i].first; v=E[i].second;
        cedge[u].push_back(v);
        redge[v].push_back(u);
    }
    memset(whi, 0sizeof(whi));
    memset(sz, 0sizeof(sz));
    memset(vis, 0sizeof(vis));
    for(i=1 ; i<=n ; i++)
        if(!vis[i]) dfs1(i);
    reverse(ord+1, ord+n+1);
    memset(vis, 0sizeof(vis));
    for(i=1 ; i<=n ; i++)
    {
        v=ord[i];
        if(!vis[v])
        {
            gr++; dfs2(v);
            ret=max(ret, sz[gr]);
        }
    }
    return ret;
}
 
void solve(void)
{
    int i, j, u, v; ll ans=0cin>>n>>m;
    for(i=1 ; i<=m ; i++)
        cin>>E[i].first>>E[i].second;
    org=calc();
   // for(i=1 ; i<=n ; i++) cout<<whi[i]<<" "; cout<<"\n";
   // for(i=1 ; i<=gr ; i++) cout<<sz[i]<<" "; cout<<"\n";
    memset(indeg, 0sizeof(indeg));
    for(i=1 ; i<=gr ; i++)
        for(j=1 ; j<=gr ; j++) cntw[i][j]=0, forw[i][j]=0;
    for(i=1 ; i<=n ; i++) cedge[i].clear();
    for(i=1 ; i<=n ; i++) redge[i].clear();
    for(i=1 ; i<=m ; i++)
    {
        u=E[i].first; v=E[i].second;
        if(whi[u]!=whi[v])
        {
            cntw[whi[u]][whi[v]]++;
            cedge[whi[u]].push_back(whi[v]);
            indeg[whi[v]]++;
        }
    }
    while(!Q.empty()) Q.pop();
    for(i=1 ; i<=gr ; i++) forw[i][i]=1;
    for(i=1 ; i<=gr ; i++if(!indeg[i]) { Q.push(i); forw[i][i]=1; }
    while(!Q.empty())
    {
        int v=Q.front(); Q.pop();
        for(i=0 ; i<cedge[v].size() ; i++)
        {
            int nxt=cedge[v][i];
            int cntv=cntw[v][nxt];
            for(j=1 ; j<=gr ; j++)
            {
                if(forw[j][v]==0continue;
                if(forw[j][v]==1 && cntv==1) forw[j][nxt]++;
                if(forw[j][v]>=2 || cntv>=2) forw[j][nxt]+=2;
            }
            indeg[nxt]--if(indeg[nxt]==0) { forw[nxt][nxt]=1; Q.push(nxt); }
        }
    }
    for(i=1 ; i<=m ; i++)
    {
        u=E[i].first; v=E[i].second;
        if(whi[u]!=whi[v] && forw[whi[u]][whi[v]]>=2)
        {
            int tot=0;
            for(j=1 ; j<=gr ; j++)
            {
                if(forw[whi[u]][j]>=1 && forw[j][whi[v]]>=1)
                    tot+=sz[j];
            }
            if(tot>org) ans+=tot;
        }
    }
    cout<<ans<<"\n";
    for(i=1 ; i<=n ; i++) cedge[i].clear();
    for(i=1 ; i<=n ; i++) redge[i].clear();
    for(i=1 ; i<=n ; i++) whi[i]=sz[i]=0; gr=org=ans=0;
}
 
int main(void)
{
    fio; int i, tc; cin>>tc;
    for(i=1 ; i<=tc ; i++)
    {
        cout<<"Case #"<<i<<"\n";
        solve(); // reset here
    }
    return 0;
}
cs


3. 회문인 부분 문자열


역시 작년에 비해 매우 어렵다. 다3 정도라고 생각. 복잡한 문제인 만큼 천천히 생각해보자. 해야 하는 것은

  • 우선 회문인 부분 문자열을 전부 뽑아낸다.
  • 그 중 조건을 만족하는 부분 문자열을 전부 뽑아낸다. (즉, 주어진 회문이 어떤 문자열에 포함되는지 판별해야 한다)
  • 그 후, 그 부분 문자열들을 사전순으로 정렬해서 $k$번째 것이 무엇인지를 파악해야 한다.

이제 각 단계를 어떻게 할 수 있을지 생각해보자.

  • APIO 2014 팰린드롬의 풀이를 생각하자. 길이 $n$ 문자열의 회문인 서로 다른 부분 문자열의 개수는 최대 $n$개다.
  • 이 시점에서 $k$의 제한은 페이크임을 알 수 있다. 또한, 회문을 모두 뽑는 것은 Manacher 알고리즘으로 가능하다.
  • 서로 다른 것을 뽑아냈는지를 확인해야 하는데, 이건 Rabin-Karp 해시로 가능하다. 충돌 안하게 모듈로 2개 적당히 잡자.
  • 위 koosaga 블로그 링크의 설명을 보면 사실 이 부분을 이분탐색 없이 할 수 있는데, 당시에는 이분탐색까지 덮었다.

이러면 1단계가 끝난다. 여기까지 하고 한 번 예제 넣어서 잘 돌아가는지 확인했다. 이제 2단계.

  • 어쨌든 후보들은 "특정 문자열의 부분문자열인 회문"들이다. 이제 이것들이 다른 문자열에도 포함되는지 확인해야 한다.
  • 그러면 세 문자열을 합친 (사이에 이상한 문자 껴넣고) 새 문자열을 만든 후, Suffix Array + LCP + Segment Tree를 적용한다.
  • 이 과정 자체는 꽤 티피컬한데 구현이 드럽게 힘들고 귀찮다. Suffix Array는 로그제곱으로 짜도 충분하다. 

이러면 2단계가 끝난다. 여기까지 하고 한 번 예제 넣어서 잘 돌아가는지 확인했다. 이제 마지막 단계.

  • 이제 부분문자열을 사전순 정렬해야 하는데, 단순하게 Suffix Array 상으로 정렬하면 안된다. (why?)
  • 제대로 정렬하려면 "이 회문을 prefix로 갖는 suffix 중 가장 Suffix Array에서 앞에 있는 것"을 찾을 필요가 있다.
  • 이를 위해서는 또 한 번 LCP + Segment Tree + 이분탐색을 적용하면 된다. 겁나 귀찮은데 해야함
  • 이제 회문들을 "SA 위치, 회문의 길이"라는 pair로 정렬하면 사전순 정렬이 됨을 확인할 수 있다. 끝.

가치가 있다고 생각해서, 디버깅 용 코드까지 전부 그대로 올린다. 


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
289
290
291
292
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef long long int ll;
typedef long double ldb;
mt19937 rng(4672627);
const ll mod1=1561035197;
const ll mod2=1871313779;
const ll p1=27386137;
const ll p2=73186173;
 

int tree[333333], C=160000;
int k, L[3], d, LEN, FINCOUNT;
string s[3], S;
int len_odd[3][55555];
int len_tr[3][111111];
int len_ev[3][55555];
ll hsh1[3][55555];
ll hsh2[3][55555];
ll pt1[55555];
ll pt2[55555];
int LCP[155555];
int SA[155555];
int rk[155555];
int pos[155555];
int tp[155555];
vector<int> POS[3];
vector< pair< pair<intint>int> > indx;
// which string, location, length
pair<intint> fin[155555];
// location in final string in (SA), length
set< pair<ll, ll> > EX; // already inserted hashes
 
bool cmp(const int U, const int V)
{
    if(pos[U]!=pos[V]) return pos[U]<pos[V];
    if(U+d<LEN && V+d<LEN) return pos[U+d]<pos[V+d];
    return U>V; // okay!
}
 
void calc_LCPSA(void)
{
    int i, j, c; LEN = S.length();
    for(i=0 ; i<LEN ; i++) pos[i]=S[i], SA[i]=i;
    for(d=1 ; d<=LEN ; d<<=1)
    {
        sort(SA, SA+LEN, cmp); tp[0]=0;
        for(i=1 ; i<LEN ; i++) tp[i]=tp[i-1]+cmp(SA[i-1], SA[i]);
        for(i=0 ; i<LEN ; i++) pos[SA[i]]=tp[i];
        if(tp[LEN-1]==LEN-1break;
    }
    for(i=0 ; i<LEN ; i++) rk[SA[i]]=i;
    for(i=0, j=0 ; i<LEN ; i++, j=max(j-10))
    {
        if(rk[i]==LEN-1continue; c=SA[rk[i]+1];
        for( ; i+j<LEN && c+j<LEN && S[i+j]==S[c+j] ; j++);
        LCP[rk[i]]=j;
    }
}
 
void update(int loc, int v)
{
    loc+=C; tree[loc]=v;
    for( ; loc>1 ; loc>>=1)
        tree[loc>>1]=min(tree[loc], tree[loc^1]);
}
 
int query(int l, int r)
{
    int ret=1e9;
    for(l+=C, r+=C ; l<r ; l>>=1, r>>=1)
    {
        if(l&1) ret=min(ret, tree[l++]);
        if(r&1) ret=min(ret, tree[--r]);
    }
    return ret;
}
 
pair<ll, ll> hasher(int idx, int l, int r)
{
    // [l, r] = [0, r] - [0, l-1] * p^(r-l+1)
    if(l==0return make_pair(hsh1[idx][r], hsh2[idx][r]);
    ll ret1=(hsh1[idx][r]-(hsh1[idx][l-1]*pt1[r-l+1]%mod1));
    if(ret1<0) ret1+=mod1;
    ll ret2=(hsh2[idx][r]-(hsh2[idx][l-1]*pt2[r-l+1])%mod2);
    if(ret2<0) ret2+=mod2;
    return make_pair(ret1, ret2);
}
 
void get_hash(int idx)
{
    ll cur1=0, cur2=0, i;
    for(i=0 ; i<s[idx].length() ; i++)
    {
        hsh1[idx][i]=(cur1*p1+(s[idx][i]-'a'+1))%mod1; cur1=hsh1[idx][i];
        hsh2[idx][i]=(cur2*p2+(s[idx][i]-'a'+1))%mod2; cur2=hsh2[idx][i];
    }
}
 
 
bool isok(int idx, int l, int r)
{
    pair<ll, ll> TT = hasher(idx, l, r);
    if(EX.count(TT)) return true;
    return false;
}
 
int getloc(int idx, int l)
{
    if(idx==0return l;
    if(idx==1return L[0]+1+l;
    if(idx==2return L[0]+L[1]+2+l;
}
 
bool isinside(int idx, int RKloc, int goal)
{
    int cc=lower_bound(POS[idx].begin(), POS[idx].end(), RKloc)-POS[idx].begin();
    // POS[cc], POS[cc-1] trial
    if(cc < POS[idx].size())
    {
        // RKloc ~ cc distance
        int rv=query(RKloc, POS[idx][cc]);
        if(rv>=goal) return true;
    }
    if(cc-1 >=0)
    {
        int rv=query(POS[idx][cc-1], RKloc);
        if(rv>=goal) return true;
    }
    return false;
}
 
int get_front(int RKloc, int goal)
{
    int lef=0int rig=RKloc-1int best=RKloc, mid;
    while(lef<=rig)
    {
        mid=(lef+rig)/2;
        if(query(mid, RKloc)>=goal) best=mid, rig=mid-1;
        else lef=mid+1;
    }
    return best;
}
 
void add_work(int idx, int l, int r)
{
   // cout<<idx<<" "<<l<<" "<<r<<endl;
    pair<ll, ll> TT = hasher(idx, l, r); EX.insert(TT);
    // one should contain, other should not
    // [l, r] at idx
    int mylen=r-l+1int myloc=rk[getloc(idx, l)];
    int others=0;
    if(isinside((idx+1)%3, myloc, mylen)) others++;
    if(isinside((idx+2)%3, myloc, mylen)) others++;
    int newmyloc=get_front(myloc, mylen);
    if(others==1)
    {
        FINCOUNT++;
        fin[FINCOUNT]=make_pair(newmyloc, mylen);
    }
}
 
void finwork(int idx)
{
    int i, j; // odd insert
    for(i=0 ; i<L[idx] ; i++)
    {
        int lef=1, rig=len_odd[idx][i], mid, best=0;
        while(lef<=rig)
        {
            mid=(lef+rig)/2;
            if(isok(idx, i-mid+1, i+mid-1)) best=mid, lef=mid+1;
            else rig=mid-1;
        }
        for(j=best+1 ; j<=len_odd[idx][i] ; j++)
            add_work(idx, i-j+1, i+j-1);
    }
    for(i=0 ; i<L[idx] ; i++)
    {
        if(len_ev[idx][i]==0continue;
        int lef=1, rig=len_ev[idx][i], mid, best=0;
        while(lef<=rig)
        {
            mid=(lef+rig)/2;
            if(isok(idx, i-mid+1, i+mid)) best=mid, lef=mid+1;
            else rig=mid-1;
        }
        for(j=best+1 ; j<=len_ev[idx][i] ; j++)
            add_work(idx, i-j+1, i+j);
    }
}
 
// will do [l, r] form
 
void run_manacher(int idx)
{
    int i, l=1, r=1; L[idx]=s[idx].length();
    string Ns = "@" + s[idx] + "#";
    for(i=1 ; i<=L[idx] ; i++)
    {
        len_odd[idx][i]=min(r-i, len_odd[idx][l+(r-i)]);
        while(Ns[i-len_odd[idx][i]] == Ns[i+len_odd[idx][i]]) len_odd[idx][i]++;
        if(i+len_odd[idx][i]>r)
        {
            l=i-len_odd[idx][i];
            r=i+len_odd[idx][i];
        }
    }
    for(i=0 ; i<L[idx] ; i++) len_odd[idx][i]=len_odd[idx][i+1];
    string NNs = "{";
    for(i=0 ; i<L[idx] ; i++)
    {
        NNs.push_back(s[idx][i]);
        if(i!=L[idx]-1) NNs.push_back('#');
    }
    NNs.push_back('}'); // {a#b#c}
    ll t=NNs.length()-2; l=r=1;
    for(i=1 ; i<=t ; i++)
    {
        len_tr[idx][i]=min(r-i, len_tr[idx][l+(r-i)]);
        while(NNs[i-len_tr[idx][i]] == NNs[i+len_tr[idx][i]]) len_tr[idx][i]++;
        if(i+len_tr[idx][i]>r)
        {
            l=i-len_tr[idx][i];
            r=i+len_tr[idx][i];
        }
    }
    for(i=2 ; i<=t ; i+=2)
    {
        int lc=i/2-1;
        len_ev[idx][lc]=len_tr[idx][i]/2;
    }
}
 
void solve(void)
{
    FINCOUNT=0;
    int i, j; EX.clear();
    for(i=0 ; i<3 ; i++) POS[i].clear();
    memset(tree, 0sizeof(tree)); indx.clear();
    cin>>s[0]>>s[1]>>s[2]>>k;
    memset(len_odd, 0sizeof(len_odd));
    memset(len_ev, 0sizeof(len_ev));
    memset(len_tr, 0sizeof(len_tr));
    for(i=0 ; i<3 ; i++) get_hash(i);
    for(i=0 ; i<3 ; i++) run_manacher(i);
    /* testing manacher
    for(i=0 ; i<3 ; i++)
    {
        for(j=0 ; j<L[i] ; j++) cout<<len_odd[i][j]<<" "; cout<<"\n";
        for(j=0 ; j<L[i] ; j++) cout<<len_ev[i][j]<<" "; cout<<"\n";
    }
    */
    S = s[0+ '}' + s[1+ '}' + s[2];
    calc_LCPSA(); LEN=S.length();
    for(i=0 ; i<=L[0]-1 ; i++) POS[0].push_back(rk[i]);
    for(i=L[0]+1 ; i<=L[0]+L[1] ; i++) POS[1].push_back(rk[i]);
    for(i=L[0]+L[1]+2 ; i<=L[0]+L[1]+L[2]+1 ; i++) POS[2].push_back(rk[i]);
    for(i=0 ; i<3 ; i++) sort(POS[i].begin(), POS[i].end());
    for(i=0 ; i<=LEN-2 ; i++) update(i, LCP[i]);
 
    /* LCP, SA check
    for(i=0 ; i<=LEN-1 ; i++)
    {
        cout<<S.substr(SA[i], S.length())<<"\n";
        cout<<LCP[i]<<"\n";
    }
    */
    //cout<<"FINWORKSTART"<<"\n"; return;
    for(i=0 ; i<3 ; i++) finwork(i);
    sort(fin+1, fin+FINCOUNT+1);
    if(FINCOUNT<k) { cout<<-1<<endlreturn; }
    int tt1=fin[k].first;
    int tt2=fin[k].second;
    for(i=0 ; i<tt2 ; i++cout<<S[SA[tt1]+i];
    cout<<endlreturn;
}
 
int main(void)
{
    fio; int i, tc; cin>>tc;
    pt1[0]=1; pt2[0]=1;
    for(i=1 ; i<=55550 ; i++) pt1[i]=(p1*pt1[i-1])%mod1;
    for(i=1 ; i<=55550 ; i++) pt2[i]=(p2*pt2[i-1])%mod2;
    for(i=1 ; i<=tc ; i++)
    {
        cout<<"Case #"<<i<<"\n";
        solve(); // reset here
    }
    return 0;
}
cs


5. 돌 옮기기


5-1을 긁는 것은 어렵지 않다. 상태 전이를 전부 파악하고 union-find를 돌리면 된다.

상태 전이를 효율적으로 하는 게 약간 헷갈릴 수 있는데, 비트마스킹을 잘 활용하면 $\mathcal{O}(n \cdot 2^n)$ 풀이를 얻는다.

뇌절을 한 흔적이 진짜 많이 보이는 코드를 짰다. 알아서 잘 해독하시길 ^~^;;


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 fio ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef long long int ll;
typedef long double ldb;
mt19937 rng(4672627);
 
int n, kt, msk1, msk2;
vector<int> edge[22];
int con[21][21];
int whi1[211111];
int whi2[211111];
int unionmask[1<<20];
int frst[1<<20];
int mymask[21];
int par[1<<20];
int actok[1<<20];
 
int find(int x)
{
    if(par[x]==x) return x;
    return par[x]=find(par[x]);
}
 
void merge(int u, int v)
{
    if(!actok[u] || !actok[v]) return;
    u=find(u); v=find(v);
    if(u==v) return;
    par[u]=v; return;
}
 
void solve(void)
{
    bool actualwork=false;
    cin>>n; int i, j, k, u, v;
    memset(con, 0sizeof(con));
    if(n<=20) { actualwork=true; }
    for(i=1 ; i<=n-1 ; i++)
    {
        cin>>u>>v; u--; v--;
        if(actualwork)
        {
            con[u][v]=1; con[v][u]=1;
            edge[u].push_back(v);
            edge[v].push_back(u);
        }
    }
    cin>>kt;
    for(i=1 ; i<=kt ; i++cin>>whi1[i]>>whi2[i];
    for(i=1 ; i<=kt ; i++) whi1[i]--, whi2[i]--;
    if(!actualwork)
    {
        cout<<0<<endl;
        return;
    }
    memset(mymask, 0sizeof(mymask));
    memset(unionmask, 0sizeof(unionmask));
    memset(actok, 0sizeof(actok)); actok[0]=1;
    for(i=0 ; i<n ; i++)
    {
        for(j=0 ; j<n ; j++)
        {
            if(con[i][j]) mymask[i]|=(1<<j);
        }
    }
    for(i=0 ; i<n ; i++) mymask[i]|=(1<<i);
    for(i=1 ; i<(1<<n) ; i++)
    {
        int cc=frst[i];
        unionmask[i]=unionmask[i^(1<<cc)]|mymask[cc];
    }
    for(i=1 ; i<(1<<n) ; i++)
    {
        int cc=frst[i];
        if(!actok[i^(1<<cc)]) continue;
        if((1<<cc)&(unionmask[i^(1<<cc)])) continue;
        actok[i]=1;
    }
    for(i=0 ; i<(1<<n) ; i++) par[i]=i;
    for(i=0 ; i<(1<<n) ; i++)
    {
        if(!actok[i]) continue;
        for(j=0 ; j<n ; j++)
        {
            if(!(i&(1<<j))) continue;
            int remmsk=i^(1<<j);
            for(k=0 ; k<edge[j].size() ; k++)
            {
                if(remmsk&(1<<edge[j][k])) continue;
                if(!(unionmask[remmsk]&(1<<edge[j][k])))
                    merge(i, remmsk|(1<<edge[j][k]));
            }
        }
    }
    int ans=0int cur1=0int cur2=0;
    for(i=1 ; i<=kt ; i++)
    {
        cur1|=(1<<whi1[i]);
        cur2|=(1<<whi2[i]);
        if(find(cur1)==find(cur2)) ans++;
    }
    for(i=0 ; i<n ; i++) edge[i].clear();
    cout<<ans<<endl;
}
 
 
int main(void)
{
    fio; int i, j, tc; cin>>tc;
    frst[0]=0; frst[1]=0;
    for(i=1 ; i<20 ; i++)
        for(j=1<<i ; j<(1<<(i+1)) ; j++) frst[j]=i;
    for(i=1 ; i<=tc ; i++)
    {
        cout<<"Case #"<<i<<"\n";
        solve(); // reset here
    }
    return 0;
}
cs


'PS > 대회 후기' 카테고리의 다른 글

SCPC 2021 1차 예선 풀이  (0) 2021.07.16
ACM-ICPC Seoul Regional 2020  (0) 2020.11.20
SCPC 2020 본선 후기  (5) 2020.11.09
ACM-ICPC Seoul Regional Preliminary 2020  (0) 2020.10.19
SCPC 2020 2차 예선 풀이  (1) 2020.09.05
SCPC 2020 1차 예선 풀이  (0) 2020.08.22
  1. 엄마 나 커서 rkm이 될래요!엄마 나 커서 rkm이 될래요!엄마 나 커서 rkm이 될래요!엄마 나 커서 rkm이 될래요!엄마 나 커서 rkm이 될래요!엄마 나 커서 rkm이 될래요!엄마 나 커서 rkm이 될래요!

  2. 2등상 넘나 멋지네여 축하드립니다!!

  3. ustoiewe231 2020.11.20 00:00

    도움되는 내용 매우 잘 보고 가요

  4. ㅇㅇ 2020.12.17 16:23

    2등 정말 섹시하다


매우 늦게 올린다. 결과는 6등으로, 예상보다는 매우 높았으나 여전히 만족스러운 결과는 아니었다. J를 풀지 못한것이 아쉬움.

작년의 팀과 멤버는 동일하다. rkm0959, junie, bjwj5505다. 내가 1년간 공부를 많이 한 건 맞지만, 정작 최근에는 CTF 참가 등으로 PS, CP에 집중하지 못해서 팀의 전체적인 실력이 강화된건지 퇴화된건지 좀 애매한 것 같다. 다른 팀원도 비슷하다. 일단 지금까지는 나쁘지 않게 하고 있는듯.

 

타임라인과 함께 간략한 설명을 붙이도록 하겠다. 모든 사람을 3인칭으로 명명하겠다.

  • 시작하자마자 문제 12개 모두 출력
  • 스코어보드 보니까 I가 0분컷으로 풀렸네? 진짜 쉽네?
  • rkm0959가 바로 컴퓨터 잡고 AC (5분)
  • 이때쯤 E도 퍼솔이 나왔고, 바로 rkm0959가 이어서 AC (8분)
  • bjwj5505는 이때 L을 읽고 있었고, junie는 앞쪽 문제를 읽는 중.
  • bjwj5505가 L을 구현했지만 WA 후 코드 프린트
  • rkm0959는 G를 보면서 수학 문제라고 생각을 했으나 매우 어려워보여서 대기중
  • 대신 K가 쉽다는 것을 확인하고, 풀이를 bjwj5505와 확인
  • rkm0959가 H의 풀이를 찾고, 정당성을 bjwj5505와 확인 
  • 그러다가 F가 쉬워보여서 rkm0959, junie가 해결 시도
  • bjwj5505가 L을 디버깅하고 있으며, rkm0959가 K를 짜기 시작
  • bjwj5505가 L을 고치고 AC (39분), rkm0959도 곧 K AC (46분)
  • bjwj5505, junie가 F의 풀이를 찾는동안 rkm0959 H 구현
  • F의 풀이를 찾고 AC (51분), H도 곧 AC (58분) - 1시간 6솔브 도달
  • 정확하게 기억은 안나지만 junie가 느린 J 풀이를 찾았음 (로그 2개)
  • 그러나 정확하게 풀이를 이해하고 있는 사람은 junie 혼자
  • bjwj5505, junie는 A의 해결에 집중. rkm0959는 B가 DP임을 확인
  • rkm0959가 D가 세그먼트 트리로 해결될 수 있는 문제임을 확인
  • A, B, D의 동시다발적 구현 + WA + 디버깅 파티 후 전부 AC (115, 133, 149분)
  • J를 고치려고 했고, "맞는" 풀이를 1분 전에 찾았으나 TLE. 똑떨....


'PS > 대회 후기' 카테고리의 다른 글

ACM-ICPC Seoul Regional 2020  (0) 2020.11.20
SCPC 2020 본선 후기  (5) 2020.11.09
ACM-ICPC Seoul Regional Preliminary 2020  (0) 2020.10.19
SCPC 2020 2차 예선 풀이  (1) 2020.09.05
SCPC 2020 1차 예선 풀이  (0) 2020.08.22
APIO 2020 Open Contest  (0) 2020.08.22


1. 실력 맞추기


기본적으로 최적의 방식는 각 그룹을 실력 순으로 나열한 뒤 매칭시키는 것이다.

이제 $A$ 그룹의 사람 한 명의 실력을 바꾼다고 가정하자. 이때, 새로운 실력이 $B$ 그룹 중 한 사람의 실력과 일치하는 경우만 고려해도 무방하다.

이제 $A_i$를 $B_j$로 바꾼다고 가정하자. 만약 $i=j$라면, 공정도의 합은 $\sum_{k=1, k \neq i}^{n} |A_k - B_k|$다. 

만약 $i < j$라면, 공정도의 합은 $\sum_{k=1}^{i-1} |A_k - B_k| + \sum_{k=i+1}^j |A_k - B_{k-1}| + \sum_{k=j+1}^n |A_k-B_k|$가 된다.

만약 $i > j$라면, 공정도의 합은 $\sum_{k=1}^{j-1} |A_k - B_k| + \sum_{k=j+1}^i |A_{k-1} - B_k| + \sum_{k=i+1}^n |A_k-B_k|$이다.

이제 각 $i, j$에 대하여 저 값들 중 최솟값을 구하면 된다. 그런데 식의 형태가 상당히 부분합 느낌이 강하게 난다.


$i=j$인 경우는 $|A_k - B_k|$에 대한 부분합을 전부 계산하는 방식으로 처리할 수 있다. 

$i < j$인 경우에는 $-|A_i-B_i| + \sum_{k=i+1}^j (|A_k - B_{k-1}| - |A_k - B_k|) $의 최솟값을 구하는 것과 같다.

이는 최대 연속 구간합을 계산하는 방식과 동일하게 계산할 수 있다. $i$를 고정하고 최적의 $j$를 쉽게 구할 수 있기 때문이다.

$i >j$인 경우에도 동일한 접근이 가능하며, 쉽게 계산하려면 $A$ 배열과 $B$ 배열을 swap 한 뒤 위 경우를 그대로 적용해도 된다.


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
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
ll n, ans, dfdf;
ll a[222222];
ll b[222222];
ll c[222222];
ll d[222222];
 
void work(void)
{
    ll i; d[n]=1e18;
    for(i=1 ; i<=n-1 ; i++) c[i]=c[i-1]+abs(a[i+1]-b[i])-abs(a[i+1]-b[i+1]);
    for(i=n-1 ; i>=1 ; i--) d[i]=min(d[i+1], c[i]);
    for(i=1 ; i<=n ; i++) ans=min(ans, dfdf+d[i]-c[i-1]-abs(a[i]-b[i]));
}
 
void solve(void)
{
    ll i, j, mx=0cin>>n; ans=0;
    for(i=1 ; i<=n ; i++cin>>a[i]; sort(a+1, a+n+1);
    for(i=1 ; i<=n ; i++cin>>b[i]; sort(b+1, b+n+1);
    for(i=1 ; i<=n ; i++) ans+=abs(a[i]-b[i]); dfdf=ans;
    for(i=1 ; i<=n ; i++) mx=max(mx, abs(a[i]-b[i])); ans-=mx;
    work(); for(i=1 ; i<=n ; i++) swap(a[i], b[i]); work();
    cout<<ans; return;    
}
 
int main(void)
{
    fio; ll i, tc; cin>>tc;
    for(i=1 ; i<=tc ;  i++)
    {
        cout<<"Case #"<<i<<"\n";
        solve(); cout<<"\n";
    }
    return 0;
}
cs


2. 고구마


$a_i + a_{i+1} + \cdots + a_j \le M$을 만족하면서, $a_i + a_{i+1} + \cdots + a_j$를 최대화하고 싶다.

부분합 배열 $ps_i = a_1 +a_2 + \cdots + a_i$를 만들면, 목표는 $ps_j - ps_{i-1}$을 조건 아래에서 최대화하는 것이다.

$j$를 고정하자. 그러면 목표는 $ps_{i-1} \ge ps_j - M$이면서 최소인 $ps_{i-1}$을 찾는 것이다.


이는 $ps$ 배열을 원소로 갖는 std::set을 이용하여 쉽게 찾을 수 있다. 1번보다 훨씬 쉬운 문제.


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
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
ll a[333333], ps[322222], n, M, ans;
set<ll> S; set<ll>::iterator it;
 
void solve(void)
{
    ll i; cin>>n>>M; S.clear(); ans=0;
    for(i=1 ; i<=n ; i++cin>>a[i]; S.insert(0);
    for(i=1 ; i<=n ; i++)
    {
        ps[i]=ps[i-1]+a[i];
        it=S.lower_bound(ps[i]-M);
        if(it!=S.end()) ans=max(ans, ps[i]-(*it));
        S.insert(ps[i]);
    }
    cout<<ans; return;
}
 
int main(void)
{
    fio; ll i, tc; cin>>tc;
    for(i=1 ; i<=tc ;  i++)
    {
        cout<<"Case #"<<i<<"\n";
        solve(); cout<<"\n";
    }
    return 0;
}
cs


3. 아르바이트


1차 4번 문제의 느낌이 나는 문제인 것 같다. 

우선 중요한 점은, 하루의 급여가 바뀐 경우 최대 $k$개의 구간의 총합이 변화한다는 점이다. 즉, 구간의 합이 변화하는 총 횟수는 최대 $Qk$번이다. 


$n-k+1$개의 구간의 총합을 관리하고 있는 multiset이 있다고 하자. 우리는 이 multiset의 중앙값을 계속 구해야 한다.

총합 자체를 관리하는 것은 $\mathcal{O}(Qk + n)$에 쉽게 할 수 있으므로, 우리의 궁극적인 문제는 다음과 같다.

  • 집합에 속한 원소 삭제
  • 집합에 원소 하나 추가
  • 집합의 중앙값 계산

다양한 접근이 가능하다. 첫 번째 접근은 세그먼트 트리를 이용한다.

가능한 구간의 합 $\mathcal{O}(Qk+n)$개를 전부 전처리 한 후 좌표압축하자. 

각 원소의 등장 횟수를 관리하는 합 세그먼트 트리를 관리하면, 이분탐색으로 답을 구할 수 있다.


세그먼트 트리를 구현할 경우 트리를 따라 내려가는 방식으로 이분탐색을 없앨 수 있다.

나는 중앙값을 계산하는 횟수가 $Q$로 적으므로, 세그먼트 트리 대신 펜윅을 사용하는 방식을 택했다.

그런데 이 방식을 구현했는데 TLE가 발생했다. 최적화를 했는데도 TLE여서 접근을 바꾸기로 했다.


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
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
struct Fenwick
{
    int tree[955555], C=450000;
    void init(void) { memset(tree, 0sizeof(tree)); }
    void update(int x, int v) { while(x<=C) { tree[x]+=v; x+=(x&-x); } }
    int query(int x) { int ret=0while(x) { ret+=tree[x]; x-=(x&-x); } return ret; }
    int rquery(int l, int r) { return query(r)-query(l-1); }
} T; 
 
int n, k, q;
int init[222222], ch[222222], ps[222222], res[222222];
int whi[222222], v[222222];
vector<int> POS;
 
int get_median(void)
{
    int lef, rig, mid, best;
    lef=1; rig=POS.size();
    while(lef<=rig)
    {
        mid=(lef+rig)/2;
        if(T.query(mid)>=(n-k+3)/2) best=mid, rig=mid-1;
        else lef=mid+1;
    }
    return POS[best-1];
}
 
void UPD(int vv, int t)
{
    int loc=lower_bound(POS.begin(), POS.end(), vv)-POS.begin()+1;
    T.update(loc, t); return;
}
 
void solve(void)
{
    int i, j, c=0, tt=0cin>>n>>k>>q; 
    tt=n-k+1; POS.clear();
    for(i=1 ; i<=n ; i++cin>>init[i];
    for(i=1 ; i<=q ; i++cin>>whi[i]>>v[i]; 
    for(i=1 ; i<=q ; i++) tt+=min(whi[i], n-k+1)-max(1, whi[i]-k+1)+1;
    POS.resize(tt); T.C=tt+5;
    for(i=1 ; i<=n ; i++) ch[i]=init[i];
    for(i=1 ; i<=n ; i++) ps[i]=ps[i-1]+init[i]; // ps[i] : i ~ i+k-1
    for(i=1 ; i<=n-k+1 ; i++) res[i]=ps[i+k-1]-ps[i-1];
    for(i=1 ; i<=n-k+1 ; i++) POS[c++]=res[i];
    for(i=1 ; i<=q ; i++)
    {
        for(j=max(1, whi[i]-k+1) ; j<=min(whi[i], n-k+1) ; j++
        {
            res[j]+=v[i]-ch[whi[i]];
            POS[c++]=res[j];
        }
        ch[whi[i]]=v[i];
    }
    sort(POS.begin(), POS.end());
    POS.erase(unique(POS.begin(), POS.end()), POS.end());
    for(i=1 ; i<=n ; i++) ch[i]=init[i];
    for(i=1 ; i<=n ; i++) ps[i]=ps[i-1]+init[i];
    for(i=1 ; i<=n-k+1 ; i++) res[i]=ps[i+k-1]-ps[i-1];
    for(i=1 ; i<=n-k+1 ; i++) UPD(res[i], 1); cout<<get_median()<<" ";
    for(i=1 ; i<=q ; i++)
    {
        for(j=max(1, whi[i]-k+1) ; j<=min(whi[i], n-k+1) ; j++
        {
            UPD(res[j], -1);
            res[j]+=v[i]-ch[whi[i]];
            UPD(res[j], 1);
        }
        ch[whi[i]]=v[i];
        cout<<get_median()<<" ";
    }
    for(i=0 ; i<=2*tt+20 ; i++) T.tree[i]=0;
}
 
int main(void)
{
    fio; int i, tc; cin>>tc; T.init();
    for(i=1 ; i<=tc ; i++)
    {
        cout<<"Case #"<<i<<"\n";
        solve(); cout<<"\n";
    }
    return 0;
}
cs


두 번째 방식은 priority_queue를 이용한다. 

$n-k+1$개의 수들 중 작은 절반을 관리하는 PQ와 큰 절반을 관리하는 PQ를 생각하자.

이를 관리하는 것은 어렵지 않은데, 다음을 반복하면 된다.

  • 원소 삭제시, 해당 원소를 포함하는 PQ에서 원소 삭제
  • 원소 추가시, 중앙값과 비교하여 적합한 PQ에 원소 추가
  • 중앙값 계산시, 큰 절반을 관리하는 PQ에서 최소 원소 찾기
  • 마지막으로, 양쪽 PQ의 원소 개수가 원하는 반반이 되도록 밸런스 맞추기

이제 문제는 PQ에서 원소를 삭제해야 한다는 것이다. 그런데 삭제 가능한 PQ가 있다!

나는 친구에게 들었는데, 대충 top()을 호출할 때 삭제된 얘들을 다 날리는 방식이다. 자세한 것은 코드 참고.


이 방식은 연산 자체가 훨씬 간단해서 더욱 빠르다. 제출 10번 채웠으면 억울해 죽을 뻔 ㅋㅋ


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
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int inf=1e9;
struct iHeap 
{
    priority_queue<int> q, qr;
    void rset(void) { while(!q.empty()) q.pop(); while(!qr.empty()) qr.pop(); }
    inline int size(void) { return q.size()-qr.size(); }
    inline void rmv(int x) { qr.push(x); }
    inline int top()
    {
        while(q.size() && qr.size() && q.top() == qr.top()) { q.pop(); qr.pop(); }
        return q.size()?q.top():-inf;
    }
    inline void push(int x) { q.push(x); }
} A, B;
 
int n, k, q, asz, bsz;
int init[222222], ch[222222];
int ps[222222], res[222222];
int cv[222222];
int whi[222222], v[222222];
vector<int> POS;
 
void rmv(int x)
{
    if(x<=A.top()) { A.rmv(x); }
    else { B.rmv(-x); }
}
 
void ins(int x)
{
    if(x<=A.top()) { A.push(x); }
    else { B.push(-x);  } 
}
 
void housekeep(void)
{
    while(A.size()>asz)
    {
        ll t=A.top(); A.rmv(t);
        B.push(-t);
    }
    while(B.size()>bsz)
    {
        ll t=B.top(); B.rmv(t);
        A.push(-t);
    }
}
 
void solve(void)
{
    int i, j; cin>>n>>k>>q; A.rset(); B.rset();
    for(i=1 ; i<=n ; i++cin>>init[i];
    for(i=1 ; i<=q ; i++cin>>whi[i]>>v[i]; 
    for(i=1 ; i<=n ; i++) ch[i]=init[i];
    for(i=1 ; i<=n ; i++) ps[i]=ps[i-1]+init[i]; 
    for(i=1 ; i<=n-k+1 ; i++) { res[i]=ps[i+k-1]-ps[i-1]; cv[i]=res[i]; }
    sort(cv+1, cv+(n-k+1)+1);
    for(i=1 ; i<=(n-k+1)/2 ; i++) { A.push(cv[i]); }
    for(i=(n-k+1)/2+1 ; i<=(n-k+1) ; i++) { B.push(-cv[i]); }
    asz=(n-k+1)/2; bsz=(n-k+1)-asz;
    cout<<-B.top()<<" ";
    for(i=1 ; i<=q ; i++)
    {
        for(j=max(1, whi[i]-k+1) ; j<=min(whi[i], n-k+1) ; j++
        {
            rmv(res[j]);
            res[j]+=v[i]-ch[whi[i]];
            ins(res[j]);
        }
        ch[whi[i]]=v[i]; housekeep();
        cout<<-B.top()<<" ";
    }
}
 
int main(void)
{
    fio; int i, tc; cin>>tc;
    for(i=1 ; i<=tc ; i++)
    {
        cout<<"Case #"<<i<<"\n";
        solve(); cout<<"\n";
    }
    return 0;
}
cs


4. 안전운전


가로선은 총합에 고려하지 않는다는 것을 늦게 읽어서 뇌절한 문제다. 

특정 $x$좌표 $T$에서 뒤집기를 시전했다고 가정하자. 그러면 그 후 경로의 모든 가로 좌표 $x$는 $2T-x$로 변환된다.


주어진 경로와 도로를 구간으로 쪼개서, 각 구간에서 경로/도로들의 가로 좌표가 고정되도록 하자.


이제 뒤집기 이전과 이후, 답에 더해지는 값들을 생각해보자.

  • 뒤집기 이전에는 기존 경로 그대로 간다. 여기서 더해지는 값은 미리 전처리 가능하다.
  • 뒤집는 가로선에서 $T$는 해당 가로선의 양 끝점 사이의 좌표가 된다.
  • 뒤집기 이후에는 가로 좌표 $x$가 $2T-x$로 변환된다. 이후 구간에서 기존 가로 좌표가 $x$고, 왼쪽/오른쪽 도로의 가로 좌표가 각각 $L, R$인 경우, $L \le 2T-x \le R$인 경우에만 구간의 세로 길이가 답에 더해진다. 이는 부등식은 $(L+x)/2 \le T \le (R+x)/2$과 같다.

이제 뒤집는 가로선의 위치를 고정하고 생각하자. 이 가로선의 위치를 위에서부터 아래로 순서대로 본다.

매우 커다란 가상의 세그먼트 트리를 하나 준비한다.

  • 각 구간에 대해, 세그트리의 구간 $[(L+x)/2, (R+x)/2]$에 해당 구간의 세로 길이만큼의 값을 더한다.
  • 가로선이 등장한 경우, 그 가로선의 범위를 $[x_l, x_r]$이라 하자. 이 구간에서 세그트리의 최댓값을 뽑는다.
  • 그 가로선 아래에서 얻어지는 값은 미리 전처리하였으므로, 이를 더한다.
  • 이렇게 해서 얻어지는 값이 답의 후보이다. 이를 위에서부터 아래로 내려가면서 반복한다.

물론, 커다란 가상의 세그먼트 트리는 단순히 좌표압축으로 단순 세그먼트 트리로 바꿀 수 있다.

이제 필요한 것은 구간에 값 추가 + 구간 최댓값을 지원하는 세그먼트 트리고, 이는 lazy propagation으로 가능하다.


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
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
struct SegmentTree
{
    int tree[3588888];
    int lazy[3588888];
    void init(void) { memset(tree, 0sizeof(tree)); memset(lazy, 0sizeof(lazy)); }
    void workdown(int index, int s, int e)
    {
        if(s!=e)
        {
            lazy[index<<1]+=lazy[index];
            tree[index<<1]+=lazy[index];
            lazy[index<<1|1]+=lazy[index];
            tree[index<<1|1]+=lazy[index];
        }
        lazy[index]=0;
    }
    void update(int index, int s, int e, int l, int r, int v)
    {
        if(l>|| r<s) return
        workdown(index,s,e); 
        if(l<=&& e<=r) 
        {
            lazy[index]+=v;
            tree[index]+=v;
            return;
        }
        int m=(s+e)>>1;
        update(index<<1,s,m,l,r,v); 
        update(index<<1|1,m+1,e,l,r,v); 
        tree[index]=max(tree[index<<1], tree[index<<1|1]);
    }
    int eval(int index, int s, int e, int l, int r)
    {
        if(l>|| r<s) return -1e9;
        workdown(index, s, e);
        if(l<=&& e<=r) return tree[index];
        int m=(s+e)>>1;
        int ret=max(eval(index<<1,s,m,l,r), eval(index<<1|1,m+1,e,l,r)); 
        tree[index]=max(tree[index<<1], tree[index<<1|1]); 
        return ret; 
    }
} T;
 
int ans, cnt, L, R, M, fin;
int lidx, ridx, midx;
int cut[666666];
pair<intint> LF[222222], RG[222222], MM[222222];
vector<int> XP, RES;
int secL[666666], secR[666666];
int secM[666666], secV[666666];
 
void UPD(int u, int v, int er)
{
    u=lower_bound(RES.begin(), RES.end(), u)-RES.begin()+1;
    v=lower_bound(RES.begin(), RES.end(), v)-RES.begin()+1;
    T.update(11, RES.size(), u, v, er);
}
 
int QUERY(int u, int v)
{
    if(u>v) swap(u, v);
    u=lower_bound(RES.begin(), RES.end(), u)-RES.begin()+1;
    v=lower_bound(RES.begin(), RES.end(), v)-RES.begin()+1;
    return T.eval(11, RES.size(), u, v);
}
 
void solve(void)
{
    fio; ll i, j, x, y, u, v; cin>>L>>R>>M;
    XP.clear(); RES.clear(); cnt=0; ans=0;
    for(i=1, x=0, y=0 ; i<=L ; i++)
    {
        cin>>u>>v; x+=u; LF[i]=make_pair(y, x);
        XP.push_back(y); y+=v; fin=y;
    }
    for(i=1, x=0, y=0 ; i<=R ; i++)
    {
        cin>>u>>v; x+=u; RG[i]=make_pair(y, x); 
        XP.push_back(y); y+=v; fin=y;
    }
    for(i=1, x=0, y=0 ; i<=M ; i++)
    {
        cin>>u>>v; x+=u; MM[i]=make_pair(y, x); 
        XP.push_back(y); y+=v; fin=y;
    }
    sort(XP.begin(), XP.end()); 
    XP.erase(unique(XP.begin(), XP.end()), XP.end()); XP.push_back(fin);
    for(i=0, lidx=1, ridx=1, midx=1 ; i<XP.size() ; i++)
    {
        if(XP[i]==fin) break;
        while(lidx<=&& LF[lidx].first<=XP[i]) lidx++; lidx--;
        while(ridx<=&& RG[ridx].first<=XP[i]) ridx++; ridx--;
        while(midx<=&& MM[midx].first<=XP[i]) midx++; midx--;
        ++cnt; secL[cnt]=LF[lidx].second; secR[cnt]=RG[ridx].second;
        secM[cnt]=MM[midx].second; secV[cnt]=XP[i+1]-XP[i];
        RES.push_back((secL[cnt]+secM[cnt])/2); RES.push_back((secR[cnt]+secM[cnt])/2);
    }
    for(i=1 ; i<=cnt-1 ; i++)
    {
        if(secM[i]!=secM[i+1]) 
        {
            RES.push_back(secM[i]);
            RES.push_back(secM[i+1]);
        }
    }
    sort(RES.begin(), RES.end());
    RES.erase(unique(RES.begin(), RES.end()), RES.end());
    for(i=1 ; i<=cnt ; i++)
    {
        cut[i]=cut[i-1];
        if(secL[i]<=secM[i] && secM[i]<=secR[i]) cut[i]+=secV[i];
    }
    ans=cut[cnt];
    for(i=cnt ; i>=2 ; i--)
    {
        UPD((secL[i]+secM[i])/2, (secR[i]+secM[i])/2, secV[i]);
        if(secM[i]!=secM[i-1]) ans=max(ans, cut[i-1]+QUERY(secM[i-1], secM[i]));
    }
    for(i=0 ; i<=4*RES.size() ; i++) T.tree[i]=T.lazy[i]=0;
    cout<<ans; return;
}
 
int main(void)
{
    fio; int i, tc; cin>>tc; T.init();
    for(i=1 ; i<=tc ; i++)
    {
        cout<<"Case #"<<i<<"\n";
        solve(); cout<<"\n";
    }
    return 0;
}
cs

5. 삼각형의 거리


볼록다각형의 경우 작년 ICPC 기출문제다. 그대로 제출하면 47점이다.


이제 본격적으로 문제를 해결해보자. 답에 대하여 이분탐색을 하자. 답이 $m$ 이하가 될 수 있는지 판별하자.

정점을 반시계 순서대로 $v_1, v_2, \cdots, v_n$이라고 하자. 

각 $i<j$에 대하여 $P_{i, j}$를 $v_i, v_{i+1}, \cdots , v_j$로 이루어진 다각형이라고 하자.

단, $v_i v_j$가 문제에서 주어진 다각형 내부에 완전히 위치해야 한다.


이제 $DP[i][j]$를 $P_{i, j}$를 지름을 $m$ 이하로 삼각분할 할 때, [$v_iv_j$를 포함하는 삼각형에서 가장 먼 삼각형까지의 거리]로 가능한 것 중 최솟값에 $1$을 더한 값이라고 하자. 만약 조건을 만족하는 삼각분할이 불가능하면 $\infty$라 하자.


$DP[i][j]$를 계산하기 위해, 점화식을 설계하자. $k \in [i+1, j-1]$을 하나 잡고 $v_i v_k v_j$가 정당한 삼각형인지를 판별하자.

만약 정당하다면, $v_iv_jv_k$와 $P_{i, k}$의 삼각분할, $P_{k, j}$의 삼각분할로 구성된 $P_{i, j}$의 삼각분할을 생각할 수 있다.

이 경우 지름은 $DP[i][k] + DP[k][j]$가 되며, 이 값이 $m$ 초과인 경우 실패라고 볼 수 있다.

성공이라면, $DP[i][j]$로 가능한 값 중 하나는 $\text{max}(DP[i][k], DP[k][j]) + 1$이 된다. 이를 업데이트 하자.


이렇게 되면 고려해야 할 $DP$ 상태는 $\mathcal{O}(n^2)$, 전이 시간복잡도도 $\mathcal{O}(n^3)$이다.


이제 본격적으로 기하적 부분을 처리해야 한다. 고통스러웠다 :(

$v_i v_k v_j$가 정당한 삼각형인지 판별하는 것은 각 변이 주어진 다각형 안에 속하는지만 판별해도 된다.

이제 선분 $v_iv_j$가 주어진 다각형 안에 속하는지 판별하는 방법을 생각해보자.

우선 다각형의 선분들 중 $v_i v_j$와 만나는 것은 없어야 한다. (끝점 제외)

이 판별이 끝나면, $v_i v_j$는 전부 다각형 내부에 속하거나 전부 다각형 외부에 속한다.

그러니, $v_iv_j$의 중점을 잡고 다각형 내부에 속하는지 판별하면 끝난다!

Point in Polygon은 ray casting algorithm으로 하면 되며, 설명은 여기를 참고하자. 


중점을 계산해야 하는데 소수점 나오면 기분이 나쁘니 모든 좌표를 2배해서 계산을 편하게 하자.


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
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
ll inf=1e9;
 
struct point_2d // ll
{
    ll x, y;
    point_2d() {}
    point_2d(ll x, ll y): x(x), y(y) {}
    bool operator==(const point_2d &t) { return x==t.x && y==t.y; }
    point_2d& operator+=(const point_2d &t) { x+=t.x; y+=t.y; return *this; }
    point_2d& operator-=(const point_2d &t) { x-=t.x; y-=t.y; return *this; }
    point_2d& operator*=(const ll t) { x*=t; y*=t; return *this; }
    point_2d& operator/=(const ll t) { x/=t; y/=t; return *this; }
    point_2d operator+(const point_2d &t) const { return point_2d(*this)+=t; }
    point_2d operator-(const point_2d &t) const { return point_2d(*this)-=t; }
    point_2d operator*(const ll t) const { return point_2d(*this)*=t; }
    point_2d operator/(const ll t) const { return point_2d(*this)/=t; }
    ll cross(const point_2d &t) const { return x*t.y-y*t.x; }
    ll cross(const point_2d &a, const point_2d &b) const { return (a-(*this)).cross(b-(*this)); }
};
 
bool inter_1d(ll a, ll b, ll c, ll d) 
{
    if(a>b) swap(a, b);
    if(c>d) swap(c, d);
    return max(a,c)<=min(b,d);
}
 
int sgn(ll x)
{
    if(x>0return 1;
    if(x==0return 0;
    if(x<0return -1;
}
 
bool check_inter(point_2d a, point_2d b, point_2d c, point_2d d)
{
    if(c.cross(a,d)==0 && c.cross(b,d)==0 && c.cross(a,b)==0// a, b, c, d colinear
        return inter_1d(a.x,b.x,c.x,d.x) && inter_1d(a.y,b.y,c.y,d.y);
    return sgn(a.cross(b,c))!=sgn(a.cross(b,d)) && sgn(c.cross(d,a))!=sgn(c.cross(d,b));
}
 
int n;
point_2d pt[333];
int isok[311][311];
int dp[311][311];
 
bool chk(int x)
{
    int i, j, k, inf=1e9;
    for(i=1 ; i<=n-1 ; i++)
    {
        for(j=1 ; j<=n-i ; j++)
        {
            if(i==1) { dp[j][j+i]=0continue; } 
            if(isok[j][j+i]==0) { dp[j][j+i]=inf; continue; }
            dp[j][j+i]=inf;
            for(k=j+1 ; k<=j+i-1 ; k++)
            {
                if(isok[j][k]==0 || isok[k][j+i]==0continue;
                if(dp[j][k]+dp[k][j+i]>x) continue;
                dp[j][j+i]=min(dp[j][j+i], max(dp[j][k], dp[k][j+i])+1);
            }
        }
    }
    if(dp[1][n]<5000return truereturn false;
}
 
bool inConcave(point_2d X)
{
    int i, cnt=0;
    point_2d Y; Y.x=inf+1; Y.y=X.y+1;
    for(i=1 ; i<=n ; i++if(pt[i]==X) return true;
    for(i=1 ; i<=n ; i++
        if(check_inter(pt[i], pt[i%n+1], X, Y)) cnt++;
    return cnt%2==1;
}
 
int chk(int u, int v)
{
    if(v==u+1 || (u==1 && v==n)) return 1;
    for(int i=1 ; i<=n ; i++)
    {
        if(i==|| i%n+1==|| i==|| i%n+1==v) continue;
        if(check_inter(pt[u], pt[v], pt[i], pt[i%n+1])) return 0;
    }
    point_2d TT; TT.x=(pt[u].x+pt[v].x)/2; TT.y=(pt[u].y+pt[v].y)/2;
    if(!inConcave(TT)) return 0return 1;
}
 
void solve(void)
{
    int i, j, k; cin>>n;
    for(i=1 ; i<=n ; i++cin>>pt[i].x>>pt[i].y;
    for(i=1 ; i<=n ; i++) pt[i]*=2;
    if(n==3) { cout<<0return; }
    if(n==4) { cout<<1return; }
    for(i=1 ; i<=n ; i++)
        for(j=i+1 ; j<=n ; j++)
            isok[i][j]=chk(i, j);
    int lef=0, rig=n, mid, best=n; 
    while(lef<=rig)
    {
        mid=(lef+rig)/2;
        if(chk(mid)) best=mid, rig=mid-1;
        else lef=mid+1;
    }
    cout<<best; return;
}
 
int main(void)
{
    fio; int i, tc; cin>>tc;
    for(i=1 ; i<=tc ; i++)
    {
        cout<<"Case #"<<i<<"\n";
        solve(); cout<<"\n";
    }
    return 0;
}
cs


'PS > 대회 후기' 카테고리의 다른 글

SCPC 2020 본선 후기  (5) 2020.11.09
ACM-ICPC Seoul Regional Preliminary 2020  (0) 2020.10.19
SCPC 2020 2차 예선 풀이  (1) 2020.09.05
SCPC 2020 1차 예선 풀이  (0) 2020.08.22
APIO 2020 Open Contest  (0) 2020.08.22
ACM-ICPC Seoul Regional 2019  (0) 2019.11.11
  1. Sait2000 2020.09.05 21:04

    :god:

    저도 3번 TL 났는데 좌표압축 할 때 인덱스 같이 넣고 정렬해서 lower_bound 안 하니까 통과했네요

아침에 일어나서 1, 2, 3번 풀고 밥 먹고 씻고 4, 5번 풀었다. 4번에서 뇌절한 거 빼고 괜찮았다.


대회가 대회인만큼 풀이는 최대한 자세하게, 코드까지 포함해서 작성한다.


1번. 다이어트


당연하게도 각 식당의 메뉴 중 가장 작은 $K$개를 먹어야 하는데, 짝을 잘 지어주는 것이 중요하다.

직관적으로 A 식당에서 칼로리가 많은 것을 B 식당에서 칼로리가 적은 것과 함께 먹어야 하고, 이는 실제로 정당한 풀이다.

증명하는 방법에는 여러 가지가 있을 수 있는데, 가장 쉬운 것은 exchange argument인 것 같다.

만약 $a_i < a_j$, $b_k < b_l$이 있어 $(a_i, b_k)$, $(a_j, b_l)$이 서로 짝을 이루고 있다면, 이를 $(a_i, b_l)$, $(a_j, b_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
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef long double ldb;
typedef complex<double> base;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const bool debug=false
const int mod=998244353;
 
ll a[222222], b[222222], n, k, ans;
 
void solve(void)
{
    int i; cin>>n>>k; ans=0;
    for(i=1 ; i<=n ; i++cin>>a[i]; sort(a+1, a+n+1);
    for(i=1 ; i<=n ; i++cin>>b[i]; sort(b+1, b+n+1);
    for(i=1 ; i<=k ; i++) ans=max(ans, a[i]+b[k+1-i]);
    cout<<ans;
}
 
int main(void)
{
    fio; int tc; cin>>tc;
    for(int i=1 ; i<=tc ; i++)
    {
        cout<<"Case #"<<i<<"\n";
        solve(); cout<<"\n";
    }
    return 0;
}
cs


2번. 카드 게임


(초고난이도 문제를 제외한) 게임 문제는 대부분 전형적인 풀이를 갖는다. 가장 대표적인 풀이는 특정 상태를 "선공승", "후공승"으로 분류하고, 이 상태를 동적 계획법으로 계산하는 것이다. 특정 상태가 선공승이 되려면, 선공이 도달할 수 있는 상태 중 하나라도 후공승이면 된다. 반대로, 특정 상태가 후공승이 되려면, 선공이 도달할 수 있는 상태가 모두 선공승이면 된다. 이를 기반으로 동적계획법 풀이를 생각해보자. $dp[i][j]$란 더미 $X$에서 아래 $i$개의 카드, 더미 $Y$에서 아래 $j$개의 카드가 남았을 때 선공승인지, 후공승인지 여부라고 하자. 선공승이면 1, 아니면 0이다. 이제 각 상태에서 선공이 할 수 있는 움직임을 따져보자.


$(i, j)$라는 상태에 있다면, $X[t+1] + \cdots + X[i] \le k$을 만족하는 $t$에 대하여 $(t, j)$로 이동할 수 있다.

또한, $Y[t+1] + \cdots + Y[j] \le k$를 만족하는 $t$에 대하여 $(i, t)$로 이동할 수 있다. 

이러한 조건을 만족하는 $t$는 하나의 구간을 이루므로, 부분합 배열을 추가하여 각 DP 값을 $\mathcal{O}(1)$에 해결할 수 있다.


예를 들어, $X[t+1] + \cdots + X[i] \le k$를 만족하는 $t$가 $[u, i-1]$이라고 하자.

그러면 우리가 확인할 것은 $dp[u][j], dp[u+1][j], \cdots, dp[i-1][j]$ 중 $0$인 것이 존재하냐는 것이다.

이는 $dp[u][j]$부터 $dp[i-1][j]$까지의 합이 $i-u$와 같은지 파악하는 것과 같으며, 이는 부분합으로 가능하다.

$Y$의 경우도 마찬가지다. 또한, 이때 조건을 만족하는 $t$의 범위는 $X, Y$에 대한 부분합과 lower_bound 등으로 쉽게 구할 수 있다. 


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
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef long double ldb;
typedef complex<double> base;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const bool debug=false
const int mod=998244353;
 
int n, k, ans_1, ans_2;
int a[3333], b[3333];
int psa[3333], psb[3333];
int cuta[3333], cutb[3333];
int dp[3005][3005]; // first start, who wins?
int psx[3005][3005];
int psy[3005][3005];
 
void solve(void)
{
    int i, j, c; cin>>n>>k; ans_1=0, ans_2=0;
    for(i=1 ; i<=n ; i++cin>>a[i];
    for(i=1 ; i<=n ; i++cin>>b[i];
    for(i=1 ; i<=n ; i++) psa[i]=psa[i-1]+a[i];
    for(i=1 ; i<=n ; i++) psb[i]=psb[i-1]+b[i];
    for(i=0 ; i<=n ; i++)
    {
        cuta[i]=lower_bound(psa, psa+n+1, psa[i]-k)-psa;
        cutb[i]=lower_bound(psb, psb+n+1, psb[i]-k)-psb;
    }
    dp[0][0]=1; psx[0][0]=1; psy[0][0]=1;
    for(i=0 ; i<=n ; i++)
    {
        for(j=0 ; j<=n ; j++)
        {
            if(i==0 && j==0continue;
            bool canfin=false;
            if(i>=1)
            {
                int totlose=psx[i-1][j];
                if(cuta[i]>=1) totlose-=psx[cuta[i]-1][j];
                int totpos=i-cuta[i];
                if(totlose<totpos) canfin=true;
            }
            if(j>=1)
            {
                int totlose=psy[i][j-1];
                if(cutb[j]>=1) totlose-=psy[i][cutb[j]-1];
                int totpos=j-cutb[j];
                if(totlose<totpos) canfin=true;
            }
            if(canfin) dp[i][j]=1;
            else dp[i][j]=0;
            psx[i][j]=(i>=1?psx[i-1][j]:0)+dp[i][j];
            psy[i][j]=(j>=1?psy[i][j-1]:0)+dp[i][j];
        }
    }
    for(i=0 ; i<=n ; i++)
    {
        for(j=0 ; j<=n ; j++)
        {
            if(dp[i][j]) ans_1++;
            else ans_2++;
        }
    }
    cout<<ans_1<<" "<<ans_2;
}
 
int main(void)
{
    fio; int i, tc; cin>>tc;
    for(i=1 ; i<=tc ; i++)
    {
        cout<<"Case #"<<i<<"\n";
        solve(); cout<<"\n";
    }
    return 0;
}
cs


3번. 사다리 게임


$N$의 범위가 작으므로, 아예 $i$에서 $j$로 가기 위한 최소 간선 삭제 횟수를 $dp[i][j]$라고 정의하자. 이를 전부 구하는 것을 목표로 한다.

초깃값을 설정해야 하는데, $dp[i][i]=0$, $dp[i][j] = \infty$ ($j \neq i$) 가 된다. 이제 DP 업데이트를 어떻게 하는지 생각하자.


만약 $u, v$를 연결하는 간선이 있다면, $u$로 도착한 경로는 강제로 $v$로 가게 된다. 반대 역시 마찬가지.

그러니 $dp[i][u] = \text{min}(dp[i][u]+1, dp[i][v])$, $dp[i][v]=\text{min}(dp[i][v]+1, dp[i][u])$가 성립하게 된다.

물론, 이 업데이트를 순서대로 하면 안되고, 동시에 적용해야 한다. 그러니 업데이트가 간선 하나 당 $\mathcal{O}(N)$이다.


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
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef long double ldb;
typedef complex<double> base;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const bool debug=false
const int mod=998244353;
 
ll ans=0;
int n, k, m, inf=1e9;
int dp[1511][1511];
 
void solve(void)
{
    int i, j, u, v, a, b; ans=0cin>>n>>k>>m;
    for(i=1 ; i<=n ; i++)
        for(j=1 ; j<=n ; j++)
            dp[i][j]=inf;
    for(i=1 ; i<=n ; i++) dp[i][i]=0;
    while(k--)
    {
        cin>>u>>v;
        for(i=1 ; i<=n ; i++)
        {
            a=dp[i][u]; b=dp[i][v];
            dp[i][u]=min(a+1, b);
            dp[i][v]=min(b+1, a);
        }
    }
    while(m--)
    {
        cin>>u>>v;
        if(dp[u][v]==inf) ans--;
        else ans+=dp[u][v];
    }
    cout<<ans;
}
 
int main(void)
{
    fio; int i, tc; cin>>tc;
    for(i=1 ; i<=tc ; i++)
    {
        cout<<"Case #"<<i<<"\n";
        solve(); cout<<"\n";
    }
    return 0;
}
cs


4번. 범위 안의 숫자


뭔가 지나치게 어렵게 푼 것 같다. 고생도 많이했다. 이상한 실수해서 제출횟수도 날리고 ㅋㅋ


우리가 해야 할 일은, 어떤 정수를 추가하고, 삭제하고, 길이 $m$ 구간에 속하는 정수의 최대 개수를 구하는 것이다.

여기서 첫 관찰은, 집합에 존재하는 정수로 시작하는 구간만을 생각해도 충분하다는 것이다. 이는 자명한 사실이므로 설명 생략.

먼저 집합에 등장할 수 있는 정수들을 전부 구하고, 이들을 정렬한 상태로 보관하자. 총 $\mathcal{O}(nk)$개가 있다.

이제 각 정수에 대하여 "그 정수로 시작하는 길이 $m$ 구간에 속한 정수의 개수"를 세그먼트 트리로 관리해보자.

특정 정수를 추가/삭제하면, 그에 따라 영향을 받는 값의 index는 하나의 구간을 이룬다. 이제 해결의 실마리가 나온다.

필요한 것은 구간에 1을 더하는 것, 1을 빼는 것, 그리고 전체의 최댓값을 구하는 연산이다. 모두 lazy propagation으로 가능하다.

하지만 이 풀이는 시간 초과가 난다. (아니라는 말도 있다) $nk$가 생각보다 크고, lazy propagation은 상수가 꽤 크기 때문이다.


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
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef long double ldb;
typedef complex<double> base;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const bool debug=false
const int mod=998244353;
 
struct SegmentTree
{
    int tree[2288888];
    int lazy[2288888];
    void build(void) { memset(tree, 0sizeof(tree)); memset(lazy, 0sizeof(lazy)); }
    void workdown(int index, int s, int e)
    {
        if(s!=e)
        {
            lazy[index<<1]+=lazy[index];
            tree[index<<1]+=lazy[index];
            lazy[index<<1|1]+=lazy[index];
            tree[index<<1|1]+=lazy[index];
        }
        lazy[index]=0;
    }
    void update(int index, int s, int e, int l, int r, int v)
    {
        if(l>|| r<s) return
        workdown(index,s,e); 
        if(l<=&& e<=r) 
        {
            lazy[index]+=v;
            tree[index]+=v;
            return;
        }
        int m=(s+e)>>1;
        update(index<<1,s,m,l,r,v); 
        update(index<<1|1,m+1,e,l,r,v); 
        tree[index]=max(tree[index<<1], tree[index<<1|1]);
    }
    int eval(int index, int s, int e, int l, int r)
    {
        if(l>|| r<s) return -1e9;
        workdown(index, s, e);
        if(l<=&& e<=r) return tree[index]; int m=(s+e)>>1;
        int ret=max(eval(index<<1,s,m,l,r), eval(index<<1|1,m+1,e,l,r)); 
        tree[index]=max(tree[index<<1], tree[index<<1|1]); 
        return ret; 
    }
} ST;
 
string s; int c[51111];
int ans, n, m, k, pt[10];
 
vector<int> POS;
vector<int> RNG;
 
void ins(int x)
{
    POS.push_back(x);
    for(int i=0 ; i<k ; i++) POS.push_back(x-x%pt[i+1]+x%pt[i]+pt[i]);
}
 
void upd(int x, int v)
{
    int tt=lower_bound(POS.begin(), POS.end(), x)-POS.begin();
    ST.update(11, POS.size(), RNG[tt]+1, tt+1, v);
}
 
void rv(int loc, int v)
{
    int i, ini=0;
    for(i=max(1, loc-k+1) ; i<=max(1, loc-k+1)+k-1 ; i++) ini=10*ini+c[i]; upd(ini, v);
    for(i=max(1, loc-k+1)+k ; i<=min(loc+k-1, n) ; i++) { ini=10*(ini-((c[i-k]*pt[k-1])))+c[i]; upd(ini, v); }
}
 
void solve(void)
{
    int i, j, ini=0, et; ans=0
    cin>>n>>k>>m>>s;
    POS.clear(); RNG.clear(); ST.build(); 
    pt[0]=1for(i=1 ; i<=k ; i++) pt[i]=10*pt[i-1];
    for(i=1 ; i<=n ; i++) c[i]=s[i-1]-'0';
    for(i=1 ; i<=k ; i++) ini=10*ini+c[i]; ins(ini);
    for(i=k+1 ; i<=n ; i++) { ini=10*(ini-((c[i-k]*pt[k-1])))+c[i]; ins(ini); }
    sort(POS.begin(), POS.end()); POS.erase(unique(POS.begin(), POS.end()), POS.end()); RNG.resize(POS.size());
    for(i=0 ; i<POS.size() ; i++) RNG[i]=lower_bound(POS.begin(), POS.end(), POS[i]-m)-POS.begin();
    ini=0for(i=1 ; i<=k ; i++) ini=10*ini+c[i]; upd(ini, 1);
    for(i=k+1 ; i<=n ; i++) { ini=10*(ini-((c[i-k]*pt[k-1])))+c[i]; upd(ini, 1); }
    ans=max(ans, ST.eval(11, POS.size(), 1, POS.size()));
    for(i=1 ; i<=n ; i++
    {
         rv(i, -1); et=c[i]; c[i]=1
         rv(i, 1); ans=max(ans, ST.eval(11, POS.size(), 1, POS.size())); 
         rv(i, -1); c[i]=et; rv(i, 1); 
    }
    cout<<ans; return;
}
 
int main(void)
{
    fio; int i, tc; cin>>tc;
    for(i=1 ; i<=tc ; i++)
    {
        cout<<"Case #"<<i<<"\n";
        solve(); cout<<"\n";
    }
    return 0;
}
cs


그래서 최적화를 할 방법을 생각했다. 사실 가장 중요한 부분은, 각 업데이트 이후 확인해야 하는 구간이 많이 겹친다는 것이다. 

숫자를 1로 바꾸기 전, 초기 $n-k+1$개의 정수 중 실제로 변화하는 것은 많아야 $k$개다. 이 점을 위 코드는 활용하지 않는다.

그러니, 위 레이지 세그먼트 트리를 초기 $n-k+1$개의 정수 중 하나로 시작하는 구간에 대해서만 만들어주자. 이러면 크기가 $\mathcal{O}(nk)$에서 $\mathcal{O}(n)$으로 줄어든다. 이제 우리가 걱정해야 하는 것은 "새로 추가되는 정수로 시작되는 길이 $m$ 구간"에 속하는 정수의 개수를 구하는 것이다. 이 구간에 속하는 정수 역시 "기존 $n-k+1$개의 정수"와 "새로 추가되는 정수"로 구분될 수 있는데, 후자는 단순하게 $\mathcal{O}(k^2)$으로 계산해도 간단한 계산이므로 충분히 빠르다. 전자의 경우, 기존 $n-k+1$개 정수의 등장 횟수를 Fenwick Tree로 관리하면 간단하게 계산할 수 있다. 특정 구간 내에 존재하는 정수의 개수를 구하면 되므로, lower_bound와 Fenwick Tree의 구간 쿼리를 통해서 계산할 수 있다. 시간복잡도는 크게 다르지 않으나, 최적화가 꽤 많이 된 코드이므로 훨씬 빠르다.


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
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef long double ldb;
typedef complex<double> base;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const bool debug=false
const int mod=998244353;
 
struct SegmentTree
{
    int tree[288888];
    int lazy[288888];
    void build(void) { memset(tree, 0sizeof(tree)); memset(lazy, 0sizeof(lazy)); }
    void workdown(int index, int s, int e)
    {
        if(s!=e)
        {
            lazy[index<<1]+=lazy[index];
            tree[index<<1]+=lazy[index];
            lazy[index<<1|1]+=lazy[index];
            tree[index<<1|1]+=lazy[index];
        }
        lazy[index]=0;
    }
    void update(int index, int s, int e, int l, int r, int v)
    {
        if(l>|| r<s) return
        workdown(index,s,e); 
        if(l<=&& e<=r) 
        {
            lazy[index]+=v;
            tree[index]+=v;
            return;
        }
        int m=(s+e)>>1;
        update(index<<1,s,m,l,r,v); 
        update(index<<1|1,m+1,e,l,r,v); 
        tree[index]=max(tree[index<<1], tree[index<<1|1]);
    }
    int eval(int index, int s, int e, int l, int r)
    {
        if(l>|| r<s) return -1e9;
        workdown(index, s, e);
        if(l<=&& e<=r) return tree[index]; int m=(s+e)>>1;
        int ret=max(eval(index<<1,s,m,l,r), eval(index<<1|1,m+1,e,l,r)); 
        tree[index]=max(tree[index<<1], tree[index<<1|1]); 
        return ret; 
    }
} ST;
 
 
struct Fenwick
{
    int tree[111111], C=50000;
    void rset(void) { memset(tree, 0sizeof(tree)); }
    void update(int x, int v) { while(x<=C) { tree[x]+=v; x+=(x&-x); } }
    int query(int x) { int ret=0while(x) { ret+=tree[x]; x-=(x&-x); } return ret; }
    int rquery(int l, int r) { return query(r)-query(l-1); }
} T; 
 
string s; int c[51111];
int ans, n, m, k, pt[10];
 
vector<int> POS;
vector<int> AT;
 
void ins(int x) { POS.push_back(x); }
 
void upd(int x, int v, int ex)
{
    int t_1=lower_bound(POS.begin(), POS.end(), x-m)-POS.begin()+1;
    int t_2=upper_bound(POS.begin(), POS.end(), x)-POS.begin();
    ST.update(11, POS.size(), t_1, t_2, v);
    if(ex) { T.update(t_2, v); }
}
 
void rv(int loc, int v, int ex)
{
    int i, ini=0; AT.clear();
    for(i=max(1, loc-k+1) ; i<=max(1, loc-k+1)+k-1 ; i++) ini=10*ini+c[i]; upd(ini, v, ex); if(v==1 && ex==0) AT.push_back(ini);
    for(i=max(1, loc-k+1)+k ; i<=min(loc+k-1, n) ; i++) { ini=10*(ini-((c[i-k]*pt[k-1])))+c[i]; upd(ini, v, ex); if(v==1 && ex==0) AT.push_back(ini); }
}
 
void do_fun_work(void)
{
    int i, j, ac;
    for(i=0 ; i<AT.size() ; i++)
    {
        int t_1=lower_bound(POS.begin(), POS.end(), AT[i])-POS.begin()+1;
        int t_2=upper_bound(POS.begin(), POS.end(), AT[i]+m)-POS.begin();
        ac=T.rquery(t_1, t_2);
        for(j=0 ; j<AT.size() ; j++if(AT[i]<=AT[j] && AT[j]<=AT[i]+m) ac++;
        ans=max(ans, ac);
    }
}
 
void solve(void)
{
    int i, j, ini=0, et; ans=0
    cin>>n>>k>>m>>s;
    POS.clear(); ST.build(); T.rset();
    pt[0]=1for(i=1 ; i<=k ; i++) pt[i]=10*pt[i-1];
    for(i=1 ; i<=n ; i++) c[i]=s[i-1]-'0';
    for(i=1 ; i<=k ; i++) ini=10*ini+c[i]; ins(ini);
    for(i=k+1 ; i<=n ; i++) { ini=10*(ini-((c[i-k]*pt[k-1])))+c[i]; ins(ini); }
    sort(POS.begin(), POS.end()); POS.erase(unique(POS.begin(), POS.end()), POS.end());
    ini=0for(i=1 ; i<=k ; i++) ini=10*ini+c[i]; upd(ini, 11);
    for(i=k+1 ; i<=n ; i++) { ini=10*(ini-((c[i-k]*pt[k-1])))+c[i]; upd(ini, 11); }
    ans=max(ans, ST.eval(11, POS.size(), 1, POS.size())); 
    for(i=1 ; i<=n ; i++)
    {
        rv(i, -11); et=c[i]; c[i]=1
         rv(i, 10); ans=max(ans, ST.eval(11, POS.size(), 1, POS.size())); do_fun_work();
         rv(i, -10); c[i]=et; rv(i, 11); 
    }
    cout<<ans;
}
 
int main(void)
{
    fio; int i, tc; cin>>tc;
    for(i=1 ; i<=tc ; i++)
    {
        cout<<"Case #"<<i<<"\n";
        solve(); cout<<"\n";
    }
    return 0;
}
cs


5번. 우범 지역


평행이동을 통해서 점 $Q$를 원점으로 옮기고 시작하자. 원점을 기준으로 나머지 점들을 각도정렬하자.

컨벡스 헐 안에 $Q$가 있을 확률은 구하기 어렵지만, $Q$가 없을 확률은 구하기 상대적으로 쉽다.

$Q$가 없을 필요충분조건은, 결국 선택한 점들이 이루는 각도 범위가 180도 미만인 것이기 때문이다.

우선 이를 기반으로 답이 $0$인지 아닌지는 쉽게 판단할 수 있다. 이를 먼저 처리해주자.

이제 점들을 각도순으로 $P_1, P_2, \cdots,  P_n$이라 하고, 그 선택 확률을 $p_1, p_2, \cdots , p_n$이라 하자.

각도 범위가 180도 미만인 경우, "시계 방향으로 처음 선택된 정점"을 직관적으로 정의할 수 있다.

위 그림에서는 오른쪽 아래에 있는 정점이 "처음 선택된 정점"이다. 이제 $P_i$가 처음 선택된 정점이라고 하자.

그 후, $P_i$부터 $P_j$까지의 각도 범위가 180도 미만인 최대의 $j$를 선택하자. 여기서 index가 한 바퀴 돌 수 있음에 주의하자. 

이를 쉽게 짜기 위해서는, $P_1, P_2, \cdots , P_n$의 정보를 $P_{n+1} , P_{n+2}, \cdots,  P_{2n}$에 복사해서 사용하면 된다.

이제 이렇게 되면 $P_{j+1}, P_{j+2}, \cdots , P_{i+n-1}$은 사용될 수 없다. 즉, 우리가 만족해야 하는 조건은 다음과 같다.

  • 우선 $P_i$를 선택해야 한다. 그 확률은 $p_i$이다. 

  • $P_{j+1}$부터 $P_{i+n-1}$은 사용되지 않는다. 그 확률은 $(1-p_{j+1}) \cdots (1-p_{i+n-1})$이다.

그러니 두 확률의 곱을 "Q가 컨벡스 헐에 포함되지 않을 확률"에 추가하면 된다. 

또한, 모든 점이 선택되지 않을 확률 역시 추가되어야 한다. 이러면 모든 확률을 중복없이 다루게 된다.

이 풀이의 매우 많은 부분은 $Q$와 $P_i, P_j$가 한 직선 위에 있지 않다는 사실에 기반한다.


위 계산을 효율적으로 할 방법을 생각해보자. 우선 $j$를 계산하는 것은 inchworm의 방식으로 쉽게 할 수 있다.

또한, $1-p$의 연속된 곱을 효율적으로 계산하는 것은 간단한 세그먼트 트리로 할 수 있다.


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
#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef long double ldb;
typedef complex<double> base;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const bool debug=false
const int mod=998244353;
 
ll n, qx, qy, C=210000; ldb tree[444444];
ldb ans, p[222222];
pair< pair<ll, ll>, ldb> PT[222222];
 
ll cross(const pair<ll, ll> &a, const pair<ll, ll> &b) { return a.first*b.second-a.second*b.first; }
 
bool cmp(const pair< pair<ll, ll>, ldb> &X, const pair< pair<ll, ll>, ldb> &Y)
{
    if((X.first>make_pair(0LL, 0LL)) ^ (Y.first>make_pair(0LL, 0LL))) return X.first > Y.first;
    return cross(X.first, Y.first) > 0;
}
 
void update(int loc, ldb t)
{
    loc+=C; tree[loc]=t;
    for( ; loc>1 ; loc>>=1) tree[loc>>1]=tree[loc]*tree[loc^1];
}
 
ldb query(int l, int r)
{
    ldb ret=1.0;
    for(l+=C, r+=C ; l<r ; l>>=1, r>>=1)
    {
        if(l&1) ret=ret*tree[l++];
        if(r&1) ret=ret*tree[--r];
    }
    return ret;
}
 
ldb getR(int L, int R)
{
    if(R<=n) return query(1, L)*query(R+1, n+1);
    if(R>n) return query(R-n+1, L);
}
 
void solve(void)
{
    fio; ll i, j; cin>>n; ans=0.0;
    memset(tree, 0sizeof(tree));
    for(i=1 ; i<=n ; i++cin>>PT[i].first.first;
    for(i=1 ; i<=n ; i++cin>>PT[i].first.second;
    for(i=1 ; i<=n ; i++cin>>PT[i].second;
    cin>>qx>>qy;
    for(i=1 ; i<=n ; i++) PT[i].first.first-=qx;
    for(i=1 ; i<=n ; i++) PT[i].first.second-=qy;
    sort(PT+1, PT+n+1, cmp);
    if(cross(PT[1].first, PT[n].first) > 0) { cout<<0.0return; }
    for(i=1 ; i<=n ; i++) PT[i+n]=PT[i];
    for(i=1 ; i<=2*n ; i++) update(i, 1.0-PT[i].second);
    for(i=1, j=1 ; i<=n ; i++)
    {
        while(j<=2*&& cross(PT[i].first, PT[j].first)>=0) j++; j--;
        ans+=PT[i].second*getR(i, j);
    }    
    ldb tt=1.0;
    for(i=1 ; i<=n ; i++) tt=(tt*(1.0-PT[i].second));
    ans=1.0-ans-tt;
    cout<<fixed<<setprecision(15)<<ans;
}
 
int main(void)
{
    fio; int i, tc; cin>>tc;
    for(i=1 ; i<=tc ; i++)
    {
        cout<<"Case #"<<i<<"\n";
        solve(); cout<<"\n";
    }
    return 0;
}
cs

 


'PS > 대회 후기' 카테고리의 다른 글

ACM-ICPC Seoul Regional Preliminary 2020  (0) 2020.10.19
SCPC 2020 2차 예선 풀이  (1) 2020.09.05
SCPC 2020 1차 예선 풀이  (0) 2020.08.22
APIO 2020 Open Contest  (0) 2020.08.22
ACM-ICPC Seoul Regional 2019  (0) 2019.11.11
나는 코더다 2018 송년대회  (4) 2018.12.22

솔직히 아쉽긴 한데 그래도 완전 망한 성적은 아니어서 만족하는 중. C를 못 푼건 그렇다치고 B는 100 맞았어야 했다.

중간에 바빠서 정신 없었던 것도 있지만 어쨌든 B에 대한 접근이 정해와 조금 많이 떨어져 있어서 100은 못 먹었을 듯.


A. 벽 칠하기


각 길이 $m$ 구간이 "칠하는 것이 가능한 구간"임을 판별할 수 있다면, 그 후의 계산은 간단한 그리디 알고리즘으로 할 수 있다.

이제 이걸 판단하는 것이 중요한데, 이제부터 색깔 $i$를 좋아하는 사람의 집합을 $S_i$라 하자.

그럼 구간 $[i, i+m)$이 색칠 가능한 것은, $t \in S_{C[i]}$, $t+1 \in S_{C[i+1]}$, $\cdots$, $t+m-1 \in S_{C[i+m-1]}$을 만족하는 정수 $t$가 존재하는 것이다. 

모든 인덱스는 $\pmod{m}$으로 본다. 물론, 조건 판별을 이대로하면 고통스러울 것이 뻔하다. 그러니 접근을 바꿔보자.

생각해보면, 저 인덱스들의 차이는 $i-t$로 동일하다는 것을 알 수 있다. 그러니 이를 활용하면 뭔가 보일 것 같다.

즉, $u \in S_{C[v]}$에 대하여 $v-u$의 카운트를 $1$씩 증가시키면, 카운트가 $m$인 정수가 존재하는지 판별하면 된다.

이제 이걸 효율적으로 관리할 방법을 생각해보자. $[0, m)$에서 시작되는 구간을 오른쪽으로 움직여보자.

$[i. i+m)$에서 $[i+1, i+m+1)$로 가려면, $S_{C[i]}$에 있는 정보를 제거하고 $S_{C[i+m]}$의 정보를 추가해야 한다.

우리가 지원해야 하는 연산은 값 하나를 바꾸고, 전체의 최댓값을 뽑아내는 것이다. 이는 세그먼트 트리로 할 수 있다.

또한, 각 $i$에 대하여 $S_{C[i]}$는 $\sqrt{400000}$ 이하이므로, 업데이트 횟수가 $N \sqrt{400000}$ 이하가 된다.

그런데 내 경험상 세그먼트 트리를 붙이면 TLE가 나고, 로그를 떼어내야 AC를 받을 수 있다.

로그를 떼는 방법은 간단한데, 필요한 것이 최댓값이 $m$인지만을 확인하는 것임을 사용하면 된다.

그냥 $c[x]$를 카운트가 $x$인 정수의 개수, $cnt[x]$를 $x$의 카운트 값이라고 정의하면 업데이트가 상수 시간에 된다. 


B. 자매 도시


Subtask 1은 각 연결컴포넌트가 path 아니면 cycle이다. path이면 당연히 실패하며, cycle이면 그 중 간선 길이 최댓값이다.


Subtask 2는 그래프가 매우 특수한 형태를 갖는다. 경우를 나눠서 생각하면 간선 길이 중 최소 3~4개 정도만 생각하면 된다는 사실을 알 수 있다. 

이는 원하는 방식으로 적당히 구현하면 된다. 나는 멀티셋 썼다. 근데 은근 케이스 생각하기 헷갈리긴 했다 ㅋㅋ


Subtask 3, 4를 위해서는 간단한 관찰이 필요한데, 바로 필요충분조건이 연결성 및 (사이클 존재 또는 차수 3 이상 정점 존재)라는 것이다.

물론, 사이클이 단순 사이클이 아니면 차수 3 이상 정점은 무조건 존재하게 되어있다. 이제 생각하기 편하다.

이제 문제를 각 쿼리당 $\mathcal{O}(N+M)$ 시간에 해결할 수 있다. 간선을 작은 것부터 순서대로 이으면서, disjoint set으로 위 사실들을 관리하면 된다. 


Subtask 5를 위해서 나는 트리 DP를 활용했다. 오프라인 풀이가 너무 자명해서 small-to-large 같은 게 먹히나 생각을 했었는데, 뭔가 아닌 것 같아서 트리를 긁기로 했다. 근데 저 방향이 정해여서 너무 아쉽다 ㅋㅋㅋ 트리라도 맞은 걸 다행이라고 생각해야겠다.


여기서 좋은 점은 사이클 존재의 경우를 생각하지 않아도 된다는 것이다. 연결성과 차수 3 이상 정점만 다루면 된다.

연결성을 위한 "최대 간선 길이의 최솟값"과, 차수 3 이상 정점을 위한 "최대 간선 길이의 최솟값"을 구한 뒤 최댓값을 취하자.


첫 번째 문제는 어렵지 않고, 잘 알려진 편이다. MST를 찾아주고, 거기서 경로 최댓값을 찾으면 충분하기 때문이다.

그러니까 단순하게 크루스칼 + Sparse Table을 열심히 구현하면 이 부분을 큰 문제 없이 해결할 수 있다.


두 번째 문제는 엄청 어려운 건 아닌 것 같지만 트리 DP 근본이 없는 수준인 나에게는 힘들었다.

우선 차수 3 이상 정점이 어디서 나올 것인가에 대해서 논의를 할 필요가 있다. 쿼리로 들어온 정점이 $X, Y$라고 하자. 

 

우선 공통된 것이 있다. $X$와 $Y$ 사이의 경로에서 차수 3 이상 정점이 나올 수 있다.

이 정점들은 (단, $X, Y$ 제외) $X, Y$가 연결된 시점에서 이미 차수가 2 이상인 것이 보장되므로, 간선 하나만 더 그으면 끝이다.

여기서 생각을 해보면 중요한 것은 각 정점에서 뻗어나오는 "3번째로 길이가 작은 간선의 길이"가 된다.

그러니 첫 번째 문제와 같은 방법으로 Sparse Table을 적용하면 이 경우를 해결할 수 있다. 


그런데 $X, Y$는 조금 다른 점이 있다. 밑으로 내려갈 수도 있기 때문이다! 잠시 $Z = \text{lca}(X, Y)$라고 하자.

$Z \neq X$라면, 차수 3 정점을 찾기 위해서 $X$에서 트리를 내려가 정점 $W$에 도착한 뒤, $W$에서 가지를 2개 치는 방법이 있다.

이 경우 필요한 최대 길이는 $X$에서 $W$로 내려가는 길이 중 최대, 그리고 $W$의 가지 중 두 번째로 작은 것이 되겠다.

이러한 경로로 가능한 것 중 필요한 최대 길이의 최솟값을 구해야 하는데, 이는 트리 DP로 미리 전처리를 할 수 있다.

$Z \neq Y$인 경우에도 이러한 계산을 하고, 이를 쿼리를 답할 때에 고려해야 한다. 


마지막으로, $Z=X$거나 $Z=Y$인 경우를 생각할 필요가 있다. 이 경우에는 위로 올라갈 수 있다!

앞선 경우와 큰 차이는 없지만, 개인적으로는 조금 헷갈렸다. 비슷한 스타일의 DP를 한 번 더 해주면 된다.


매우 고통스러운 풀이였는데, 이걸 어쨌든 짜서 서브태스크를 긁었다는 게 다행이다. 솔직히 틀릴 것 같았다.


이 풀이를 일반적인 경우로 확장하려고 했는데, 단순 사이클을 다루는 것이 어마어마하게 힘들더라 ㅠㅠ   


C. 즐거운 행로


Subtask 1, 2는 우선 트리 전체의 구조를 $N^2$번의 쿼리로 구한다. (모든 거리를 알면 복원은 자명)

그 후, 트리의 지름을 잡고 가능한 정점 중 가장 먼 곳을 반복적으로 사용하면 된다. 


Subtask 3은 이 과정을 전형적인 이진트리에서 하면 된다. 위 과정을 그대로 적용하되, 트리의 높이가 작다는 점을 이용한다.

그냥 각 정점에 대해서 "내 왼쪽에 있는 정점" / "내 오른쪽에 있는 정점"의 집합을 관리하면 된다. 

'PS > 대회 후기' 카테고리의 다른 글

SCPC 2020 2차 예선 풀이  (1) 2020.09.05
SCPC 2020 1차 예선 풀이  (0) 2020.08.22
APIO 2020 Open Contest  (0) 2020.08.22
ACM-ICPC Seoul Regional 2019  (0) 2019.11.11
나는 코더다 2018 송년대회  (4) 2018.12.22
NYPC 2018 본선 복기 및 후기  (8) 2018.10.28