코드포스 Codeforces Round #741 (Div. 2) 풀이

1562A - The Miracle and the Sleeper

30을 예로 들자면 나누는 숫자가 30부터 16으로 작아질수록 나머지는 1 씩 증가한다.

 

15가 되면 나머지는 다시 0이 되고 나머지는 다시 증가하다가 10이 되면 다시 0이 된다.

 

이렇게 나머지는 숫자가 점점 커지다가 작아지다를 반복하는데, 잘 보면 나머지의 최대는 대략 30을 2로 나눈 숫자다.

 

이를 토대로 나눠지는 값은 최대한 크게 잡고 나눠지는 값은 그의 절반값이 될 수 있으면 나머지는 최대가 된다.

 

하지만, 나누는 값이 나눠지는 값의 절반이 될 수 없으면 나머지는 나눠지는 값 빼기 나누는 값이 된다.

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
#define F first
#define S second
int main() {
    ios::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);

    int T;
    cin >> T;
    while(T--) {
        int l, r;
        cin >> l >> r;
        if(l*2<=(r+1)) {
            cout << (r+1)/2-1 << '\n';
        }
        else {
            cout << r-l << '\n';
        }
    }
}

---

1562B - Scenes From a Memory

주어진 숫자에 1, 4, 6, 8, 9가 들어간다면, 정답은 그 숫자 하나가 된다.

 

하지만 주어진 숫자에 이 숫자들이 들어가지 않는다면 답은 두 자리 이상이 되는데, 항상 두 자리로 만들 수 있다.

 

111~999까지가 0이 없는 3자리 숫자인데 먼저 숫자가 1, 4, 6, 8, 9 인경우를 제외한다.

 

그리고 마지막 숫자가 2, 5인 두 자리 이상의 수는 합성수 이므로 2, 5도 제외하면 남는 숫자는 3과 7이다.

 

다 해보면 알겠지만 세 자릿수 중에서 3과 7로 끝나는 수는 무조건 한 개 숫자를 빼서 합성수를 만들 수 있다. 또는 3으로 나누어 떨어진다.

 

1, 4, 6, 8, 9가 포함이 안되고, 마지막이 3과 7로 끝나는 수를 무작위로 만들어 보면,

 

257인 경우 27로 만들 수 있다.

 

237인 경우 3으로 나누어 떨어진다.

 

이렇게 하나하나 다 해보면 3자리 숫자는 전부 두 자리의 합성 수로 만들 수 있다.

 

나는 그럴 것이라고 예상은 했지만 불확실하여 10000까지의 합성수를 만들어 놓고 1부터 확인해서 있으면 출력했다.

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
#define F first
#define S second

string s;
vector<int> ans;

bool find_p(int in) {
    bool ret=false;
    string str=to_string(in);
    for(int i=0; i<s.size(); i++) {
        if(ret) break;
        if(s[i]==str[0]) {
            int j=1;
            if(j==str.size()) {
                ret = true;
                break;
            }
            for(int x=i+1; x<s.size(); x++) {
                if(s[x]==str[j]) {
                    j++;
                    if(j==str.size()) {
                        ret = true;
                        break;
                    }
                }
            }
        }
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);

    bool go[10010]{0};
    go[1] = 1;
    for(int i=2; i<=10000; i++) {
        if(go[i]==0) {
            for(int j=i*2; j<=10000; j+=i) {
                go[j] = 1;
            }
        }
    }
    for(int i=1; i<=10000; i++) {
        if(go[i]==1) {
            ans.push_back(i);
        }
    }
    int T;
    cin >> T;
    while(T--) {
        int k;
        cin >> k >> s;
        string res=s;
        for(int i=0; i<ans.size(); i++) {
            if(find_p(ans[i])) {
                res = to_string(ans[i]);
                break;
            }
        }
        cout << res.size() << '\n' << res << '\n';
    }
}

---

1562C - Rings

 

k가 1인 경우 나눈 두 2진수의 크기는 같다.

 

k가 2인 경우 나눈 두 2진수의 차이는 오른쪽 끝 0 한 개뿐이다.

 

2진수에 2를 곱하면 왼쪽 쉬프트가 되기 때문이다.

 

전체가 1로 주어지는 경우를 생각해보자.

 

[1111] 1

 

1 [11111]

 

이렇게 나누면 된다.

 

0과 1이 섞여있는 경우를 생각해보자.

 

0이 있으면 무조건 두 개로 나눌 수 있다.

 

1010111010010100일 때

 

1010111 [010010100]

 

10101110 [10010100]

 

또는

 

[10101110]10010100

 

[1010111]010010100

 

이렇게 나누면 된다.

 

전자일 경우 맨 앞 0은 없는 숫자와 같으므로 k=1일 때 성립한다.

 

후자일 경우 맨 뒤 0은 2를 곱한 숫자와 같으므로 k=2일 때 성립한다.

 

