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

1567A - Domino Disaster

문자열을 입력받고. U는 D로 바꿔서 출력하면 된다.

 

#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;
        vector<char> ans;
        for(int i=0; i<n; i++) {
            if(s[i]=='U') {
                ans.push_back('D');
            }
            else {
                ans.push_back(s[i]);
            }
        }
        for(char c : ans) {
            cout << c;
        }
        cout << '\n';
    }
}

---

1567B - MEXor Mixup

0부터 a-1까지 xor를 한 값을 x라 하자

x가 b면 --> a

x^b가 a가 아니면 --> a+1

x^b가 a면 ->> a+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 xorr(int n) {
	int m = n % 4;
	if (m == 0) return n;
	if (m == 1) return 1;
	if (m == 2) return n + 1;
	return 0;
}

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

    int T;
    cin >> T;
    while(T--) {
        int a, b;
        cin >> a >> b;
        int x=xorr(a-1)^0;

        if(x==b) {
            cout << a << '\n';
        }
        else {
            x ^= b;
            if(x==a) {
                cout << a+2 << '\n';
            }
            else {
                cout << a+1 << '\n';
            }
        }
    }
}

---

1567C - Carrying Conundrum

자리 올림 할 때 뒤로 한 칸씩 밀렸으니까 홀수번째 수와 짝수번째 수를 a와 b로 나눈 후 각 a와 b를 두 개의 덧셈으로 나누는 경우의 수를 구해주면 된다.

정답 : (a+1)(b+1)-2

더하는 한쪽이 0이 되는 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--) {
        string s;
        cin >> s;
        int a=0;
        int b=0;
        for(int i=0; i<s.size(); i+=2) {
            a *= 10;
            a += s[i]-'0';
        }
        for(int i=1; i<s.size(); i+=2) {
            b *= 10;
            b += s[i]-'0';
        }
        cout << (a+1)*(b+1)-2 << '\n';
    }
}

---

1567D - Expression Evaluation Error

쪼갤 때 항상 자릿수가 최대인 것이 많게 쪼개야 한다.

 

10진수 5와 11진수 5의 크기는 같지만 자릿수가 커지면 차이가 발생하기 시작한다.

 

10진수 5와 11진수 5의 크기는 차이가 없다.

 

10진수 15와 11진수 15의 크기는 1 차이가 난다.

 

10진수 115와 11진수 115의 크기는 22 차이가 난다.

 

관찰 결과 : 첫 번째 자리에서 차이는 0이고, 두 번째 자리에서 차이는 1이고, 세 번째 자리에서 차이는 22다.

	첫째자리	둘째자리	셋째자리	넷째자리
10진수	1	10	100	1000
11진수	1	11	121	1331
차이	0	1	21	331

결국 표에서 볼 수 있듯이 11진수에서 자릿수가 클수록 10진수와 더 크게 차이가 나게 된다.

 

셋째 자리까지 있는 100을 두 개의 숫자로 쪼개는 경우를 생각해 보자.

 

먼저 최대 11진수로 최대한 쪼개 준다.

 

100 = 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10

 

그리고 초과되게 쪼개진 것들을 다 더해준다.

 

100 = 10 + 90

 

따라서 답은 10 + 90 이 된다.

 

여기서 주의해야 할 점은 쪼개고 난 후의 덧셈은 11진수에 영향을 안 미치거나, 좋은 영향을 미친다.

 

그 이유는 표에서 나와있듯이 10진수에서 더해서 자릿수가 올라갈수록 11진수가 커지기 때문이다.

 

둘째 자리까지 있는 97을 아무 숫자로 쪼개는 경우도 생각해 보자.

 

먼저 97을 최대 11진수로 최대한 쪼개 준다.

 

97 = 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10 + 1 + 1 + 1 + 1 + 1 + 1 + 1

16개로 쪼개진다.

 

여기서 16개보다 적게 쪼개려면 초과되게 쪼개진 것들을 아무렇게나 더해서 묶어주면 된다.

 

아무렇게나 더해도 되는 이유는 아무렇게나 더해도 개수가 10개 이상이 되어서 자릿수가 넘어가는 일이 없기 때문이다.

 

표에서 볼 수 있듯이 자릿수 변동이 안 일어나면 11진수의 값은 항상 똑같다.

 

여기서 16개보다 크게 쪼개려면 쪼개도 손해가 가장 없는 자릿수가 가장 낮은 것부터 쪼개 준다.

 

예를 들어 10이 제일 낮다면 10---> 1x10으로 쪼개 준다.

 

