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

1582A - Luntik and Concerts

a, b, c가 전부 1개 이상 존재하므로 최대 차이는 1이다. 따라서 차이는 0 또는 1이 될 수 있다.

 

a + b*2 + c*3 이 짝수면 차이는 0이고 홀수면 차이는 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
int main() {
    ios::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);

    int T;
    cin >> T;
    while(T--) {
        int a, b, c;
        cin >> a >> b >> c;
        int s=a+b*2+c*3;
        if(s&1) cout << 1;
        else cout << 0;
        cout << '\n';
    }
}

---

1582B - Luntik and Subsequences

1의 개수를 a, 0의 개수를 b라 하자.

 

전체 합이 s-1이 되려면 1만 빼줘야 한다.

 

그리고 0은 빼줘도 되고 안 빼줘도 된다.

 

따라서 답은 1이 빠질 수 있는 경우의 수 x 0을 선택할 수 있는 경우의 수 이므로

 

a*2^b이다.

#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;
        cin >> n;
        ll an[100]{0};
        ll one=0;
        ll zero=0;
        for(int i=1; i<=n; i++) {
            cin >> an[i];
            if(an[i]==1) one++;
            else if(an[i]==0) zero++;
        }
        ll p=1;
        for(int i=1; i<=zero; i++) {
            p *= 2;
        }
        cout << one*p << '\n';
    }
}

---

1582C - Grandma Capa Knits a Scarf

단순히 모든 경우의 수를 세어주면 된다.

 

오로지 한 문자만 뺄 수 있으므로, a~z까지 총 26개의 반복문을 수행하면 된다.

 

모든 문자열이 팰린드롬이 되어야 하므로 위치를 나타내는 두 개의 변수에 각 각 0과 n-1을 대입한다.

 

하나씩 비교하면서 left는 1씩 증가시켜주고, right는 1씩 빼 준다.

 

현재 선택한 문자를 a라 하자.

 

만약 두 개의 문자가 다를 경우 둘 중 현재 선택한 문자가 left에 존재한다면 left만 +1 한다.

 

right에 존재한다면 right만 -1 한다.

 

만약 둘 중 어디에도 현재 선택한 문자가 존재하지 않는다면 선택한 문자만 제거해서는 문자열이 팰린드롬이 될 수 없다는 뜻이므로 반복문을 취소하고 다른 문자열을 선택한다.

 

이렇게 a~z까지 전부 확인하면서 최솟값을 갱신해주고, 갱신이 안됐다면 가능한 경우가 없으므로 -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
int main() {
    ios::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);

    int T;
    cin >> T;
    while(T--) {
        int n;
        cin >> n;
        string s;
        cin >> s;
        int ans=1000000000;
        for(int i=0; i<26; i++) {
            int left=0;
            int right=n-1;
            int res=0;
            while(left<=right) {
                if(s[left]==s[right]) {
                    left++;
                    right--;
                }
                else {
                    if(s[left]==('a'+i)) {
                        res++;
                        left++;
                    }
                    else if(s[right]==('a'+i)) {
                        res++;
                        right--;
                    }
                    else {
                        res = 1000000000;
                        break;
                    }
                }
            }
            ans = min(ans, res);
        }
        if(ans==1000000000) cout << -1;
        else cout << ans;
        cout << '\n';
    }
}

---

1582D - Vupsen, Pupsen and 0

정수 a, b가 주어졌을 때 (a!=0, b!=0)

 

ax + by = 0을 만족하는 x, y는 x=b, y=-a이다.

 

서로가 서로를 곱해주고 부호만 다르게 해 주면 된다.

 

 

정수 a, b, c가 주어졌을 때 (a!=0, b!=0, c!=0)

 

ax + by + cz = 0을 만족하는 x, y, z는 x=-c, y=-c, z=a+b이다.

 

a(-c) + b(-c) + c(a+b) = -c(a+b) + c(a+b) = 0이다.

 

※ 문제의 조건에서 x, y, z는 0이 불가능하므로로 a+b가 0이 되면 안 된다.

 

만약 a!=0, b!=0, c!=0이고 a+b가 0이고 a+c가 0이라면 b+c는 무조건 0이 아니기 때문에 세 수 중에서 두 수의 합이 0이 아닌 두 수 쌍이 항상 존재하게 된다.

 

