경우없는 개발 블로그

A. Sakurako's Exam

a b 가 주어지는데 a개수만큼 1이 주어지고 b의 개수만큼 2가 주어지는데

각 숫자 사이에 부호를 + , -를 배치해서 0을 만들수 있는지 출력하는문제

a와 b의 개수를 파악해서 각자 짝수냐 홀수냐 그리고 1의개수를 잘 따지면 된다

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
 
 
int main() {
    
    int t;
    cin >> t;
 
    while (t--) {
        int a, b;
        cin >> a >> b;
 
        int remainB = 0;
        if (b % 2 != 0) {
            remainB = b % 2;
        }
 
        if (a  == remainB *2) {
            cout << "yes" << '\n';
        }
        else if (a % 2 != 0 || a == 0) {
            cout << "no" << '\n';
        }
        else {
            cout << "yes" << '\n';
        }
 
    }
 
    return 0;
}

B. Square or Not

정사각형의 테두리는 1이고 가운데는 0인 행렬로 만들 수 있는지 물어보는 문제

주어지는 입력이 한줄로 이뤄지기 때문에

이 한줄 입력을 정사각행렬에 맞춰서 인덱스 조회가 가능한지 물어보는 문제

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
 
 
int main() {
    
    int t;
    cin >> t;
 
    while (t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;
 
        bool flag = true;
 
        int root = sqrt(n);
        if (root * root != n) {
            flag = false;
        }
 
        for (int i = 0; i < root; i++) {
            if (s[i] != '1' || s[n - root + i] != '1') flag = false;
 
            if (s[i * root] != '1' || s[(i + 1) * root - 1] != '1') flag = false;
        }
 
        for (int i = 1; i < root - 1; i++) {
            for (int j = 1; j < root - 1; j++) {
                if (s[i * root + j] != '0') flag = false;
            }
        }
 
        if (flag) {
            cout << "yes" << '\n';
        }
        else {
            cout << "no" << '\n';
        }
    }
 
    return 0;
}

C. Longest Good Array

점점 증가하는 행렬을 만드는데 이전과 원소와의 차이도 증가하는 행렬을 만드는 문제

차이가 점점 증가하므로 등차수열을 활용하면 된다 

#include <iostream>
using namespace std;
 
 
long long sum_sequence(long long n) {
    return n * (n + 1) / 2;
}
 
int longest_array(int l, int r) {
    int diff = r - l;
 
 
    int left = 0, right = 10000000; 
    int max_n = 0;
 
    while (left <= right) {
        int mid = (left + right) / 2;
        if (sum_sequence(mid) <= diff) {
            max_n = mid; 
            left = mid + 1;
        }
        else {
            right = mid - 1; 
        }
    }
 
    return max_n + 1; 
}
 
int main() {
    int t;
    cin >> t; 
 
    while (t--) {
        int l, r;
        cin >> l >> r; 
 
 
        if (l == r) {
            cout << 1 << endl;
        }
        else {
            cout << longest_array(l, r) << endl;
        }
    }
 
    return 0;
}

D. Sakurako's Hobby

각 배열을 흰색 혹은 블랙으로 이뤄져있고

각 배열의 인덱스 i 에서 배열의 원소가 3이라면 3의 인덱스를 참조하고 배열의 인덱스 3 의 p[3] 원소를 또참조해서 만나는 블랙의 원소들의 개수를 전부 카운팅 하는 문제

말그대로 구현문제이다.

#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
 
 
int main() {
    int t;
    cin >> t;
 
    while (t--) {
        int n;
        cin >> n;
 
        vector<int> p(n);
        vector<int> F(n, -1);
        vector<bool> visited(n, false);
 
        for (int i = 0; i < n; i++) {
            cin >> p[i];
            p[i]--;
        }
 
        string s;
        cin >> s;
 
        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;
 
            vector<int> cycle;
            int x = i;
            while (!visited[x]) {
                visited[x] = true;
                cycle.push_back(x);
                x = p[x]; 
            }
 
 
            int black_count = 0;
            for (int idx : cycle) {
                if (s[idx] == '0') black_count++;
            }
 
            for (int idx : cycle) {
                F[idx] = black_count;
            }
        }
 
        for (int i = 0; i < n; i++) {
            cout << F[i] << " ";
        }
        cout << endl;
    }
 
    return 0;
}

