제1회 청소년 IT경시대회 중등부 후기

그냥 재밌어보여서 쳤다. 아마 9월 16일에 쳤던 것 같다. 원래 후기 안쓰려고 했는데 백준에 문제가 올라와서 간단하게 정리만 하겠다.

백준에 안올라올 줄 알고 코드는 다 지웠어서 다시 짰다.

240305 추가) 1회 난이도는 정올 하위호환 정도라고 생각하면 되고, 특히 1회는 빈집(고수들이 없음)이었기 때문에 275점이 대상이었다.

2회부터는 어떻게 될지 잘 모르겠다.

총점

275/300

만점 노리고 한 대회였는데 A,C를 풀고 B를 못 풀어서 충격먹었다.

 

A

4분인가 걸렸다. 문자열에서 팰린드롬인 가장 긴 suffix를 구해야 한다는 사실을 알아낸다면 쉽게 풀 수 있다.

using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define MOD 1000000007
typedef long long ll;
ll t;
int main(){
    fast;
    cin>>t;
    while(t--){
        string s; cin>>s;
        for(int i = 0 ; i <s.size() ; i++){
            bool f=0;
            for(ll l = i, r = s.size()-1 ; l < r ; l++,r--){
                if(s[l]!=s[r]){
                    f=1;
                    break;
                }
            }
            if(f)continue;
            cout<<s;
            for(int j = i-1 ; j >= 0 ; j--)cout<<s[j];
            cout<<"\n";
            break;
        }
    }
}

 

B

섭태1은 자명하고 섭태2,3은 Ai+Aj가 같은 (i,j)를 싹다 구한 후 좌표압축한다음 잘 비비면 된다

여기까지가 75점이고 여기서 좀 더럽게 처리를 해주면 100점이 나올 것 같은데 왜 안나왔지 ㅑㅐㅗㅈㄷ;히ㅏㅓㅁ해ㅕㅔㅠㅁㅈㄷ훠ㅁ

 

C

HLD로 풀릴 것 같이 생겼다. 근데 중등부에 HLD가 나올리 없다 -> LCA로 풀릴 거 같이 생겼으니 LCA다 라는 기적의 논리로 LCA로 접근하기 시작했다. 그냥 케이스를 나눠서 하면 풀린다. 좀 많이 더러울 뿐이다. (HLD도 되긴 한다.)

간단하게만 설명하면, a->b, c->d를 a->lca(a,b), b->lca(a,b), c->lca(a,b), d->lca(a,b)로 쪼갠다음 각각 (a,c),(a,d),(b,c),(b,d) 쌍에 대하여 경로가 겹치는지를 확인해주면 된다. 그럼 이제 f(a,b,c,d) : a->c, b->d 경로가 겹치는가? 를 판별하는 f만 짜면 되는데 얘는 시작점끼리 포함되는가? 와 도착점끼리 포함되는가? 로 나눠서 열심히 케웍해주면 풀린다.

대회 당시에 왜인진 모르겠는데 f에서 변수를 a랑 b가 아니고 a랑 c를 사용했다. 의식의 흐름이다.

using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define MOD 1000000007
typedef long long ll;
ll n, q;
ll depth[101010];
vector<ll> adj[101010];
bool visited[101010];
ll par[101010][22];
void dfs(ll x, ll y){
    visited[x]=1;
    for(auto next : adj[x]){
        if(!visited[next]){
            depth[next] = y+1;
            par[next][0]=x;
            dfs(next, y+1);
        }
    }
}
ll lca(ll a, ll b){
    if(depth[a]<depth[b])swap(a,b);
    ll diff = depth[a]-depth[b];
    for(int i = 0 ; i < 20 ; i++){
        if(diff&(1<<i))a = par[a][i], diff -= (1<<i);
    }
    if(a==b)return a;
    for(int i = 20 ; i >= 0 ; i--){
        if(par[a][i]!=par[b][i])a = par[a][i], b = par[b][i];
    }
    return par[a][0];
}
bool chk(ll a, ll c, ll l1, ll l2){
    if(a==l1 or c==l2)return 0; //시작점=도착점
    if(a==c){   //같을때
        return 1;
    }
    ll t = lca(a,c);
    if(t==a){   //c가 a에 포함
        if(lca(l2,a) == a)return 0;
        return 1;
    }
    if(t==c){   //a가 c에 포함
        if(lca(l1,c) == c)return 0;
        return 1;
    }
    if(lca(l1,l2) == l1){
        if(lca(t,l2) == t)return 0;
        return 1;
    }
    if(lca(l1,l2) == l2){
        if(lca(t,l1) == t)return 0;
        return 1;
    }
    return 0;
}
int main(){
    fast;
    cin>>n>>q;
    for(int i = 0 ; i < n-1 ; i++){
        ll a,b; cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(1,0);
    for(int j = 1 ; j <= 20 ; j++){
        for(int i = 1 ; i <= n ; i++){
            par[i][j] = par[par[i][j-1]][j-1];
        }
    }
    while(q--){
        ll a,b,c,d; cin>>a>>b>>c>>d;
        if(a==b or c==d){
            cout<<"YES\n";
            continue;
        }
        ll l1 = lca(a,b), l2 = lca(c,d);
        if(chk(a,c,l1,l2) or chk(a,d,l1,l2) or chk(b,c,l1,l2) or chk(b,d,l1,l2)){
            cout<<"NO\n";
        }
        else cout<<"YES\n";
    }
}

이김에 HLD나 공부해볼까? 근데 다음에 센트로이드 하기로 했는데