Codeforces Round #944 (Div. 4)

ㅇㅇ · 2024.05.11 02:44:38

개인적으로 쓴 글입니다. 약간 깁니다.

# Codeforces Round #944 (Div. 4)

잘 풀다가 마지막 H 문제 보고 충격받아서 미리 복기나 하기로 함.

## Problem A. My First Sorting Problem

설명이 필요없는 문제.

Div 3/4에서 A~C번 문제를 풀 때는 <m2.codeforces.com>을 애용하자.
m1도 버벅거리더라.
Div 2도 A번 문제는 미러사이트에서 푸는게 쾌적하는 사실.

```python
import sys

def main() -> None:
    input = sys.stdin.readline
 
    for _ in range(int(input())):
        a, b = map(int, input().split())
        print(min(a, b), max(a, b))

sys.exit(main())
```

## Problem B. Different String

본문을 읽다가 한 칸 옮기면 되겠다는 생각이 들었다.
예제에 `NO`가 있길래 "언제 안 되지?"라고 생각했는데, 당연히 모든 문자가 같으면 안 된다.
코드를 적으면서 정당성 증명을 했다.
문자가 서로 다른 곳에서 한 칸 씩 이동하면 당연히 두 위치의 문자가 달라지니까...

```python
import sys

def main() -> None:
    input = sys.stdin.readline

    for _ in range(int(input())):
        s = input().strip()

        if len(set(s)) == 1:
            print("NO")
        else:
            print("YES")
            print(s[1:] + s[0])

sys.exit(main())
```

## Problem C. Clock and Strings

이제 좀 문제다운 문제가 나온다고 생각했다.
12-1 에 불연속이 있어서 어떻게 판단할까 고민했는데, 모든 수가 서로 다르다는 조건이 있어서 off-by-one 에러는 없겠거니 했고, a, b를 정렬하고 나면 그 사이 범위는 무조건 깔끔하게 나오니까 그 사이에 c가 있고, d는 그 밖에 있으면 되겠다고 생각했다.
그래서 처음에 조건문을 `(a < c < b) and not (a < d < b)`으로 썼었은데 다행히 예시에서 걸려서 고쳐냈다.
일단 무지성 xor로 고쳐서 통과했다.
한참 뒤에 (G번 풀고 나서) 다시 보니 10, 12, 11, 1 같은 경우에는 c, d의 포함관계가 바뀐다는걸 깨달았다.

```python
import sys

def main() -> None:
    input = sys.stdin.readline

    for _ in range(int(input())):
        a, b, c, d = map(int, input().split())

        if a > b:
            a, b = b, a
        if c > d:
            c, d = d, c

        if (a < c < b) ^ (a < d < b):
            print("YES")
        else:
            print("NO")

sys.exit(main())
```

## Problem D. Binary Cut

와 진짜 이번 셋은
`A<B<C<E<F<G < D <<< H`
인거같다.

처음에는 막 "01" 개수랑 "10" 개수 세고 첫 문자가 "0"이냐 "1"이냐로 식 세우면 되겠거니하고 온갖 짓을 다 해봤는데 안 됐다.
일단 그리디는 맞는거 같았고, 말로 정확하게 표현하기는 애매한데 "우리가 만들려고하는게 0..01..1" 꼴이니까 첫 번째로 나온 "01"은 공짜다(?)" 라는 생각이 들었다.
아래 코드를 보면 `while True` 무한루프가 나오기 전에 while문이 2개 더 있는데, 이게 그걸 반영한거다.
deque 사용해서 짜다가 "아 인덱스 순회하는게 더 효율적이겠는데" 생각이 들었지만 이런들 어떠하리 저런들 어떠하리 O(n)이니까 그냥 냅뒀다.

아 그리고 `while t[0] == "0"` 이런 식으로 적었다가 예제에서 걸렸는데, `while t and t[0] == "0"` 이렇게 적는게 맞다.
단순 실수지만 조심하자!

```python
import sys
from collections import deque

def main() -> None:
    input = sys.stdin.readline

    for _ in range(int(input())):
        s = input().strip()
        print(solve(s))

def solve(s: str) -> int:
    t = deque(s)
    ans = 0

    if t[0] == "1":
        ans += 1
        while t and t[0] == "1":
            t.popleft()

    if not t:
        return ans

    ans += 1

    while t and t[0] == "0":
        t.popleft()
    while t and t[0] == "1":
        t.popleft()

    if not t:
        return ans

    c = "0"
    while True:
        ans += 1
        while t and t[0] == c:
            t.popleft()
        if not t:
            return ans
        c = "1" if c == "0" else "0"

sys.exit(main())
```

## Problem E. Find the Car