https://codeforces.com/problemset/problem/1995/A

#전체 코드

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <climits>
using namespace std;
 
int main() {
    
    int t;
    cin >> t;
 
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<int> diagonals(n + 1, 2);
        diagonals[n] = 1;
 
        int placeCount = 0;
 
        while (k > 0) {
            for (int i = k; i > 0; i--) {
                if (i <= n && diagonals[i] > 0) {
                    k -= i;
                    diagonals[i]--;
                    placeCount++;
                    //cout << "k:" << k << '\n';
                    if (k == 0) {
                        break;
                    }
                    break;
                }
            }
        }
 
        cout << placeCount << '\n';
 
    }
 
 
 
}

#문제 간단 정리

prefix 와 subfix 가 존재하고

prefix 는 x 까지 이전의 값들끼리 더했을때 최대가 되는 인덱스

subfix 는 y 이후 값들끼리 더했을 떄 최대가 되는 인덱스

y<x 로 주어진다

n길이의 배열로 n x y를 만족하는

배열을 구하라(반드시 존재함)

#문제 해결 방법

우선 x<y 기 때문에

x와 y 사이에는 무조건 1로 채워주는 게 배열을 만들기 가장 쉽다.

왜냐면 가운데는 두 서브픽스와 프리픽스 전부다 영향을 주기 때문이다.

그래서 x 이후에는 감소해야 prefix 가 고정되기 때문에

변갈아서 -1 로 바꿔주고

y 이전에도 번갈아서 -1로 바꿔준다

번갈아서 -1을 해주지 않을 경우에는 반례가 존재하기에 

번갈아서 바꿔줘야한다.

12 7 6 같은 경우가 존재 할 수 있다. (번갈아서 안바꾸면)

#전체 코드

#include <iostream>
#include <vector>
using namespace std;


int main() {
    int t;
    cin >> t;

    while (t--) {
        int n, x, y;
        cin >> n >> x >> y;
        vector<int> a(n, 1);

        // x 이후의 1의 개수보다 -1의 개수가 많아야 한다
        for (int i = x; i < n; i += 2) {
            a[i] = -1;
        }

        // y 이전의 1의 개수보다 -1의 개수가 많아야 한다
        for (int i = y-2; i >=0; i -= 2) {
            a[i] = -1;
        }


        for (int i = 0; i < n; ++i) {
            cout << a[i] << " ";
        }
        cout << endl;
    }

    return 0;
}

#문제 간단 정리

mx는 처음에 0으로 주어진다

배열에서 고르면 그 고른 값으로 mx 가 결정되고

상대방에 턴에는 mx 이상인 값만 고를 수 있다.

alice 가 이길 수 있는지 없는지 리턴하라는 문제

#문제 해결 방법

요지는 모든 숫자를 카운팅 소트를 해준 다음에

모두가 짝수로 존재한다면 패배하고

홀수개수가 존재한다면 승리한다

왜냐하면 일단 가장 높은 숫자의 개수가 짝수개라면

먼저 선택하지 않고 

홀수 개수를 먼저 선택하면 이길 수 있기 때문

5

3 3 3 4 4

일때 3 을 먼저 선택하면 이길 수 있다

만약 가장 높은 숫자가 홀수개라면 그냥 이길 수 있다

6

3 3 3 4 4 4

#전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
 
    while (t--) {
 
        //첫턴에 mx를 설정 가능하고, 모든 값들이 mx 이하라면 승리
        //현재 가장 높은게 홀수개라면 승리 짝수개라면 패배
 
        int n;
        cin >> n;
 
        vector<int> counting(10002, 0);
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
 
        for (auto i : a) {
            counting[i]++;
        }
 
        vector<int> compress;
 
        for (int i = 10001; i > 0; i--) {
            if (counting[i] != 0) {
                compress.push_back(counting[i]);
            }
        }
 
        bool win = false;
        for (auto i : compress) {
            if (i % 2 == 0) {
            }
            else {
                win = true;
            }
        }
 
 
        if (win) cout << "YES" << '\n';
        else cout << "NO" << '\n';
    }
 
    return 0;
}