예를 들어 100이 제일 낮다면 100---> 10x10으로 쪼개 준다.

 

주의해야 할 점은 100을 10으로 쪼갰다면 그다음 쪼개는 순서는 10을 다시 쪼개야 한다.

 

왜냐하면 100을 쪼개서 더 작은 10이 다시 생겼기 때문이다.

 

이렇게 쪼개고 싶은 개수보다 딱 이상이 될 만큼 쪼갠 후 자릿수가 낮은 것부터 묶어준다.

 

아무렇게나 더하면 안 되는 이유는, 많이 쪼개 놔서 1의 개수가 자릿수가 넘어가는 10개 이상이 될 수 있기 때문이다.

#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 s, n;
        cin >> s >> n;
        vector<int> v;
        for(int i=s; i>0; i/=10) {
            v.push_back(i%10);
        }
        while(accumulate(v.begin(), v.end(), 0)<n) {
            for(int i=1; i<v.size(); i++) {
                if(v[i]>0) {
                    v[i]--;
                    v[i-1] += 10;
                    break;
                }
            }
        }
        int sum=accumulate(v.begin(), v.end(), 0);
        int cnt=sum-n+1;
        int res=0;
        int ten=1;
        bool finish=false;
        for(int i=0; i<v.size(); i++) {
            while(v[i]>0) {
                v[i]--;
                cnt--;
                res += ten;
                if(cnt==0) {
                    finish = true;
                    break;
                }
            }
            if(finish) break;
            ten *= 10;
        }
        ten = 1;
        cout << res << ' ';
        for(int i=0; i<v.size(); i++) {
            if(v[i]>0) {
                for(int j=0; j<v[i]; j++) {
                    cout << ten << ' ';
                }
            }
            ten *= 10;
        }
        cout << '\n';
    }
}

---

1567E - Non-Decreasing Dilemma

 

1번째 쿼리는 요소를 바꾸라는 쿼리고

 

2번째 쿼리는 [l, r] 구간에서 감소하지 않는 쌍(p, q)의 개수를 묻는 쿼리다.

 

[l, r] 구간에 x개의 요소가 전부 감소하지 않는다고 했을 때 나올 수 있는 쌍의 개수는 다음과 같다.

 

[l, l], [l+1, l+1],... , [r, r] ---> x개

 

xC2 --->1부터 x-1까지의 합

 

1부터 x까지의 합 : x(x+1)/2

 

일단 f(x) = x(x+1)/2라 하자.

 

 

세그먼트 트리에 저장해야 하는 값은 4가지이다.

 

1. 왼쪽 끝부터 감소하지 않는 부분 배열과 오른쪽 끝부터 증가하지 않는 부분 배열을 제외시킨 구간에서 정답의 개수

 

2. 왼쪽 끝부터 감소하지 않는 부분 배열의 길이

 

3. 오른쪽 끝부터 감소하지 않는 부분 배열의 길이

 

4. 이 구간이 전부 감소하지 않는 배일인지 여부

 

 

이렇게 4가지로 나누는 이유는

 

1. 세그 트리의 각 구간과 구간의 경곗값에 따라 값이 달라진다.

 

예를 들어 [3, 6] 구간에서 답을 구하고 [7, 9] 구간에서 답을 구한 다음 합해버리면, 생기는 문제점이 있다.

 

구간의 경계 [6,7]에서 an [6]<=an [7] 일 경우 이어준 다음에 f함수를 써서 계산을 해 줘야 한다.

 

예를 들어 f(3)+f(2)!= f(5) 이기 때문이다.

 

따라서 경계 구간이 주어진 조건을 만족할 경우,

 

같이 합산을 해야 하므로 위에서 적었던 트리에 저장해야 하는 값 2번과 3번이 필요하다.

 

 

 

세그먼트 트리를 만들 때에는 두 개의 노드를 합칠 때 경곗값이 조건을 만족하는 경우 합해서 계산해주고 경곗값이 조건을 만족하지 않는 경우 각 각 계산해서 1번에 저장한다.

 

만약 구간 전체가 조건을 만족할 경우 1 2 3 은 0 값을 넣어주고, 4번에 1 값을 넣어준다.

 

두 구간을 합칠 때에 한 구간의 4번이 1일 경우에는 잘 고려해서 1 2 3 4번 값을 채워주면 된다.

 

 

쿼리를 만드는 방법도 알아보자.

 

각 쿼리에서 구간의 경계가 굉장히 중요하다.

 

