Codeforces Round #854 Editorial

Codeforces Round #854 Editorial

기한	2023-02-28
solving	3/9
소회	Blue에 복귀하였다..

A. Recent Actions Problem - A - Codeforces

• queue구조로 항상 n+1~n+m사이의 값이 맨 앞에 추가되기 때문에 boolean 변수를 하나 두고 시뮬레이션 하면 된다.
  맨 마지막부터 순서대로 증가하는 순서로 정답이 결정된다.

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <memory.h>
#include <queue>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <time.h>
#include <math.h>
#include <list>

#include <assert.h>
#define debug(x) printf("(%s): %d", #x, x)
#define MAX(a,b) ((a)>(b)?(a):(b))

#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>0?(a):-(a))
#define rep(x, start, end) for(int x=start;i < end; i++)
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);

#include <bitset>
#include <complex>

using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
const ll MOD = 1e9 + 7;

const long long inf = 1e9;
typedef complex<double> compx;
const double pi = 3.14159265358979;

const int MAX_ID = 101010;

int A[100005];
int answer[100005];
int n, m;

void solve() {
    cin >> n >> m;
    memset(A, 0, sizeof(A));
    memset(answer, -1, sizeof(answer));
    int k = n;
    int t = 1;

    for (int i = 0; i < m; i++) {
        int v;
        cin >> v;
        A[v]++;
        if (A[v] == 1) {
            answer[k--] = i+1;
        }
    }
    for (int i = 1; i <= n; i++) cout << answer[i] << " ";
    cout << "\n";
}
int main() {
    fastio;

    int testCase = 1;
    cin >> testCase;
    for (int i = 1; i <= testCase; i++) {
        solve();
    }
}

B. Equalize by Divide Problem - B - Codeforces

Problem - B - Codeforces

쑤셔 풀었다. 문제 풀이 당시에는 다음과 같은 정보로만 풀었다.

 

1) 모든 숫자가 같으면 0번만에 가능하다
2) 1에 해당하지 않을 때 1이 존재하면 무조건 불가능하다
3) 2가 있으면 무조건 된다. (어떤 숫자든 2로 만들 수 있다)
문제 제한에서 operation이 최대 30n까지 가능하다는 내용이 있는데, 최대값이 거의 2^30에 걸쳐있다.
4) 나머지는 작은걸로 계속 나눠봐서 2가 나오던가, 다 같아지던가 둘 중 하나를 체크한다.

 

맘에 안든 풀이였다

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <memory.h>
#include <queue>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <time.h>
#include <math.h>
#include <list>

#include <assert.h>
#define debug(x) printf("(%s): %d", #x, x)
#define MAX(a,b) ((a)>(b)?(a):(b))

#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>0?(a):-(a))
#define rep(x, start, end) for(int x=start;i < end; i++)
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);

#include <bitset>
#include <complex>

using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
const ll MOD = 1e9 + 7;

const long long inf = 1e9;
typedef complex<double> compx;
const double pi = 3.14159265358979;

const int MAX_ID = 101010;

pair<ll,int> A[100005];
int n;

void proc(vector<pair<int,int>> & q, int a) {
    while (A[a].first != 2) {
        A[a].first = (A[a].first + 1) / 2;
        q.push_back({ A[a].second, A[0].second });
    }
}
void solve() {
    vector<pair<int, int>> q;
    cin >> n;
    int oneNum = 0;
    for (int i = 0; i < n; i++) {
        cin >> A[i].first;
        A[i].second = i + 1;

        if (A[i].first == 1) oneNum++;
    }
    bool allSame = true;
    for (int i = 0; i < n; i++) {
        if (A[i].first != A[0].first) allSame = false;
    }


    if (oneNum == n || n==1 || allSame) {
        cout << 0 << "\n";
        return;
    }
    else if (oneNum > 0) {
        cout << -1 << "\n";
        return;
    }

    auto run = [](vector<pair<int,int>>& q, int a, int b) {
        if (A[a].first == A[b].first) return;
        A[b].first = (A[b].first + A[a].first - 1) / A[a].first;
        q.push_back({ A[b].second, A[a].second });

    };
    int c = 0;
    sort(A, A + n);
    while (A[0].first != 2 && c < 30) {
        for (int i = 1; i < n; i++) {
            run(q, 0, i);
        }
        sort(A, A + n);
        c++;
    }
    if (A[0].first == 2) {
        for (int i = 1; i < n; i++) proc(q, i);
    }
    else {

        bool allSame = true;
        for (int i = 0; i < n; i++) {
            if (A[i].first != A[0].first) allSame = false;
        }
        if (allSame == false) {
            cout << -1 << "\n";
            return;
        }
    }

    cout << q.size() << "\n";

    for(auto x : q) cout << x.first << " " << x.second << "\n";
}
int main() {
    fastio;



    int testCase = 1;
    cin >> testCase;
    for (int i = 1; i <= testCase; i++) {
        solve();
    }
}

