[Csacademy] Csacademy Round #26 (Div. 2 only) 이야기

오늘은 A, B번 문제를 해결하였고, C번 문제는 1시간 20분 가량 고민을 하다가 결국 답을 못내었다.

레이팅은 1405(-8)로 마무리 하였다.

A, B문제는 15분 내로 쉽게 해결이 되었으나 C번 문제에서 계속 고민을 했다.

A번 문제는 다음과 같다.

A. Limited Vocabulary :: https://csacademy.com/contest/round-26/#task/limited-vocabulary

최대 k개 단어를 포함한 단어 중, 가장 긴 단어를 찾아라.

chk 배열을 두고 그냥 거기에 단어를 넣으면서 총 몇가지 단어가 있나 확인하고, 단어가 k개를 넘으면 다음 단어를 보고

k개를 넘지 않으면 max를 통해 ans에 저장해서 최종적으로 가장 긴 단어를 찾는 문제였다.

이 문제는 O(N)의 시간 복잡도를 가진다. 

#include <iostream>
#include <cstdio>
#include <string>
#include <memory.h>
#include <algorithm>
 
using namespace std;
 
int main()
{
    int n, k;
    int chk[300];
 
    scanf("%d %d", &n, &k);
    string str[101];
 
    for (int i = 0; i < n; i++)
        cin >> str[i];
 
    int ans = -1;
    for (int i = 0; i < n; i++)
    {
        int len = str[i].size();
        memset(chk, 0, sizeof(chk));
        for (int j = 0; j < len; j++)
        {
            char ch = str[i][j];
            chk[(int)ch]++;
                    
        }
        
        // 알파벳 수
        int cnt = 0;
        for (int i = 0; i < 260; i++)
            if (chk[i] >= 1)
                cnt++;
 
        if (cnt > k)
            continue;
 
        ans = max(ans, len);
    }
 
    printf("%d", ans);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

B번 문제는 다음과 같다.

B. Odd Pair Sums :: https://csacademy.com/contest/round-26/#task/odd-pair-sums

인접한 두 수의 합이 짝수면 그 수중 하나를 지워 다음 인접한 두 수의 합이 홀수가 되도록 해야한다.

최소 몇번 지우는 행위를 하여 인접한 모든 수의 합이 홀수가 되도록 할 수 있을까?

구현 문제이다.

다른 트릭이 있을 줄 알았지만 따로 없었고, i와 i + 1번째의 값을 합하여 짝수면 i + 1번째를 지우고 다시 i번째 부터 검사하도록 한다.

시간 복잡도는 O(N) 이다.(i가 머물러 있더라도 erase가 되어 전체 사이즈가 줄기 때문)

#include <iostream>
#include <cstdio>
#include <vector>
 
using namespace std;
 
vector<int> arr;
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
    {
        int val;
        scanf("%d", &val);
 
        arr.push_back(val);
    }
 
    int cnt = 0;
    for (int i = 0; i < arr.size() - 1; i++)
    {
        if ((arr[i] + arr[i + 1]) % 2 == 0)
        {
            cnt++;
            arr.erase(arr.begin() + i + 1);
            i--;
        }
    }
    cout << cnt;
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

못풀었지만 C번 문제에 대해서도 이야기를 해보고자 한다.

C. Bounded Distinct :: https://csacademy.com/contest/round-26/#task/bounded-distinct

L~R 길이를 가진 부분 배열들 중, 수가 정확히 한번씩만 나오는 부분 배열의 총 가지수를 구해라.

보자마자 느껴진 알고리즘은 슬라이딩 윈도우, 투 포인터였다.

하지만 슬라이딩 윈도우를 하기에는 벅찬 감이 있는게 N제한이 10^5라서 시간 복잡도가 O(N^2)이 나오게 된다.

따라서 투 포인터를 통해 O(N)에 해결하고자 하였다.

생각은 여기까지였다..

구현이 너무 어려웠고 정답을 봤는데 왜 이게 답이 되는지도 잘 모르겠다.

#include <iostream>
#include <cstdio>
#include <map>
 
using namespace std;
 
map <int, int> mp;
int v[100001];
 
int main() 
{
    int i, n, l, r, b, e;
    cin >> n >> l >> r;
 
    for (i = 1; i <= n; i++)
        cin >> v[i];
 
    b = e = 1;
    long long ans = 0;
 
    while (b <= n) 
    {
        while (e - b + 1 <= r && e <= n && mp[v[e]] == 0) 
        {
            mp[v[e]]++;
            e++;
        }
 
        if (e - b >= l)
            ans += e - b - l + 1;
 
        mp[v[b]]--;
        b++;
    }
    cout << ans;
    return 0;
}

(출처 :: Job #189092 26 Apr 2017 00:30:20 popovicirobert -- Task Bounded Distinct, Round #26 (Div. 2 only) -- Accepted)

ans += e - b - l + 1과정이 궁금해서 질문을 한 결과 얻은 답은 다음과 같다.

<< because there are (e-b) segments with length ≤ r, so you have to deduct (l-1) from (e-b) so that the length is in [l, r] so it becomes e-b-l+1 >>

행여나 누군가 이 글을 보고 이해하게 된다면 댓글로 알려주시면 정말 감사하겠습니다..

마지막으로 codeforces #401 콘테스트였는데 1번 문제를 푸는데  자꾸 풀리지 않아 화가나서 10번가량 제출하며 틀리면서 풀었다.

마지막에는 결국 코드를 갈아 엎으니 AC를 받게 되었는데, 매우 자신에게 기분이 나빠 따로 후기를 올리지 않았었다.