나눈 배열의 길이가 항상 전체 배열의 길이의 절반보다 같거나 커야 하므로

 

첫 0의 인덱스가 배열의 절반보다 안쪽에 있으면 k=1로 나누고,

 

첫 0의 인덱스가 배열의 절반보다 커지면 k=2로 나누는 경우를 생각하면 된다.

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
#define F first
#define S second

int main() {
    ios::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);

    int T;
    cin >> T;
    while(T--) {
        int n;
        string s;
        cin >> n >> s;
        bool solve=false;
        for(int i=0; i<n; i++) {
            if(s[i]=='0') {
                solve = true;
                if(i<=(n-1)/2) {
                    cout << i+1 << ' ' << n << ' ' << i+2 << ' ' << n << '\n';
                }
                else {
                    cout << 1 << ' ' << i+1 << ' ' << 1 << ' ' << i << '\n';
                }
                break;
            }
        }
        if(!solve) {
            cout << 1 << ' ' << n-1 << ' ' << 2 << ' ' << n << '\n';
        }
    }
}

---

1562D1 - Two Hundred Twenty One (easy version)

 

쿼리 구간의 원소 수를 n이라 하자.

 

쿼리 구간의 배열을 ai라 하자. (i=1, 2, 3,..., n)

 

 

문제에 나와있듯이 전하의 부호 변수 합계는 아래와 같다.

 

a1 - a2 + a3 - a4 +...

 

쿼리 구간에서 ai원소 한 개를 뺀 전하의 부호 변수 합계를 bi라 하자.

 

bi와 b(i+1)의 차이는 ai == a(i+1) 일 때는 0의 차이가 난다

 

ai! = a(i+1) 일 때는 2의 차이가 난다.

 

따라서 수열 bi는 항상 0 또는 2의 차이가 나게 된다.

 

 

n이 홀수인 경우를 생각해보자

 

주어진 쿼리 구간에서 이미 전하의 부호 변수 합계가 0인 경우는 답이 0이 된다.

 

 

0이 아닌 경우에는 한 개 이상 원소를 빼 주어야 한다.

 

모든 전하의 부호 변수 합계는 원소가 하나 증가할 때마다 항상 한 칸씩 증가하거나 감소하므로 전체 원소의 개수가 홀수인 경우 전하의 부호 변수 합계는 홀수가 되고, 짝수인 경우 짝수가 된다.

 

n이 홀수인 경우를 생각하고 있으므로 원소를 한 개 빼주면 n은 짝수가 된다. 따라서 전하의 부호 변수 합계는 짝수가 된다.

 

b1 == 0 이거나 bn == 0 이면 답은 1이 된다. (수열 bi의 뜻을 생각해보자)

 

b1 < 0이고 bn > 0 일 때 답은 항상 2~n-1 사이에 존재하게 된다.

 

수열 bi는 인접항과 차이가 항상 0 또는 2 차이가 나게 되는데, 전하의 부호 변수 합계가 짝수이므로 중간에 0을 꼭 거쳐가게 된다.

 

비슷한 수학 정리로 중간값 정리가 있다.

 

b1 > 0이고 bn < 0 인 경우도 마찬가지다.

 

 

b1 < 0이고 bn < 0 이거나 b1 > 0이고 bn > 0 인 경우는 존재할 수 없다.

 

아무것도 원소를 제거하지 않았을 때 전하의 부호 변수 합계를 s라 하자.

 

bn은 끝 원소 하나를 제거하므로 bn == s+1 또는 bn == s-1 이 된다.

 

b1은 맨 앞 원소 하나를 제거하는 경우다.

 

모든 원소의 부호가 바뀌므로 -s가 되고 원소 하나를 제거하므로 b1 == -s+1 또는 b1 == -s-1 가 된다.

 

 

따라서 n이 홀수인 경우는 무조건 답이 1이다.

 

n이 짝수인 경우는

 

주어진 쿼리 구간에서 이미 전하의 부호 변수 합계가 0인 경우는 답이 0이 된다.

 

0이 아닌 경우에는 한 개 이상 원소를 빼 주어야 한다.

 

n이 짝수인 경우를 생각하고 있으므로 원소를 한 개 빼주면 n은 홀수가 된다. 따라서 전하의 부호 변수 합계는 홀수가 된다.

 

이 말은 즉, bi가 홀수라는 뜻인데 bi는 인접한 항과 0 또는 2 차이가 나므로 모든 bi는 홀수가 돼서 bi == 0 만족하는 i는 존재할 수 없게 된다.

 

따라서 원소 한 개를 더 빼줘야 한다.

 

이러한 경우는 n이 홀수인 경우처럼 무조건 bi==0을 만족하는 i가 구간 사이에 존재하므로 답은 2가 된다.

 

 

간단하게 요약하면

 

주어진 쿼리 구간이 이미 조건을 만족하면 답은 0이고

 

주어진 쿼리 구간의 원소의 개수가 홀수이면 답은 1이고

 