문제 읽으면서 "누적합인가" 생각 했는데, main함수 입력 부분을 짜면서 "아니다 비례식+이분탐색이구나"라고 생각했다.
하.. 근데 내가 이분탐색만 하면 불안한게
1. bisect_left인가 bisect_right인가?
2. 가끔씩 찾을 값을 (값-1)이나 (값+1)로 바꿔써야되는 경우가 있음
3. 인덱스 i 찾고 나서도 i-1, i+1로 바꿔서 써야되는 경우가 있음
이게 항상 헷갈린다.
차라리 파라메트릭 서치는 lo+1 < hi가 만능이라서 편한데 ㅋㅋ

일단 이 문제에서 bisect_left를 쓰는것과 값을 그대로 쓰는건 다행히 확신이 들었는데...
if d == arr[i]: result = brr[i]
여기까지 쓰고 나서 "아 그다음은 어떡하지?"라는 생각이 들었다.
처음에는 result = brr[i] + (d - arr[i]) * (brr[i+1] - brr[i]) / (arr[i+1] - arr[i])
이렇게 썼다가 틀렸다.
그래서 막 print로 디버깅하면서 고쳤다. 휴...

근데 딱 제출창에 복붙하고 나니까 실수오차 걱정이 되더라.
근데 예제 통과했으니 괜찮겠지 싶었고, 일단은 통과했다.
wa 핵 당할 수도 있겠다 ㅠㅠ 근데 당해도 할 말은 없다...

```python
import bisect
import sys

def main() -> None:
    input = sys.stdin.readline

    for _ in range(int(input())):
        n, k, q = map(int, input().split())
        arr = [0] + list(map(int, input().split()))
        brr = [0] + list(map(int, input().split()))
        qrr = [int(input()) for _ in range(q)]

        ans = solve(arr, brr, qrr)
        print(" ".join(map(str, ans)))

def solve(
    arr: list[int],
    brr: list[int],
    qrr: list[int],
) -> list[int]:
    results = []

    for d in qrr:
        i = bisect.bisect_left(arr, d)

        if d == arr[i]:
            result = brr[i]
        else:
            result = brr[i - 1] + (d - arr[i - 1]) * (brr[i] - brr[i - 1]) / (arr[i] - arr[i - 1])

        results.append(int(result))

    return results

sys.exit(main())

```

## Problem F. Circle Perimeter

백준에서 최근에 풀었던거 같은데 뭐였지? 고민하다가 기억 안나서 그냥 풀기로 했다.
일단 축 위에는 점이 무조건 하나면 있고, 각 사분면에 있는 점 개수를 count라고 하면
4 * count + 4가 답이겠구나하고 count를 구했다.
축에 걸리는 점을 빼기 위해 y를 1부터 시작하는게 중요하다면 중요했던거 같다.

코포 치기전에 종이랑 펜 준비 해두자.
간단한거라도 적으면서 정리하면 깔끔하고 생각하기도 수월하다.

```python
import sys


def main() -> None:
    input = sys.stdin.readline

    for _ in range(int(input())):
        r = int(input())
        print(solve(r))


def solve(r: int) -> int:
    ans = 0
    for t in range(1, r + 1):
        y2 = r * r - t * t
        y = max(1, int(y2**0.5) - 1)
        while t * t + y * y < r * r:
            y += 1
        y0 = y
        while t * t + y * y < (r + 1) * (r + 1):
            y += 1
        y1 = y

        cy = y1 - y0

        ans += cy

    ans = 4 * ans + 4

    return ans


sys.exit(main())
```

## Problem G. XOUR

이거 살짝 념글갔던 "ps 싸대기 마려운 화법"일수도 있겠는데, 진짜 보자마자 풀이가 떠올랐다.
어차피 스왑은 xor이 4 미만이어야 가능하니까 윗 비트들이 같은거 끼리만 스왑된다.
그러면 윗 비트들이 다른 그룹들끼리는 교환이 일어나지 않으므로, 윗 비트들의 그룹을 나눠서 정렬하면 된다.
그리고 기존 키들(윗 비트)들의 순서를 기억해놓고, 그것에 해당하는 그룹의 제일 앞 수를 뽑아내면 된다.
또 deque 썼다.

그룹을 나눌때 dict 자료형을 썼는데, 해시 저격이 불안해서 str으로 바꾸고 앞뒤로 스트링도 붙였다.

```python
import sys
from collections import defaultdict, deque

salt = "abc"

def main() -> None:
    input = sys.stdin.readline

    for _ in range(int(input())):
        n = int(input())
        arr = list(map(int, input().split()))
        print(" ".join(map(str, solve(n, arr))))


def solve(n: int, arr: list[int]) -> list[int]:
    keys = [x >> 2 for x in arr]
    arr.sort()
    st = defaultdict(deque)
    for a in arr:
        st[salt + str(a >> 2) + salt].append(a)

    result = []
    for k in keys:
        result.append(st[salt + str(k) + salt].popleft())

    return result

sys.exit(main())
```

