AtCoder ABC 360

서론

바로 전날에 현대모비스 1차와 팀연습을 좋지 않게 마무리하고 Atcoder를 시작했습니다.

Contest

A - A Healthy Breakfast[+, 1:21]

사용 알고리즘

구현(Implementation)
문자열(String)

문제 상황

R, M, S 가 하나씩 있는 길이 $3$의 문자열이 주어질 때, R이 M보다 먼저인지 검사하는 문제입니다.

풀이

abc A번 치고는 구현할 것이 있는(?) 문제였습니다. 매번 어떤 문자열과 같은지 비교하시오 이런거 나오다가 R의 위치와 S의 위치를 찾아야 하는 문제였습니다. string::find를 사용하여 간단히 풀 수 있었습니다.

void solve(){
    ll i,j,k;
    string str;
    cin>>str;
    if(str.find('R')<str.find('M')){
        yes();
    }
    else{
        no();
    }
}

B - Vertical Reading[+, 5:21]

사용 알고리즘

구현(Implementation)
문자열(String)
브루트포스(Brute Force)

문제 상황

두개의 문자열 $S$와 $T$가 주어집니다. $S$를 길이 $w$씩 잘라서 이차원으로 적고 이를 세로로 읽을 때, 한 열이라도 $T$와 같은 문자열이 있는지 확인하는 문제입니다. 이 때, $w$는 $S$의 길이 \textbf{미만}입니다. 대회 끝나고 알았는데, $\lvert T\rvert < \lvert S\rvert$라는 조건이 처음에 적혀있었으나, 실제로는 $\lvert T\rvert\le \lvert S\rvert$였습니다. 이 이슈가 1시간 넘게 지난 후 수정되었고, 이것 때문에 WA받은 사람이 있어 어떻게 처리할 지 atcoder가 고민하고 있고, Rating 반영이 많이 늦게 되었습니다. 저는 예제를 보고 이해한지라 해당 이슈가 있는 지 몰랐습니다.

풀이

문자열 길이가 $100$이므로 가능한 모든 경우를 해줍니다. $O(\lvert S \rvert^2)$에 해결가능합니다.

void solve(){
    ll i,j,k;
    string s,t;
    cin>>s>>t;
    ll n=s.size();
    for(i=1;i<n;i++){
        vector<string> vct(i);
        for(j=0;j<n;j++){
            vct[j%i]+=s[j];
        }
        if(find(all(vct),t)!=vct.end()){
            yes();
            return;
        }
    }
    no();
}

C - Move It[+, 8:06]

사용 알고리즘

구현(Implementation)
정렬(Sort)

문제 상황

$N$개의 물건이 있고, 각각의 무게와 어떤 상자에 들어있는지 주어집니다. 각 상자별로 물건을 한 개만 남기고 다 빼고 싶을 때, 빼야 하는 무게의 합을 구하는 문제입니다.

풀이

그냥 각 상자별로 무게를 정렬하고, 가장 무거운 것을 제외한 나머지를 더해주면 됩니다. $O(N\log N)$에 해결가능합니다. 개인적으로 B번보다 쉬운 것 같습니다.

굳이 정렬을 하지 않아도, 각 상자별로 가장 무거운 것을 합한 후 전체 합에서 빼주면 $O(N)$에 해결가능합니다.

void solve(){
    ll i,j,k;
    ll n;
    cin>>n;
    vector<ll> arr(n),w(n);
    vector<vector<ll>>rarr(n+1);
    for(i=0;i<n;i++){
        cin>>arr[i];
    }
    for(i=0;i<n;i++){
        cin>>w[i];
    }
    for(i=0;i<n;i++){
        rarr[arr[i]].pb(w[i]);
    }
    for(i=1;i<=n;i++){
        sort(all(rarr[i]));
    }
    ll ans=0;
    for(i=1;i<=n;i++){
        for(j=0;j+1<rarr[i].size();j++){
            ans+=rarr[i][j];
        }
    }
    cout<<ans<<'\n';
}

D - Ghost Ants[+, 14:37]

사용 알고리즘

정렬(Sort)
덱(Deque)

문제 상황

개미들이 일차원 수직선 위 서로 다른 위치에서 왼쪽 혹은 오른쪽을 보고 있습니다. $1$초에 $1$만큼 움직일때, $T+0.1$초 후 만나는 개미 쌍의 수를 구하는 문제입니다. 개미는 서로 만나더라도 서로 통과해 지나갑니다.

풀이