여기서 응용해서 a, b, c, d(전부 0이 아님)가 주어졌을 때의 해를 구해보자.

 

먼저 고른 한 개의 수를 d라 하자 나머지 세수에 -d를 곱해주고 d에는 a+b+c를 곱해주면 된다.

 

n이 짝수인 경우 두 개씩 묶어서 답을 도출하면 된다.

 

n이 홀수인 경우 먼저 3개를 묶고 나머지는 두 개씩 묶어서 답을 도출하면 된다.

 

n이 홀수일 때 첫 3개를 묶어주면 좀 더 깔끔할 것 같다.

#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

const int N=100000;
int an[N+10];
int bn[N+10];
int main() {
    ios::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while(T--) {
        int n;
        cin >> n;
        for(int i=1; i<=n; i++) {
            cin >> an[i];
        }
        bool odd=false;
        if(n&1) {
            odd = true;
            for(int i=1; i<n-3; i+=2) {
                if(an[i]*an[i+1]>0) {
                    cout << -abs(an[i+1]) << ' ' << abs(an[i]) << ' ';
                }
                else {
                    cout << abs(an[i+1]) << ' ' << abs(an[i]) << ' ';
                }
            }
        }
        else {
            for(int i=1; i<n; i+=2) {
                if(an[i]*an[i+1]>0) {
                    cout << -abs(an[i+1]) << ' ' << abs(an[i]) << ' ';
                }
                else {
                    cout << abs(an[i+1]) << ' ' << abs(an[i]) << ' ';
                }
            }
        }
        if(odd) {
            if(an[n-2]+an[n-1]!=0) {
                cout << -an[n] << ' ' << -an[n] << ' ' << an[n-2]+an[n-1];
            }
            else if(an[n-2]+an[n]!=0) {
                cout << -an[n-1] << ' ' << an[n-2]+an[n] << ' ' << -an[n-1];
            }
            else if(an[n-1]+an[n]!=0) {
                cout << an[n]+an[n-1] << ' ' << -an[n-2] << ' ' << -an[n-2];
            }
        }
        cout << '\n';
    }
}

 

---

1582E - Pchelyonok and Segments

먼저 k가 j일 때 필요한 최소 배열 길이는 1부터 k까지의 합, j*(j+1)/2이다.

 

n이 100000까지 가능하므로 k의 최댓값은 447이 된다.

 

dp[i][j]를 i부터 n까지 범위에서 k==j가 가능하다면 그때의 첫 번째 배열(길이 : k)의 최댓값으로 정의하자.

 

i는 내림차순, j는 오름차순으로 채우면 된다.

 

기본적으로 새로 추가되는 원소를 포함하지 않았을 때 dp[i][j] = dp[i-1][j]이다.

 

새로 추가되는 원소를 포함할 때는 새로 추가되는 원소를 포함한 첫 번째 배열의 합을 구한다.

 

배열의 합을 빠르게 구하기 위해서 prefix sum을 이용한다.

 

새로 추가되는 원소를 포함한 첫 번째 배열의 합이 다음번 배열보다 작다면은 dp[i][j]가 될 수 있는 후보가 된다.

 

다음은 수식으로 표현한 것이다.

 

pref[i+j-1]-pref[i-1] < dp[i+j][j-1] 이면 ([i, i+j-1] : 구간합, i+j : 다음 배열(시작은 아닐 수 있음), j-1 : 다음 배열 길이)

dp[i][j] = max(dp[i][j], pref[i+j-1]-pref[i-1]) 이다.

 

코드로 나타내 보자면 다음과 같다.

for(int i=n; i>=1; i--) {
    for(int j=1; j<k; j++) {
        dp[i][j] = dp[i+1][j];
        if(i+j-1<=n && pref[i+j-1]-pref[i-1] < dp[i+j][j-1]) {
            dp[i][j] = max(dp[i][j], pref[i+j-1]-pref[i-1]);
        }
    }
}

 

여기서 dp에 들어가는 첫 번째 기본값을 대입해 줘야 한다.

 

만약 j가 0이라면 항상 그 값은 존재해야 하기 때문에 모든 i에 대하여 j가 0일 때 최댓값을 대입해 준다.

for(int i=1; i<=n+1; i++) {
    dp[i][0] = inf;
}

 

