Codeforces Round #650 (Div. 3)

[Contests] : Codeforces Round #650 (Div. 3)

 

아주 오랜만에 코드포스 콘테스트를 치러봤다 역시나 초보.. 답게  2문제를 풀었다

11: 45분쯤에 들어가 10분 안되게 늦게 풀기 시작했다 1~2번은 항상 빠르게 풀린다

나만 그런 것이 아니고 나와 비슷한 레이팅에 있으신 분들은 모두 그러할 것이라 생각한다 

언제쯤 실력이 늘것인지..  또 어떻게 해야 실력이 느는지 답답하고 한심하다..

 

 

 

[A Short Substrings ]

 

이 문제는 단순한 문자열 관련 구현 문제이다.

 

다음 예시는 문제에서 주어진 예시이다

A  = " abac " 라고 하자 첫 번째 인덱스부터 2개씩 끊어서 써보자 "ab", "ba", "ac"  이것을 이어 쓰게 되면 

새로운 문자열 B = "abbaac" 로 쓸 수 있다 

 

문제는  B를 이용해서 --- > A를 찾는 것이다

 

단순하게 2개씩 끊어서 정답이 되는 문자열을 만든다고 생각해서 풀었다

 

첫 번째로는 그냥 2개의 문자열을 정답이 되는 문자열에 더해준다

ans += "ab"

 

두 번째로는 겹치는 것이 존재하게 되므로 'a' 하나만 더해 준다

ans = " ab"   + "ba"

ans = "aba" 

.....

.....

 

이렇게 2개씩 검사하면 정답을 찾을 수 있다. 소스코드 또한 매우 간단하다.

 

[A번 소스코드]

 

#include <iostream>
#include <string>
using namespace std;
int test_case;
int main() {
    cin >> test_case;
    while (test_case--) {
        string str, ans = "";
        cin >> str;
        int idx = 0;
        while (idx < str.size()) {
            if (ans.size() == 0 || ans.back() != str[idx]) ans += str.substr(idx, 2);
            else ans += str[idx + 1];
            idx += 2;
        }
        cout << ans << "\n";
    }
}

 

 

[B. Even Array]

 

B번 문제 또한 간단한 구현 문제이다

각 각의 테스트 케이스에 배열 원소의 개수 n과 배열의 원소들이 입력이 주어진다.

 

모든 배열의 원소들은 다음식을 만족 해야 한다 (i : 0 < i < n-1)

 

 

그렇지 않다면 임의의 2개의 원소를 골라 swap 하여 위의 식을 만족 하게 하는 swap의 최소 횟수이다

만약 swap을 해도 식을 만족 시킬수 없다면 -1을 출력한다.

 

모든 원소에 대한 i mod 2 의 값을 모두 구해주고 마찬가지로 a[i] mod 2 식을 구해 준다.

여기서 조금 주의 할 것은 2로 나누므로 나머지는 0또는 1이 될 것이다 두 식이 같기 위해서는

왼쪽의 0의 개수 (또한 1의 개수) 오른쪽 식의 0의 개수(또한 1의 개수)가 같아야 할 것이다 

0의 개수가 서로 다르다면 아무리 swap을 해도 위의 식을 만족시킬 수 없을 것이다

 

swap의 최소 횟수를 구하는 것이니 일단 서로 다른 것의 개수를 구하고 

서로 다른 것의 개수가 2로 나누었을 때 나머지가 1이 된다면 이 역시 아무리 swap을 해도 위의 식을

만족시킬 수 없을 것이다 즉 서로 다른 것의 개수가 짝수개이여야만 한다

이를 2로 나눈 것이 정답이 된다

 

[B번 소스코드]

 

#include <iostream>
#include <string>
using namespace std;
const int MAX = 40;
int test_case, n;
int arr[MAX], Left[MAX], Right[MAX];
int l, r = 0;
int main() {
    cin >> test_case;
    while (test_case--) {
        l = 0, r = 0;
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        for (int i = 0; i < n; i++) {
            Left[i] = (i % 2);
            Right[i] = (arr[i] % 2);
            if (!Left[i])l++;
            if (!Right[i])r++;
        }
        int now = 0;
        for (int i = 0; i < n; i++) {
            if (Left[i] != Right[i]) now++;
        }
        if (l == r) {
            if (now % 2) cout << -1 << '\n';
            else cout << now / 2 << '\n';
        }
        else cout << -1 << '\n';
    }
    return 0;
}