Codeforces Round #599 (Div. 2) 후기

[푼 문제] - A, B1, C

 

A. Maximum Square

 

널판지(planks)로 만들 수 있는 최대 정사각형의 한변의 길이를 구하는 문제.

내림차순 정렬하고 인덱스와 비교하면서 한번 훑으면 된다.

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    N = int(input())
    k = list(map(int, input().split()))
    k.sort(reverse=True)
    ans = 0
    for i in range(N):
        if k[i] < i + 1:
            ans = i
            break
    if k[N-1] >= N:
        ans = i+1
    print(ans)

 

B1. Character Swap (Easy Version)

 

두 문자열의 문자를 '최대 1번' 교환해서 문자열을 같게 만들 수 있는지 판별하는 문제.

문자열을 같게 만들 수 있으려면 (1) 매치 안되는 문자가 2개이면서 (2) 한 문자열에서 그 두 문자가 같아야한다.

즉, s = "aa", t = "bb"이면 한번의 교환으로 "ab"로 같게 만들 수 있다.

for _ in range(int(input())):
    N = int(input())
    s = input()
    t = input()
    idx = [-1, -1]
    cnt = 0
    ans = "YES"
    for i in range(N):
        if s[i] != t[i]:
            if cnt == 2:
                cnt = -1
                ans = "NO"
                break
            idx[cnt] = i
            cnt += 1
    if cnt == 1:
        ans = "NO"

    if cnt == 2:
        if s[idx[0]] != s[idx[1]] or t[idx[1]] != t[idx[0]]:
            ans = "NO"
    print(ans)

 

C. Tile Painting

 

N개의 타일을 채울 수 있는 최대 색깔의 수를 구하는 문제.

이때 타일 사이 간격을 k라 하면 N mod k = 0 ( k > 1 )이면 같은 색으로 칠해야한다.

맨 처음에 가장 작은 약수로 생각했지만 틀렸고

N = 12에 경우 2와 3이 12에서 같은 색이니 결국 모든 타일 색이 같아지는 것을 보고

가장 큰 약수에서 몇개 빼서 제출했지만 또 틀렸다.

 

N = 15일 때, 3과 5가

3 * 5 + 0 = 5 * 3

3 * 3 + 1 = 5 * 2

3 * 1 + 2 = 5 * 1

이 되는 것을 보고 임의의 거듭제곱이 아닌 소인수 a, b에 대해서

an + k = bm가 0 <= k < a인 k에 대해 모두 성립하는건가??하고

소인수 분해 했을 때 수 1개의 거듭제곱꼴이 아니면 1로하고 제출하니 맞았다.

두 수가 소수면 저게 성립하나보다.

 

그리고 시간이 한참 지나있었다.

import sys
import math
input = sys.stdin.readline

N = int(input())
k = N
ans = set()

while True:
    if k == 1 : break
    q = k
    for i in range(2,int(math.sqrt(k))+2):
        if k % i == 0:
            ans.add(i)
            k //= i
            break
    if k == q:
        ans.add(k)
        break

if N == 1: print(1)
elif len(ans) == 1: print(*ans)
else: print(1)

 

[끝나고 푼 문제] - B2

 

B2. Character Swap (Hard Version)

 

B1에서 확장해서 최대 2N번 교환해서 문자열을 같게 만들 수 있는지 묻는 문제다. 교환하는 순서도 출력해야한다.

 

만약 문자가

a1 b  c

d  e  a2

이렇게 있으면 b a2를 교환하고 a2와 d를 교환하면 첫번째 문자를 일치시킬 수 있다.

그렇게 교환하면 두번째 문자부터 다시 반복하면 되고

매치 안되는 문자가 짝수였으니 결국 마지막에는 B1처럼 aa bb 이런식으로 남아서 N-1까지 교환하면 완료된다. 

 

이걸 파악하고 구현하려니까 결국 시간 안에 못했다. 괜히 N^2이 아니라 N에 하려다가 에러가 잔뜩 났다.

import sys
input = sys.stdin.readline

for q in range(int(input())):
    N = int(input())
    s = list(input().rstrip())
    t = list(input().rstrip())
    ans = []
    for i in range(N-1):
        if s[i] != t[i]:
            for j in range(i + 1, N):
                if s[j] == s[i]:
                    ans.append((j + 1, i + 1))
                    s[j], t[i] = t[i], s[j]
                    break
                if t[j] == s[i]:
                    ans.append((i + 2, j + 1))
                    s[i + 1], t[j] = t[j], s[i + 1]
                    ans.append((i + 2, i + 1))
                    s[i + 1], t[i] = t[i], s[i + 1]
                    break

    flag = True
    for i in range(N):
        if s[i] != t[i]:
            flag = False
            
    if flag:
        print("Yes")
        print(len(ans))
        for u,v in ans:
            print(u, v)
    else:
        print("No")

끝나고 N^2으로 작성해보니 허무하게 쉽다.

 

 

 

 

1.

학기 중이라 요즘 코포 한번 보는게 힘들다.

또한 올해 안에 블루 가는 것이 목표로 하고 올해가 거의 다 가고있다보니

한번 볼때마다 잘 안되면 좀 화난다 후..

 

2. 

C만 빨리 풀었어도 B2 풀고 블루 갈 수 있었을 것 같은데 아쉽다.

그래도 C 못 풀어서 레이팅 하강했으면 잠시 코포 접을뻔했는데 다행이다.

 

3.

코포도 같이 하는 사람이 있어야 더 즐거운 것 같다.

학교에서 스터디 하는 사람들끼리 코포 끝나고 이야기하는게 재밌었다.