SCPC 2020 본선 후기

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 사용하면 뚝딱.

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

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$ 계산에서 오버플로우에 주의하자.

#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<int, int> 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, 0, sizeof(whi));
    memset(sz, 0, sizeof(sz));
    memset(vis, 0, sizeof(vis));
    for(i=1 ; i<=n ; i++)
        if(!vis[i]) dfs1(i);
    reverse(ord+1, ord+n+1);
    memset(vis, 0, sizeof(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=0; cin>>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, 0, sizeof(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]==0) continue;
                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;
}

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로 정렬하면 사전순 정렬이 됨을 확인할 수 있다. 끝.

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

#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<int, int>, int> > indx;
// which string, location, length
pair<int, int> 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-1) break;
    }
    for(i=0 ; i<LEN ; i++) rk[SA[i]]=i;
    for(i=0, j=0 ; i<LEN ; i++, j=max(j-1, 0))
    {
        if(rk[i]==LEN-1) continue; 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==0) return 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==0) return l;
    if(idx==1) return L[0]+1+l;
    if(idx==2) return 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=0; int rig=RKloc-1; int 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+1; int 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]==0) continue;
        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, 0, sizeof(tree)); indx.clear();
    cin>>s[0]>>s[1]>>s[2]>>k;
    memset(len_odd, 0, sizeof(len_odd));
    memset(len_ev, 0, sizeof(len_ev));
    memset(len_tr, 0, sizeof(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<<endl; return; }
    int tt1=fin[k].first;
    int tt2=fin[k].second;
    for(i=0 ; i<tt2 ; i++) cout<<S[SA[tt1]+i];
    cout<<endl; return;
}
 
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;
}

5. 돌 옮기기

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

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

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

#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, 0, sizeof(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, 0, sizeof(mymask));
    memset(unionmask, 0, sizeof(unionmask));
    memset(actok, 0, sizeof(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=0; int cur1=0; int 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;
}