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
ACM-ICPC Seoul Regional Preliminary 2020  (0) 2020.10.19
SCPC 2020 2차 예선 풀이  (1) 2020.09.05
SCPC 2020 1차 예선 풀이  (0) 2020.08.22