## Problem H. ±1

아니 이거 문제 이해하는데 한참 걸렸다.
또 한참 생각하다가 이거 SAT인데 싶었다.
아니 그래도 설마 div 4에 출제자가 미쳐서 SAT을 내겠냐 ㅋㅋ 했는데
아무리 생각해도 이건 SAT이다...
randomization + backtracking 생각도 해보고...
혹시 내가 잘못 생각한 조건이 있나? 애드혹인가?
막 한 column에 무조건 같은 변수가 두개씩은 들어가는게 특정 proportion을 넘겨서 그런거 없애면 막 O(log n)개만 남고 그런 놀라운 관찰이 필요한가?
오오 좀 정리 했는데 -a1 a2 a1 같은 경우는 a2=1이 고정이 되네? 이런걸 쓰는건가?
했는데 그래도 SAT이더라.

그래서 그냥 깔끔하게 포기했다.
일단 7솔에 hack당해도 6솔이 무너지진 않을거 같아서.

그리고 이 글쓰기 시작했다. 근데 푼 사람 별로 없는거 보면 잘 한 선택인거 같다 ^o^

번호	말머리	제목	글쓴이	작성일	조회	추천
2872	설문	연예인 안됐으면 어쩔 뻔, 누가 봐도 천상 연예인은?	운영자	24/06/17	-	-
44906	공지	피갤컵 call for tasks를 진행합니다! [6]	*나는최고*	24.05.22	805	16
44466	공지	[ps 정보글 모음집] [2]	*나는최고*	24.05.07	964	13
44058	공지	알고리즘 대회 공부 과정 [22]	*나는최고*	24.04.20	2804	31
19170	공지	규칙 v2022.02.16 [8]	*0xrgb*	22.02.06	6844	36
1	공지	와 PS! [24]	*0xrgb*	18.05.28	21984	30
45743	일반	근데 어차피 모비스 그런 알고리즘 상금 큰대회는 [3]	ㅇㅇ(222.236)	20:36	28	1
45742	일반	백준 개씨;빨년들 진짜 존나 빡치게 하네 씨빨지나ㅉ [5]	ㅇㅇ(115.139)	20:27	50	0
45741	일반	내일이면 종강이군	Miyano	20:01	38	0
45740	팁	Problem Solving effect graph	ㅇㅇ(223.39)	19:24	93	5
45736	일반	요새도 종만북이 제일인가요?	ㅇㅇ(211.234)	18:51	59	2
45735	일반	다들 닥치고 문제나 풀어라	ㅇㅇ(106.101)	18:25	120	8
45734	일반	골3까지는 무슨문제를 줘도 30분컷 달성하고싶다.. [3]	ㅇㅇ(221.145)	17:43	153	0
45733	일반	안녕하세요. 비추 주세요. [4]	ㅇㅇ(147.47)	17:42	242	31
45732	일반	PS == 스타크래프트 [1]	ㅇㅇ(211.253)	17:18	128	4
45731	일반	좆목충들 많아서 그럼거임 ㅋㅋ [8]	ㅇㅇ(223.39)	17:15	305	21
45730	일반	비추 무서워서 갤질 못하냐고들 하는데 [7]	ㅇㅇ(222.112)	17:00	232	6
45729	일반	PS뉴비 랜덤마라톤에서 브5문제 떴는데 이거 진짜 브5에요?! [4]	ㅇㅇ(115.22)	15:59	203	0
45728	일반	오늘도 애드혹 답지를 봤다 [6]	ㅇㅇ(211.217)	15:13	190	1
45726	질문	트라이 구현 상수 질문 [7]	치사토쨩	13:12	154	0
45724	일반	얘들아 운동해라.. [3]	아마게	12:12	221	1
45723	일반	여기는 비추가 너무 많음 [13]	ㅇㅇ(118.235)	12:09	345	11
45721	질문	병특 고민상담 [9]	병특러(121.134)	10:48	326	4
45720	일반	개똥같은 윈도우쓰레기개발그만하고 ps나 하고싶네 [1]	고추꺼내봐	10:43	174	0
45719	일반	난 다이아 밑으로는 사람 취급 안한다 [1]	ㅇㅇ(49.165)	10:33	219	1
45718	일반	ps [12]	ㅇㅇ(121.66)	08:41	322	11
45716	일반	선생님들 지금 부트캠프 개발자 준비하면 안되나요? [21]	ㅇㅇ(1.229)	02:38	397	1
45715	일반	구현문제에 6시간 꼬라박았는데	ㅇㅇ(220.76)	02:07	135	3
45714	일반	사이트개발자인 친구가 여기에서 기초닦으래서 왔습니다 [3]	ㅇㅇ(112.148)	01:41	276	1
45713	일반	PS 관련 커뮤는 여기 밖에 없음??? [6]	ㅇㅇ(223.39)	00:36	307	0
45712	일반	행렬 제곱 문제가 왜 분할정복인지 설명좀 해줄 수 있음? [3]	ㅇㅇ(123.214)	00:07	252	1
45711	일반	C++ 배우려는데 온라인으로 쓸 수 있는 자료 추천점요 [12]	ㅇㅇ(24.30)	06.20	207	1
45710	일반	그래도 나보다 위에 있는 사람이 있다는게 좋은 순환이 아닐까? [1]	ㅇㅇ(119.195)	06.20	189	0
45709	일반	아니 진짜 의문이네 [1]	ㅇㅇ(119.202)	06.20	269	2
45708	일반	팩트는 PS를 끊어야 건강해진다는거임 [1]	ㅇㅇ(223.39)	06.20	325	3
45707	일반	피갤은 요즘 커뮤 정서와 정반대인거 같음 [17]	ㅇㅇ(223.39)	06.20	716	21
45706	일반	바킹독님 그리디 해설 중에	코더(59.16)	06.20	190	5
45705	일반	솔브드 플래티넘까진 걍 허접들임 [8]	ㅇㅇ(223.39)	06.20	497	16
45704	일반	이쯤되면 골드를 골드라고 정의한 솔브드 잘못이다 [3]	ㅇㅇ(106.101)	06.20	341	0
45702	일반	솔브드 문제풀은수 계속 줄어드는데 뭐임...? [3]	ㅇㅇ(223.33)	06.20	267	0
45701	일반	뉴비 랜덤마라톤 마지막 문제 절망 [1]	ㅇㅇ(117.111)	06.20	202	0
45699	일반	C언어 처음 입문해보려는데 [7]	ㅇㅇ(211.234)	06.20	219	0
45698	일반	스마트테크 코리아 다녀감 [2]	ㅇㅇ(220.75)	06.20	230	1
45697	일반	옛날 백준은 코드 비공개가 기본이었나	ㅇㅇ(118.235)	06.20	176	0
45696	일반	팩트는 랜디를 하면 건강해진다는 거임 [11]	노는게제일좋아	06.20	359	0
45695	일반	형들 뉴비 질문좀 받아줘 [6]	ㅇㅇ(14.37)	06.20	157	1
45694	일반	골랜디만 계속하면 코포어디까지 가능함? [18]	ㅇㅇ(223.39)	06.20	378	0
45693	일반	뉴비 코포해보니까 [1]	ㅇㅇ(180.70)	06.20	118	0
45692	질문	dp랑 그리디는 도대체 어떻게 공부해야 되는 거지 [7]	ㅇㅇ(121.134)	06.20	223	1
45691	일반	백준 로그인하는데 누가 내 실2소스 들여다봤길래 [7]	코더(59.16)	06.20	310	3
45690	일반	ps 공부 다시 시작한다 시발... [12]	노럐	06.20	330	5
45689	일기	3주차 마라톤 완	ㅇㅇ(182.215)	06.20	187	5
45688	일반	lcs 6을 풀다가 [5]	ㅇㅇ(106.101)	06.20	222	0
45686	일반	코테준비할때 솔브닥 많이푼 순서대로 푸는거 어케생각함? [9]	ㅇㅇ(221.145)	06.19	297	0
45684	일반	아이돌이 말아주는 C++ [3]	ㅇㅇ(24.30)	06.19	370	3
45683	일반	개발로 먹고 살려면 java도 시작해봐야 하나 [10]	ㅇㅇ(223.39)	06.19	348	0

최근 방문

즐겨찾기

즐겨찾기 갤러리

마이너 갤러리 이슈박스, 최근방문 갤러리

연관 갤러리

마이너 갤러리 소개

차단하기

[PS 갤러리]

갤러리 본문 영역

게시물을 간편하게 NFT로 만들어 보세요!

NFT 발행 방법

NFT 발행

비회원 글삭제,수정

추천 비추천

댓글 영역

① NFT 발행

② NFT 구매

하단 갤러리 리스트 영역

왼쪽 컨텐츠 영역

갤러리 리스트 영역

페이지 이동

오른쪽 컨텐츠 영역

알림 설정

알림

디시콘 리스트

디시콘

디시콘 검색결과(0)

인기 디시콘

지갑 연결