Upsolving

Editorial 내용을 참고했다.

 

1) 최초 모든 숫자가 같으면 아무것도 안하면 된다.

2) 다른 경우, 만약 1인 값이 존재하면 답은 존재하지 않는다 (모든 값을 다 1로 만들 수 없다)

3) 값이 모두 2보다 크면 답은 항상 존재한다.

 

만약 모든 값이 2보다 클 경우 다음과 같은 방식으로 항상 정답에 도달할 수 있다.

 

1) 가장 큰 값과 가장 작은 값에 operation을 수행한다.

2) 가장 큰 값과 가장 작은 값이 같을 때 까지 반복한다.

 

가장 큰 값과 가장 작은 값을 위의 연산을 취할 경우 항상 2보다 커질 수 밖에 없다. (최소보다 1만 커도 2니까!)

결국 최소 값과 최대 값이 같지 않다면, 항상 연산 결과는 2 이상이다. 최종적인 값 또한 2 이상이 될 것

 

C. Double Lexicographically Minimum Problem - C - Codeforces

Problem - C - Codeforces

쑤셔 풀었다. 이쯤되면 쑤셔 풀기 장인이다

 

1) 작은 순으로 왼쪽과 오른쪽에 값을 넣는다.

2) 왼쪽과 오른쪽에 값을 넣을 때 다른 값이 존재하는 순간 다음과 같은 분기가 생긴다.

3) 다른 두 값 중 큰 값을 b라고 하자. 남은 모든 문자가 b라면, 작은 문자가 중간에 껴들어가는게 최적이다.

e.g., [a]bbb[b] 일 경우, 작은 값 쪽이 중간에 낑겨 들어가야 된다. bbabb.

4) 남은 문자가 b말고도 있다면, 남은 문자를 소팅해서 중간에 넣어주면 된다.

e.g., a[b]feb[a]a 일 경우, 중간에 있는 문자를 소팅해서 넣어준다. abbefaa.

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <memory.h>
#include <queue>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <time.h>
#include <math.h>
#include <list>

#include <assert.h>
#define debug(x) printf("(%s): %d", #x, x)
#define MAX(a,b) ((a)>(b)?(a):(b))

#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>0?(a):-(a))
#define rep(x, start, end) for(int x=start;i < end; i++)
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);

#include <bitset>
#include <complex>

using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
const ll MOD = 1e9 + 7;

const long long inf = 1e9;
typedef complex<double> compx;
const double pi = 3.14159265358979;

const int MAX_ID = 101010;

pair<ll, int> A[100005];
int n;

int histo[26];
void solve() {
    string s;
    cin >> s;
    int n = s.size();
    memset(histo, 0, sizeof(histo));
    for (int i = 0; i < n; i++) histo[s[i] - 'a']++;
    string t = s;
    sort(s.begin(), s.end());

    int left = 0;
    int right = n - 1;

    int c = 0;
    for (int i = 0; i < n / 2; i++) {
        t[right--] = s[c++];
        t[left++] = s[c++];
        if (t[left - 1] != t[right + 1]) break;
    }

    if (c < n) {
        vector<char> alls;
        bool allSame = true;
        char base = -1;
        if (left - 1 >= 0 && right + 1 < n) {
            base = max(t[left - 1], t[right + 1]);
        }
        while (c < n) {
            alls.push_back(s[c++]);
            if (alls.back() != base) allSame = false;
        }

        string v = t;
        reverse(v.begin(), v.end());
        sort(alls.begin(), alls.end());
        int mid = (left + right + 1) / 2;
        int curLast = right + 1;

        for (int i = 0; i < alls.size(); i++) {
            t[left] = alls[i];
            v[left++] = alls[i];
        }

        if (allSame) {
            swap(t[mid], t[curLast]);
            v = t;
        }

        if (t < v) cout << v << "\n";
        else cout << t << "\n";
    }
    else {
        string v = t;
        reverse(t.begin(), t.end());
        if (t < v) cout << v << "\n";
        else cout << t << "\n";
    }

}
int main() {
    fastio;

    int testCase = 1;
    cin >> testCase;
    for (int i = 1; i <= testCase; i++) {
        solve();
    }
}

Upsolving

editorial > 내가 한 풀이하고 똑같은데, 구조화가 안된다.. 좀 더 생각이 필요할 듯