Codeforces Round 923 (Div. 3) upsolve

A. Make it White

흰색 타일(W)과 검정색 타일(B) 두 개가 일렬로 쭉 주어지는데, 일자로 한 번 칠해서 모두 흰색으로 바꾸려고 한다. 여기서 칠해야하는 min length를 구하는 문제. B가 처음 나오는 위치 ~ B가 마지막으로 나오는 위치를 찾아 길이를 출력하면 된다.

import sys
input = sys.stdin.readline
 
T = int(input())
 
for i in range(T):
    n = int(input())
    st = list(input().rstrip())
    res_min = n
    res_max = 0
    for s in range(n):
        if st[s] == 'B':
            res_min = min(s, res_min)
            res_max = max(s, res_max)
    print(res_max-res_min+1)

 

B. Following the String

#include <iostream>
#include <vector>
using namespace std;
int T;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> T;
 
    for (int i = 0; i < T; i++) {
        int N;
        cin >> N;
        vector<int> st(N);
        vector<int> alp(26, 0);
        string res = "";
 
        for (int s = 0; s < N; s++) {
            cin >> st[s];
            if (st[s] == 0) {
                for (int j = 0; j < 26; j++) {
                    if (alp[j] == 0) {
                        alp[j] += 1;
                        res += char(97 + j);
                        break;
                    }
                }
            }else {
                for (int j = 0; j < 26; j++) {
                    if (alp[j] == st[s]) {
                        alp[j] += 1;
                        res += char(97 + j);
                        break;
                    }
                }
            }
        }
        cout << res << '\n';
    }
    return 0;
}

for 문 안에 if else를 넣을지 반대로 할 지 고민했는데 그냥 빨리 내고 싶어서 아무렇게나 막짰다... 새벽이 될수록 심신미약 상태가 되는 기분이었다.

바보같은 인덱스 실수를 해서 이상한 패널티를 추가해버렸다. 요즘 내 학습 패턴이.. 실수하고 난 다음 깨지면서 배우게 된다. 참고로 왜 C++로 제출했냐면 같은 풀이의 pypy가 TLE로 터지길래 흠... 싶어서 그냥 바로 C++으로 돌렸더니 맞았다. 요즘 파이썬 최적화 생각을 안하고 그냥 냅다 쓰고 있는데 파이썬을 쭉 쓰고싶으면 다양한 최적화 방법을 살펴봐야한다......

내 python 코드 gpt에 C++으로 바꿔달라고 하면 AC 받는다.......

 

C. Choose the Different Ones !

import sys
input = sys.stdin.readline
T = int(input())
 
for i in range(T):
    N, M, K = map(int, input().split())
    nli = list(map(int, input().split()))
    mli = list(map(int, input().split()))
    Kli = [[0 for _ in range(K+1)] for _ in range(2)]
 
    for n in nli:
        if n <= K:
            Kli[0][n] += 1
 
    for m in mli:
        if m <= K:
            Kli[1][m] += 1
 
    n_only, m_only = 0, 0
    com = 0
    flg = 1
 
    for j in range(1, K+1):
        if Kli[0][j] or Kli[1][j]:
            continue
        else:
            flg = 0
            print('NO')
            break
 
    if flg == 1:
        for j in range(1, K+1):
            if Kli[0][j] and Kli[1][j]:
                com += 1
            elif Kli[0][j]:
                n_only += 1
            else:
                m_only += 1

        if n_only + com < K//2 or m_only + com < K//2:
            print('NO')
        else:
            print('YES')
 
    # 1~K까지 다 나온지 확인하고 yes or no
    # 각 li에서 겹치는건 상관x, 하나만 있는경우가 문제

핵심 아이디어를 콘테 치를 때 이미 주석으로 써놔서 주석으로 대체한다.

 

D. Find the Different Ones !

콘테 때 문제에 세그 쓰는건가??? 하고 착각해서 졸음이 쏟아지는 심신미약 상태로 쳐다보다가 자러간 문제이다. 물론 세그로 풀 수도 있긴 한데, 다른 분들의 의견과 코드를 살펴보니 안써도 충분히 풀 수 있었다. 멀쩡한 상태에서 문제를 다시 봤다.

index를 저장하는 배열을 따로 만들고, arr를 순차적으로 탐색하면서 이전과 다른 값이 나왔을 때 다른 값의 index 번호를 배열에 저장한다. 그리고 l, r을 받아서 해당 구간의 맨 마지막인 index[r]의 값과 l 인덱스의 대소 비교 조건으로 불가능한 경우를 걸러내면 된다.

import sys
input = sys.stdin.readline
T = int(input())

for _ in range(T):
    n = int(input())
    arr = list(map(int, input().split()))
    q = int(input())
    idx = [-1]*n

    for i in range(1, n):
        idx[i] = idx[i-1]
        if arr[i-1] != arr[i]:
            idx[i] = i-1 #다른거 나왔을 때 인덱스 배열 갱신

    #print(idx)

    for i in range(q):
        l, r = map(int, input().split())

        if idx[r-1] < (l-1): #배열 인덱스 차이 주의
            print(-1, -1)
        else:
            print(idx[r-1]+1, r)
    print()

 

 

E. Klever Permutation

여기까지 해야지..! 문제의 이름과 어울리게 순열을 관찰하면 특이한 성질이 보인다. 

대충 일반항

홀짝에 따라 특정하게 나뉘는 건 관찰했는데, 이걸 뭔가 깔끔하게 구현할 수 없을까 고민하다가 에디토리얼의 도움을 받았다. 반복문 안에서 l, r 투 포인터로 깔끔하게 구현된 코드였는데 보고 배웠다.. 우선 i가 홀수, 짝수 일 때 번갈아가며 l과 r 값을 각각 할당해주고 l은 왼쪽에서 오른쪽으로, r은 오른쪽에서 왼쪽으로 채워준다. 이렇게 하면 res 순열을 얻을 수 있다.

---

계속 해야지~ 생각만 하고 까먹고 있었는데 오늘 아침에서야 밀린걸 뚝딱 다썼다. 다른거 공부하느라 재밌어서 놓친 것 같다. LCA 공부한 것도 정리해야 하는데 시간이 부족하다..