먼저 ans, k 두 개 변수를 선언해 주고 왼쪽부터 오른쪽으로 맞는 구간을 검색한다.

 

맞는 구간이 왔을 경우 그 구간 첫 번째 값과 이전 값이 문제의 조건을 만족하면 k에 조건의 맞는 구간 길이를 더해준다.

 

만약 만족하지 않는다면 ans += f(k) 하고 k는 조건의 맞는 구간 길이로 초기화시켜준다.

 

이런 식으로 더해 나가고 마지막으로 남은 k가 있으면 ans += f(k)를 해주면 정답이 완성된다.

#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=200005;
int an[N], k;
ll seg[N*4][4], ans;

ll f(int x) {
    return ((ll)x*(x+1))/2;
}

void calc(int i, int l, int r) {
    int m=(l+r)/2;
    if(seg[i*2][3]&&seg[i*2+1][3]) {
        if(an[m]>an[m+1]) {
            seg[i][0] = 0;
            seg[i][1] = m-l+1;
            seg[i][2] = r-m;
            seg[i][3] = 0;
        }
        else {
            seg[i][0] = 0;
            seg[i][1] = 0;
            seg[i][2] = 0;
            seg[i][3] = 1;
        }
    }
    else if(seg[i*2][3]) {
        if(an[m]>an[m+1]) {
            seg[i][0] = seg[i*2+1][0]+f(seg[i*2+1][1]);
            seg[i][1] = m-l+1;
            seg[i][2] = seg[i*2+1][2];
            seg[i][3] = 0;
        }
        else {
            seg[i][0] = seg[i*2+1][0];
            seg[i][1] = m-l+1+seg[i*2+1][1];
            seg[i][2] = seg[i*2+1][2];
            seg[i][3] = 0;
        }
    }
    else if(seg[i*2+1][3]) {
        if(an[m]>an[m+1]) {
            seg[i][0] = seg[i*2][0]+f(seg[i*2][2]);
            seg[i][1] = seg[i*2][1];
            seg[i][2] = r-m;
            seg[i][3] = 0;
        }
        else {
            seg[i][0] = seg[i*2][0];
            seg[i][1] = seg[i*2][1];
            seg[i][2] = r-m+seg[i*2][2];
            seg[i][3] = 0;
        }
    }
    else {
        if(an[m]>an[m+1]) {
            seg[i][0] = seg[i*2][0]+seg[i*2+1][0]+f(seg[i*2][2])+f(seg[i*2+1][1]);
            seg[i][1] = seg[i*2][1];
            seg[i][2] = seg[i*2+1][2];
            seg[i][3] = 0;
        }
        else {
            seg[i][0] = seg[i*2][0]+seg[i*2+1][0]+f(seg[i*2][2]+seg[i*2+1][1]);
            seg[i][1] = seg[i*2][1];
            seg[i][2] = seg[i*2+1][2];
            seg[i][3] = 0;
        }
    }
}

void build(int i, int l, int r) {
    if(l==r) {
        cin >> an[l];
        seg[i][3]=1;
        return;
    }
    int m=(l+r)/2;
    build(i*2, l, m);
    build(i*2+1, m+1, r);
    calc(i, l, r);
}

void update(int i, int l, int r, int x, int y) {
    if(x<l||x>r) return;
    if(l==r) {
        an[x] = y;
        return;
    }
    int m=(l+r)/2;
    update(i*2, l, m, x, y);
    update(i*2+1, m+1, r, x, y);
    calc(i, l, r);
}

void query(int i, int l, int r, int s, int e) {
    if(r<s||e<l) return;
    if(s<=l&&r<=e) {
        if(seg[i][3]) {
            if(an[l-1]>an[l]) {
                ans += f(k);
                k = r-l+1;
            }
            else {
                k += r-l+1;
            }
        }
        else {
            if(an[l-1]>an[l]) {
                ans += f(k)+seg[i][0]+f(seg[i][1]);
            }
            else {
                ans += seg[i][0]+f(k+seg[i][1]);
            }
            k = seg[i][2];
        }
        return;
    }
    int m=(l+r)/2;
    query(i*2, l, m, s, e);
    query(i*2+1, m+1, r, s, e);
}

int main() {
    ios::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
    int n, q, t, l, r;

    cin >> n >> q;
    build(1, 1, n);
    while(q--) {
        cin >> t >> l >> r;
        if(t==1) {
            update(1, 1, n, l, r);
        }
        else {
            ans = k = 0;
            query(1, 1, n, l, r);
            cout << ans+f(k) << '\n';
        }
    }
}