왼쪽을 보는 개미와 오른쪽을 보는 개미는 서로 만날 수 있지만, 서로 같은 방향을 보는 개미는 만나지 않습니다. 우선 예제는 좌표가 다 정렬되어 주어지지만, 실제로는 정렬되지 않은 데이터가 주어지기에 좌표를 먼저 정렬합니다. 이후 좌표가 증가하는 순서대로 개미를 보며, 오른쪽을 보는 개미라면 덱에 넣어주고, 왼쪽을 보는 개미라면 현재 덱에 들어있는 가장 왼쪽의 개미(덱의 front)가 $2T$이하의 거리에 있도록 pop_front를 해줍니다. 그러면 덱에는 현재 좌표에서 $2T$이내에 있는 오른쪽을 보는 개미들만 들어있게 됩니다. 즉, 덱의 크기를 더해주면 됩니다. 정렬에 $O(N\log N)$, 이후 $O(N)$에 해결가능합니다.

void solve(){
    ll i,j,k;
    ll n,m;
    string str;
    cin>>n>>m>>str;
    vector<ant> ants(n);
    for(i=0;i<n;i++){
        cin>>ants[i].x;
        ants[i].dir=str[i]-'0';
    }
    sort(all(ants));
    ll ans=0;
    deque<ll>lef;
    for(i=0;i<n;i++){
        if(ants[i].dir==1){
            lef.push_back(ants[i].x);
        }
        else{
            while(lef.size() && ants[i].x-lef.front()>2*m){
                lef.pop_front();
            }
            ans+=lef.size();
        }
    }
    cout<<ans<<'\n';
}

E - Random Swaps of Balls[+, 26:26]

사용 알고리즘

확률론(Probability)
기댓값의 선형성(Linearity of Expectation)
모듈로 곱셈 역원(Modular Inverse)

문제 상황

$N$개의 공이 있고, $1$번공은 검정색, 나머지는 흰색입니다. $1$이상 $N$이하의 범위에서 Uniform하게 $i$와 $j$를 독립적으로 선택해 두 공을 바꾸는 작업을 $K$번 수행할 때, 최종적으로 검정색 공이 있는 번호의 기댓값을 구하는 문제입니다.

풀이

현재 $x$번에 검정색 공이 있다고 가정하면, 한 번의 작업에 대해 케이스를 네 가지로 나눌 수 있습니다.

$i\ne x$, $j\ne x$: 이 경우에는 $x$번 공이 그대로 있으므로 변화가 없습니다.
$i=x$, $j\ne x$: 이 경우에는 $x$번 공이 $j$번 공으로 이동합니다.
$i\ne x$, $j=x$: 이 경우에는 $i$번 공이 $x$번 공으로 이동합니다.
$i=x$, $j=x$: 이 경우에는 변화가 없습니다.

위의 각각을 살펴보면 1번의 경우 $\frac{(N-1)^2}{N^2}$의 확률로 발생합니다. $y\ne x$에 대해 한 번의 작업 후 검정색 공이 $y$번으로 바뀔 확률은 2, 3번 각각 1가지 경우가 있으므로, $\frac{2}{N^2}$입니다. $x$번에 유지될 확률은 1번 혹은 4번의 경우이므로, $\frac{(N-1)^2+1}{N^2}$입니다.

그런데, $x$번에 유지될 확률을 다르게 해석하여 $\frac{N^2-2N}{N^2}+\frac{2}{N^2}$로 생각하게 되면, 확률/기댓값의 선형성에 따라 다음 두가지 케이스로 해석할 수 있습니다.

검정색 공이 $1$번부터 $N$번까지의 번호에 대해 동일한 $\frac{2}{N^2}$의 확률로 이동합니다. 여기에는 원래 검정공의 위치도 포함됩니다.
$\frac{N^2-2N}{N^2}$의 확률로 공이 $x$번에 유지됩니다.

만약 $K$번의 작업 중 1번이 한번이라도 일어난다면, 모든 번호에 대해 uniform해지기 때문에, 검정색 공이 최종적으로 $i$번의 위치에 있을 확률은 모든 $i$에 대해 $\frac{1}{N}$으로 동일합니다. 즉, 이 경우 기댓값은 $\frac{N+1}{2}$입니다.

만약 $K$번의 작업 중 단 한번도 1번이 일어나지 않으면, 검정색공은 $1$번에 유지됩니다. 이 경우 기댓값은 $1$입니다.

$K$번의 작업 중 단 한번도 1번이 일어나지 않을 확률은 $(\frac{N^2-2N}{N^2})^K$입니다. 즉, 최종적으로 기댓값은 $1\cdot(\frac{N^2-2N}{N^2})^K+\frac{N+1}{2}\cdot(1-(\frac{N^2-2N}{N^2})^K)$입니다. 모듈로 역원을 $O(\lg P)$에 구할 수 있으므로, $O(\lg P)$에 해결가능합니다. AtCoder에서 제공하는 ACL을 처음으로 사용해본 문제였습니다.

