KOI 2021 1차 후기

 KOI 1차 예선이 끝났다. 예상 점수는 421(수정: 406.8)점으로 만족스럽지는 않지만 그래도 받을 만큼 받은 것 같다. 사실 KOI 1차 대비 셋이 2개가 더 있었는데, 시간 관계상 올리지 않는 것으로 혼자 합의 봤다.

 

 

 1교시

문제가 20개나 있어서 상당히 놀랐지만, 앞쪽의 문제들이 쉬워서 시간이 부족하지는 않았다. 스토리가 있는 문제들만 언급하겠다.

 

10. 중심 노드 찾기 : n*(n-1)/2 로 찍고 검토하지 않아 틀렸다. 그런데 지금 생각해봐도 n-1이 어떻게 가능한지 모르겠다. 조금 생각해보면 쿼리 한 번마다 후보 노드 하나를 제거할 수 있다.

 

12. 사각형 세기 : 이걸 틀려놨다. 24가 너무 적은 것 같은 느낌은 들었지만 눈을 씻고 봐도 더는 안 보였다... 대회 끝나고 보니 큰 다이아 6개가 떡하니 있더라.

 

17. 단조증가 수열 : 보자마자 'BOJ 수열 1, 2' 문제가 떠올랐고, 다이아 문제를 왜 냈는지 의문을 가지며 넘어갔다. 나중에 Slope Trick을 공부했던 기억을 더듬으며 겨우 풀었는데, n이 작아서 그냥 해봐도 답을 구할 수 있었던 것 같다.

 

18. 삼각형 게임 : BOJ의 '다각형 게임'이 떠올랐는데 스프라그-그런디 정리를 써먹진 못했다. 아무리 해봐도 AI가 계속 이기길래 그냥 못 이기는 줄 알고 넘어갔다. (진짜로 못 이기는 줄 알았다.) 그런데 다른 문제를 다 풀고 시간이 남아서 막 해보던 중에 갑자기 이겼다.(...)

 

19. 팀 구성 : 좌측 상단에서 2, 3, -4를 포함할 생각을 못해서 소문제 3개를 틀렸다... 왜 당연히 -1도 포함해야 된다고 생각했을까.

 

20. 2행 정렬 : 네이브하게 되는데 왜 14점이지...?

 

 

2교시

체감 난이도는 ( 1, 2, 3 ) = ( 브론즈1 / 골드4 / ??? ) 정도였다. 3번은 풀이를 보니 플레 5~4 정도 되는 것 같다.

 

 

1. 단순 식 정리 수학 문제. ( ~00:08 )

 

#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
int main()
{
    fastio;
    int tc; cin >> tc;
    while(tc--){
        ll n,m,k,d;
        cin >> n >> m >> k >> d;
        ll p=k*n*m*(m-1)/2+m*m*n*(n-1)/2;
        if(p>d){
            cout << "-1\n";
            continue;
        }
        ll q=d/p;
        cout << q*p << '\n';
    }
}

 

 

 

2. 순서가 중요하지 않은데 순서를 왜 따지라고 하는건지 고민하다가 시간만 날렸다. 정렬 후 그리디. 벡터 4개를 한 번에 관리해주는게 조금 귀찮다. 분수 비교를 double로 하다가 70점을 받았는데, long double을 쓰면 맞는 것 같다. ( ~00:35 )

 