주어진 쿼리 구간의 원소의 개수가 짝수이면 답은 2다.

 

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
#define F first
#define S second

string s;
const int N=300000;
int n, q, an[N+10], sum[N+10];

int main() {
    ios::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);

    int T;
    cin >> T;
    while(T--) {
        cin >> n >> q >> s;
        for(int i=0; i<n; i++) {
            if(s[i]=='+') {
                an[i+1] = 1;
            }
            else {
                an[i+1] = -1;
            }
            sum[i+1] = sum[i] + ((i&1) ? -an[i+1] : an[i+1]);
        }
        for(int i=0; i<q; i++) {
            int l, r;
            cin >> l >> r;
            if(sum[r]-sum[l-1]==0) {
                cout << 0 << '\n';
            }
            else {
                if((l-r+1)&1) {
                    cout << 1 << '\n';
                }
                else {
                    cout << 2 << '\n';
                }
            }
        }
    }
}

---

1562D2 - Two Hundred Twenty One (hard version)

D2에서는 D1에서 제거원 원소의 인덱스도 같이 출력해 주면 된다.

 

1부터 모든 원소까지에 대해 전하의 부호 변소 합계를 저장하는 prefix sum을 만들어 준다.

 

prefix [1] = a1

 

prefix [2] = a1 - a2

 

prefix [3] = a1 - a2 + a3

 

...

 

prefix [n] = a1 - a2 +... an

 

이런 식으로 구해 주면 된다.

 

그리고 쿼리 구간 [l, r]에 대해 bi(쿼리 구간에서 ai원소 한 개를 뺀 전하의 부호 변수 합계, i=1~n)를 구하는 공식은 다음과 같다.

 

(쿼리 구간 첫 원소부터 i번 이전 원소까지 전하 부호 변수 합)

 

+(-(i번 다음 원소부터 쿼리 구간 끝까지 전하 부호 변수 합))

 

두 번째에서 -를 붙여준 이유는 한 원소가 빠지면 그다음은 부호가 전부 바뀌기 때문이다.

 

따라서 아래와 같은 식이 나온다.

 

f(i) = prefix [i-1]-prefix [l-1]-(prefix [r]-prefix [i])

 

이제 쿼리 구간에서 저 i에 해당하는 값을 찾아 주어야 한다.

 

n이 홀수인 경우 무조건 존재한다고 D1에서 증명했다.

 

따라서 반복문으로 r부터 l까지 순차적 탐색하면서 찾아도 되긴 하지만 시간 초과가 나온다.

 

여기서 이분 탐색을 이용할 수 있다.

 

m = (s+e)/2라 하자 (s, e는 이분 탐색 첫 지점과 끝 지점)

만약 f(m)과 f(l)의 부호가 다르다면 l~m 사이에 0이 존재하므로(D1에서 증명) e = m-1이 된다.

 

만약 f(m)과 f(r)의 부호가 다르다면 m~r 사이에 0이 존재하므로 s = m+1이 된다.

 

이렇게 가다 보면 무조건 한 개가 있으므로 무조건 찾게 된다.

 

n이 짝수인 경우 무조건 2개가 존재한다고 D1에서 증명했다.

 

따라서 간단하게 위하여 쿼리 구간 [l, r]에서 가장 첫 번째 원소인 l를 선택하고 출력한다. (아무거나 선택해도 된다.)

 

그리고 [l+1, r]에서 다시 이분 탐색으로 나머지 원소 하나를 찾아주면 문제가 해결된다.

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
#define F first
#define S second

string s;
const int N=300000;
int n, q, an[N+10], sum[N+10], l, r;

int f(int i) {
    int cal=sum[i-1]-sum[l-1]-(sum[r]-sum[i]);
    if(cal==0) return 0;
    else if(cal>0) return 1;
    else return -1;
}

int main() {
    ios::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);

    int T;
    cin >> T;
    while(T--) {
        cin >> n >> q >> s;
        for(int i=0; i<n; i++) {
            if(s[i]=='+') {
                an[i+1] = 1;
            }
            else {
                an[i+1] = -1;
            }
            sum[i+1] = sum[i] + ((i&1) ? -an[i+1] : an[i+1]);
        }
        for(int i=0; i<q; i++) {
            cin >> l >> r;
            if(sum[r]-sum[l-1]==0) {
                cout << 0 << '\n';
            }
            else {
                if((l-r+1)&1) {
                    cout << 1 << '\n';
                }
                else {
                    l++;
                    cout << 2 << '\n';
                    cout << l-1 << ' ';
                }
            }
            int s=l;
            int e=r;
            while(s<=e) {
                int m=(s+e)/2;
                if(f(m)==0) {
                    cout << m << '\n';
                    break;
                }
                else if(f(m)!=f(s)) {
                    e = m-1;
                }
                else {
                    s = m+1;
                }
            }
        }
    }
}