그리고 테스트 케이스가 끝날 때마다 dp를 초기화해야 한다.

 

하지만 dp배열의 길이는 100000 * 450이라서 매 번 초기화를 하면 시간 초과가 난다.

 

따라서 매 번 dp배열을 모두 0으로 초기화 하기보다는 어차피 dp[i][j]는 i가 내림차순으로 채워지기 때문에 dp[n+1][1~k] 만 0으로 초기화하면 된다.

for (int j=1; j<k; j++) {
    dp[n+1][j] = 0;
}

#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

const int N=100000;
const int inf=2000000000;
ll an[N+5];
ll dp[N+5][450];
ll pref[N+5];

int main() {
    ios::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while(T--) {
        int n, k;
        cin >> n;
        for(int i=1; i<=n; i++) {
            cin >> an[i];
            pref[i] = pref[i-1] + an[i];
        }
        k = 1;
        while(k*(k+1)<=n*2) k++;
        for (int j=1; j<k; j++) {
            dp[n+1][j] = 0;
        }
        for(int i=1; i<=n+1; i++) {
            dp[i][0] = inf;
        }
        for(int i=n; i>=1; i--) {
            for(int j=1; j<k; j++) {
                dp[i][j] = dp[i+1][j];
                if(i+j-1<=n && pref[i+j-1]-pref[i-1] < dp[i+j][j-1]) {
                    dp[i][j] = max(dp[i][j], pref[i+j-1]-pref[i-1]);
                }
            }
        }
        int ans=0;
        for(int i=1; i<k; i++) {
            if(dp[1][i]>0) ans = i;
        }
        cout << ans << '\n';
    }
}

---

1582F1 - Korney Korneevich and XOR (easy version)

a[i]가 최대 500까지 가능하기 때문에 최대 계산될 수 있는 xor 값은 512이다.

 

따라서 0부터 512 기준으로 dp를 생성하면 된다.

 

dp[j]를 r1^r2^r3^r4^...^rm = j 라 했을 때 마지막 원소 rm의 최솟값이라고 정의하자.

 

선택한 부분 수열의 원소들은 순차적으로 증가해야 하므로(문제의 조건에 나와있다.) an[1]부터 an[n]까지 순차적으로 확인한다.

 

점화식은 다음과 같다.

 

만약 dp[j]가 현재 확인하고 있는 an[i]보다 작을 경우 다음 과정을 실행한다. (dp[j] = r1^r2^r3^r4^...^rm에서의 rm이고 우리가 하고 싶은 행동은 이 수식 뒤에 원소(an[i]) 하나를 더 붙이고 싶기 때문에 문제의 조건에서 부분 수열은 항상 증가해야 하므로 dp[j]가 an[i]보다 작아야 한다.)

 

dp[j^an[i]]보다 an[i]가 작을 경우 dp[j^an[i]]에 an[i]를 대입해준다.

 

여기까지가 점화식이다.

 

dp[j]를 r1^r2^r3^r4^...^rm = j 라 했을 때 마지막 원소 rm의 최솟값이라고 정의했기 때문에 dp[j^an[i]]를 식으로 표현하자면 r1^r2^r3^r4^...^rm^an[i] 의 마지막 원소의(현재는 an[i]) 최솟값이다.

 

r1^r2^r3^r4^...^rm^an[i] = k라고 했을 때 기존 dp[k]에 들어있는 값보다 an[i]가 더 작다면 dp[k]를 an[i]로 업데이트한다.

 

순차적으로 an[i]를 확인하고 있으므로 순서는 항상 부분 수열이 되므로 만족한다.

#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

const int N=100000;
const int inf=1000000000;
int n, an[N+10], dp[520];
vector<int> ans;

int main() {
    ios::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i=1; i<=n; i++) {
        cin >> an[i];
    }
    for(int i=1; i<=512; i++) {
        dp[i] = inf;
    }
    for(int i=1; i<=n; i++) {
        for(int j=0; j<=512; j++) {
            if(dp[j] < an[i]) {
                dp[j^an[i]] = min(dp[j^an[i]], an[i]);
            }
        }
    }
    ans.push_back(0);
    for(int i=1; i<=512; i++) {
        if(dp[i]!=inf) ans.push_back(i);
    }
    cout << ans.size() << '\n';
    for(int i : ans) {
        cout << i << ' ';
    }
}