Codeforces Round #744 (Div. 3) A, B, E1

A. Casimir's String Solitaire

C++

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define all(c) c.begin(), c.end()
#define INF 1e9
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

int main(){
    fastio;
    int tc;
    cin >> tc;
    while(tc--){
        string s;
        cin >> s;
        int a, b, c;
        a = b = c = 0;
        for(char i : s){
            switch(i){
                case 'A':
                    a++;
                    break;
                case 'B':
                    b++;
                    break;
                case 'C':
                    c++;
                    break;
            }
        }
        if(a+c == b) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

A, B 또는 B, C 를 동시에 제거해나가야 하므로, 모두 제거하려면 A, C 를 합한 개수가 B 의 개수와 같아야 한다.

B. Shifting Sort

C++

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define all(c) c.begin(), c.end()
#define INF 1e9
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

bool compare(int a, int b){
    return a < b;
}

int main(){
    fastio;
    int tc;
    cin >> tc;
    while(tc--){
        int n;
        cin >> n;
        vector<int> a(n);
        for(int& i : a){
            cin >> i;
        }
        deque<int> dq;
        for(int i : a){
            dq.push_back(i);
        }
        sort(all(a), compare);
        vector<vector<int>> ans;
        int l = 0;
        for(int r = n-1; r > 0; r--){
            int d = 0;
            if(a[r] != dq.back()){
                while(true){
                    int tmp = dq.front();
                    dq.pop_front();
                    d++;
                    if(tmp == a[r]) break;
                    else dq.push_back(tmp);
                }
                ans.push_back({l+1, r+1, d});
            }
            else dq.pop_back();
        }
        int k = ans.size();
        cout << k << "\n";
        for(vector<int> i : ans){
            for(int j : i) cout << j << " ";
            cout << "\n";
        }
    }
    return 0;
}

문제에서 정렬을 위한 최소 shift 를 찾을 필요는 없으며 단지 shift 횟수를 n 번 넘기지 말라고 했다.

예제를 풀다보면 segment 를 범위를 전체로 잡고 맨 끝에서부터 줄여 나가며 제일 큰 수가 나올 때 까지 회전시키면 항상 n-1 번 이하로 shift 하여 정렬이 가능하다는걸 알 수 있다.

이미 정렬된 배열과 덱을 사용하여 풀이하였다.

E1. Permutation Minimization by Deque

C++

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define all(c) c.begin(), c.end()
#define INF 1e9
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

int main(){
    fastio;
    int tc;
    cin >> tc;
    while(tc--){
        int n;
        cin >> n;
        vector<int> p(n);
        for(auto& i : p) cin >> i;
        deque<int> dq;
        for(int i : p){
            if(i < dq.front()) dq.push_front(i);
            else dq.push_back(i);
        }
        while(!dq.empty()){
            cout << dq.front() << " ";
            dq.pop_front();
        }
        cout << "\n";
    }
    return 0;
}

예전에 완전 똑같은 문제를 풀었던 것 같다.

배열의 값을 순서대로 덱에 넣어 가능한 사전적으로 작게 만들으라고 한다.

덱의 맨 앞의 값을 확인해가며 넣으려는 값보다 작으면 앞에 크면 뒤에 넣어주면 된다.

---

C. Ticks (Upsolving)

C++

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define all(c) c.begin(), c.end()
#define INF 1e9
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

int n, m, k;

bool solve(vector<string>& cell, vector<vector<bool>>& painted){
    for(int y = n-1; y >= 0; y--){
        for(int x = 0; x < m; x++){
            int d, ld, rd;
            int ny, nx;
            bool isTick = true;
            vector<pii> left, right;
            if(cell[y][x] == '*'){
                // left-top
                ld = 0;
                ny = y, nx = x;
                while(true){
                    ny--;
                    nx--;
                    if(ny < 0 || ny >= n || nx < 0 || nx >= m) break;
                    if(cell[ny][nx] != '*') break;
                    left.push_back({ny, nx});
                    ld++;
                }
                // right-top
                rd = 0;
                ny = y, nx = x;
                while(true){
                    ny--;
                    nx++;
                    if(ny < 0 || ny >= n || nx < 0 || nx >= m) break;
                    if(cell[ny][nx] != '*') break;
                    right.push_back({ny, nx});
                    rd++;
                }
                d = min(ld, rd);
                if(d < k) isTick = false;
                if(!isTick){
                    if(!painted[y][x]){
                        return false;
                    }
                }
                else{
                    for(int i = 0; i < d; i++){
                        painted[left[i].first][left[i].second] = true;
                        painted[right[i].first][right[i].second] = true;
                    }
                    painted[y][x] = true;
                }
            }
        }
    }
    return true;
}

int main(){
    fastio;
    int tc;
    cin >> tc;
    while(tc--){
        cin >> n >> m >> k;
        vector<string> cell(n, "");
        for(int y = 0; y < n; y++){
            cin >> cell[y];
        }
        vector<vector<bool>> painted(n, vector<bool>(m, false));
        if(solve(cell, painted)) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

문제 조건을 보면 tick 은 좌, 우로 정확히 d 만큼 칠해져야 한다고 적혀있는데 제멋대로 좌, 우 둘 중 짧은 길이의 tick 만 고려해서 구현하는 바람에 시스텟에서 터져버렸다.

후기

이번 코포는 독해와 구현에서 시간을 많이 뺏긴 것 같다. div.3 라 D 번도 어렵지 않았을텐데 읽지도 못하고 끝나서 아쉽다.