+ 이 문제의 더 쉬운 풀이로 $O(K)$ DP가 있습니다. 제한을 보고 DP인가 했지만 DP보다 위의 풀이가 먼저 생각나 이렇게 풀었습니다. 사실 대회 끝나고 changhw(now_cow)의 코드를 보기 전까지 DP 풀이는 생각나지 않았습니다.

void solve(){
    ll i,j,k;
    ll n,m;
    cin>>n>>m;
    ll q=n*n-2*n,p=n*n;
    q%=mod,p%=mod;
    ll prob=q*inv_mod(p,mod)%mod;
    prob=pow_mod(prob,m,mod);
    ll rprob=(1-prob+mod)%mod;
    ll ans=0;
    ans=prob+(1+n)%mod* inv_mod(2,mod)%mod*rprob%mod;
    ans%=mod;
    cout<<ans<<'\n';
}

F - InterSections[-]

사용 알고리즘

세그먼트 트리(Segment Tree)
이분탐색(Binary Search)

문제 상황

두 구간이 \texttt{겹친다}는 것은 두 구간이 abab형태로 exclusive하게 겹친다는 것을 의미합니다. $N$개의 구간이 주어질 때 최대한 많은 구간과 겹치도록 하는 정수 구간을 만드는 문제입니다. 만약 그런 구간이 많다면 $(l,r)$의 사전순으로 가장 작은 구간을 출력합니다.

풀이

가능한 답의 두 끝점은 주어진 구간들의 $l+1$ 혹은 $r+1$ 중 있습니다. 따라서 좌표압축을 시킨 뒤 정렬하고, 원하는 범위에 +, - 시키고 원하는 범위의 최댓값을 찾는 세그를 만든 뒤 우선 모든 구간의 범위를 + 시켜두고, 이후 구간을 정렬해 sweeping하면서 빼주고 하면 됩니다. 대회 끝나고 여러번 제출해봤는데, 아직도 왜틀렸는지 모르겠습니다.

풀이는 에디토리얼과 같고, 심지어 맞은 사람의 코드와 코드도 거의 동일한데 구현을 뭔가 lower_bound, upper_bound나 +1 할 때 안할 때 이런 구분을 잘못한 것 같습니다. $O(N\log N)$에 해결가능합니다.

실제 대회 때는 E푼시점에 F 푼사람 10 언더, G 푼사람 20정도여서 G로 바로 갔습니다.

G - Suitable Edit for LIS[+, 51:42]

사용 알고리즘

LIS(Longest Increasing Subsequence)

문제 상황

수열이 주어질때, 원하는 수 하나를 바꾸어서 LIS(Longest Increasing Subsequence)의 길이를 최대로 만드는 문제입니다.

풀이

수를 하나 바꾸기 때문에 답은 원래 수열의 LIS의 길이 혹은 +1입니다. 그럼 언제 LIS길이 +1이 답이 되는지 살펴보면 다음 경우입니다.

첫번째 혹은 마지막 수 중 하나를 포함하지 않고 LIS를 구했을 때, 원래 수열의 LIS와 길이가 같다면 포함하지 않은 수를 $-\infty$혹은 $\infty$로 바꾸면 +1이 됩니다.
LIS를 적었을 때, LIS의 연속된 두 수의 차이가 $2$이상이고 사이에 다른 수가 있다면, 그 사이에 있는 수를 작은수+1로 바꾸면 +1이 됩니다.

즉, 각각 구해주면 됩니다. 1번 경우는 LIS를 한번씩 더구하면 되고, 2번 경우는 이제 여러 LIS가 있을 수 있는데, 다음과 같이 구하면 됩니다.

먼저, 가능한 LIS 중 최대한 수들이 가장 작은 수열을 구합니다.
이 수를 원래 수열과 인덱스를 매칭시키는데, 이때 인덱스가 가장 작은 수열을 구합니다.
해당 수열에서 검사한 후, 반대로 최대-최대가 되도록 해줍니다.
저는 이 경우는 원래 수열을 뒤집고 음수로 바꾼 다음 위의 과정을 똑같이 진행했습니다.

위의 두 가지 경우(최소-최소, 최대-최대)를 검사하면 되는데, 간단한 증명은 다음과 같습니다.