#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define X first
#define Y second
typedef long long ll;
typedef pair<ll,ll> pll;
bool cmp(pll p1,pll p2)
{
    return (__int128)p1.X*p2.Y>(__int128)p2.X*p1.Y;
}
int main()
{
    fastio;
    int n,k;
    cin >> n >> k;
    ll a[4];
    cin >> a[0] >> a[1] >> a[2] >> a[3];
    vector<ll> x[4];
    for(int i=0;i<n;i++){
        char c; ll k;
        cin >> c >> k;
        if(c=='A') x[0].push_back(k);
        if(c=='B') x[1].push_back(k);
        if(c=='C') x[2].push_back(k);
        if(c=='D') x[3].push_back(k);
    }
    for(int i=0;i<4;i++) sort(x[i].begin(),x[i].end(),greater<ll>());
    int it[4]={};
    while(k--){
        pll ans={0,1}; int idx=-1;
        for(int i=0;i<4;i++){
            if(it[i]==x[i].size()) continue;
            ll v=x[i][it[i]];
            pll cur={a[i]+v,a[i]};
            if(cmp(cur,ans)) ans=cur, idx=i;
        }
        if(idx==0) cout << "A ";
        if(idx==1) cout << "B ";
        if(idx==2) cout << "C ";
        if(idx==3) cout << "D ";
        cout << x[idx][it[idx]] << '\n';
        a[idx]+=x[idx][it[idx]];
        it[idx]++;
    }
}

 

 

 

3. 제목부터 절망적인 문자열 문제다. 정해는 O(N)에 가까운 시간복잡도일텐데, O(N^2)조차도 생각이 안나서 테케나 열심히 긁었다. Naive로 56점이 긁힌다는데, 아무리 긁어도 32점이 한계였다. ( ~01:40 )

 

TC 1 :

#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define X first
#define Y second
typedef long long ll;
typedef pair<ll,ll> pll;
int main()
{
    fastio;
    int tc; cin >> tc;
    while(tc--){
        string x,y,w;
        cin >> x >> y >> w;
        char c=w[0];
        int x1=-1,x2=-1,y1=-1,y2=-1;
        for(int i=0;i<x.size();i++) if(x[i]==c) {
            if(x1==-1) x1=i;
            x2=i;
        }
        for(int i=0;i<y.size();i++) if(y[i]==c) {
            if(y1==-1) y1=i;
            y2=i;
        }
        bool cx1[26]={},cx2[26]={},cy1[26]={},cy2[26]={};
        for(int i=0;i<x2;i++) cx1[x[i]-'a']=1;
        for(int i=x1+1;i<x.size();i++) cx2[x[i]-'a']=1;
        for(int i=0;i<y2;i++) cy1[y[i]-'a']=1;
        for(int i=y1+1;i<y.size();i++) cy2[y[i]-'a']=1;
        bool can=0;
        for(int i=0;i<26;i++){
            if(cx1[i]&&cy1[i]) can=1;
            if(cx2[i]&&cy2[i]) can=1;
        }
        cout << (can?'1':'0') << '\n';
    }
}

 

TC 2 :

#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define X first
#define Y second
typedef long long ll;
typedef pair<ll,ll> pll;
string x,y,w;
bool cx(int idx,char c)
{
    int wi=0;
    for(int i=0;i<x.size();i++){
        if(wi==w.size()&&idx==-1) break;
        if(wi==idx){
            if(c==x[i]) idx=-1;
        }
        else{
            if(wi==w.size()) break;
            if(w[wi]==x[i]) wi++;
        }
    }
    if(wi==w.size()&&idx==-1) return true;
    else return false;
}
bool cy(int idx,char c)
{
    int wi=0;
    for(int i=0;i<y.size();i++){
        if(wi==w.size()&&idx==-1) break;
        if(wi==idx){
            if(c==y[i]) idx=-1;
        }
        else{
            if(wi==w.size()) break;
            if(w[wi]==y[i]) wi++;
        }
    }
    if(wi==w.size()&&idx==-1) return true;
    else return false;
}
int main()
{
    fastio;
    int tc; cin >> tc;
    while(tc--){
        cin >> x >> y >> w;
        bool can=false;
        for(int i=0;i<=w.size();i++){
            for(int j=0;j<26;j++)
                if(cx(i,'a'+j)&&cy(i,'a'+j)) {
                    can=true;
                    break;
                }
            if(can) break;
        }
        cout << (can?"1":"0") << '\n';
    }
}