두 LIS a-b-c와 a-b’-c에 대해
b와 b’간 대소가 있어 일반성을 잃지 않고 $b<b’$이라고 합시다.
- 그렇다면 $a<b<b’<c$가 되고, a와 b’, 그리고 b와 c는 각각 $2$ 이상 차이가 납니다.
- 만약 a와 b’사이에 수가 있다면 해당 수를 a+1로 바꿀 수 있습니다.
- 만약 b와 c사이에 수가 있다면 해당 수를 c-1로 바꿀 수 있습니다.
- 결국, 둘 모두 캡쳐되지 않으려면 a-b’-b-c로 연속된 경우임을 알 수 있습니다.
- 이 경우를 제외하면, 최소-최소, 최대-최대 둘 모두 캡쳐됩니다.
$b=b’$인 경우를 봅시다.
- 그렇다면 $a<b=b<c$인 a-b-b’-c가 됩니다.
- 만약 $a+1=b=c-1$이라면 +1되지 않으므로 문제 없습니다.
- 만약 $a+2\le b$라면 최대-최대에서 LIS가 a-b’-c가 되므로 a-(b->a+1)-b’-c를 잡을 수 있습니다.
- 만약 $b\le c-2$라면 최소-최소에서 LIS가 a-b-c가 되므로 a-b-(b’->c-1)-c+1를 잡을 수 있습니다.

LIS만 잘 구하고 역추적만 잘하면 되므로 $O(N\log N)$에 해결가능합니다.

// 대회 당시 짰던 코드가 너무 더러워서 다시 짰습니다.
void solve(){
    int i,j,k;
    int n;
    cin>>n;
    vector<int>arr(n);
    for(i=0;i<n;i++)cin>>arr[i];
    // find LIS with O(nlogn) with smallest sequence
    auto lis=[](const vector<int>&arr)->vector<int>{
        vector<int>lis;
        vector<int>idx;
        vector<int>prev(arr.size(),-1);
        for(int i=0;i<arr.size();i++){
            auto it=lower_bound(all(lis),arr[i]);
            if(it==lis.end()){
                lis.push_back(arr[i]);
                idx.push_back(i);
                if(idx.size()>1){
                    prev[i]=idx[idx.size()-2];
                }
            }
            else{
                *it=arr[i];
                idx[it-lis.begin()]=i;
                if(it!=lis.begin()){
                    prev[i]=idx[it-lis.begin()-1];
                }
            }
        }
        vector<int>ret;
        int i=idx.back();
        while(i!=-1){
            ret.push_back(arr[i]);
            i=prev[i];
        }
        reverse(all(ret));
        return ret;
    };
    auto check1=[&lis](const vector<int>&arr)->int{
        vector<int>brr=lis(arr);
        if(lis(vector<int>(arr.begin()+1,arr.end())).size()==brr.size()){
            return brr.size()+1;
        }
        else if(lis(vector<int>(arr.begin(),arr.end()-1)).size()==brr.size()){
            return brr.size()+1;
        }
        return 0;
    };
    auto check2=[&lis](const vector<int>&arr)->int{
        vector<int>brr=lis(arr);
        vector<int> lis_idx;
        int now = 0,i;
        for (i = 0; i < brr.size(); i++) {
            while (arr[now] != brr[i])now++;
            lis_idx.push_back(now);
            now++;
        }
        for (i = 0; i < brr.size() - 1; i++) {
            if (brr[i] + 1 == brr[i + 1]) {
                continue;
            } else if (lis_idx[i] + 1 == lis_idx[i + 1]) {
                continue;
            } else {
                return brr.size() + 1;
            }
        }
        return 0;
    };
    int ans;
    if(n>1&&(ans=check1(arr))){
        cout<<ans<<'\n';
    }
    else if(ans=check2(arr)){
        cout<<ans<<'\n';
    }
    else{
        reverse(all(arr));
        for(auto&x:arr)x=-x;
        if(ans=check2(arr)){
            cout<<ans<<'\n';
        }
        else{
            cout<<lis(arr).size()<<'\n';
        }
    }
}

총평

개인적 평가

전날 쳤던 모든 대회/연습이 망해서 걱정했으나 2400퍼폼에 전체 76등이라는 준수한 성적을 거두어 기분이 좋습니다. 두라운드 연속해서 2000+ 퍼폼인 만큼 유지해보도록 해야겠습니다. 아직도 F는 왜틀렸는지 모르겠는데, 혹시 제 코드들 보고 틀린 부분이 있으면 알려주시면 감사하겠습니다.

해당 라운드 평가

B번 문제에 문제가 있어(…) 조금 그런 대회 셋이였습니다. 그걸 차치하고 보더라도 개미 문제나 LIS등 웰노운 문제들을 살짝 변형한 문제들이 많아 아쉽습니다. G가 너무 쉬웠고, 그 중간에 확률문제는 DP말고 수학으로 푸는 버전으로 나왔다면(물론 그럼 F 갈 확률이 높지만) 합니다.