Codeforces 라운드 #595 (Div. 3)

요즘 알고리즘 인터뷰 하는 것이 대세인지라 PS를 조금 해봤는데, 생각보다 재미있어서 좀더 깊게 파봐야 겠다는 생각을 했다. 대회에만 나오는 알고리즘까지 공부하고 싶진 않지만 문제풀이 자체는 재미있는지라 꾸준히 참여해보려 한다.

1249A

조건대로 가면 1 그룹 아니면 2 그룹으로 나뉘어진다. 정렬하고 차이 1 나는거 있으면 1 아니면 2 출력해서 끝

1249B1

문제에서 요구하는 그대로 코드로 옮겼다.

tc = int(input())
for _ in range(tc):
    n = int(input())
    p = list(map(int, input().split()))
    for i in range(n):
        ans = 1
        pos = p[i]
        while pos != i+1:
            ans += 1
            pos = p[pos-1]
        print(ans, end=' ')
    print()

1249B2

위 문제와 같으나 쿼리가 1000개로 증가, n 의 값도 2*10⁵으로 증가했다. 위의 방법대로 풀면 TLE가 나게 되므로 최적화 할 방법을 생각해야 한다.
예제 입력인 4 6 2 1 5 3 를 살펴보면 첫번째 숫자인 4는 1을 거쳐 다시 4가 되고, 네번째 숫자인 1의 경우엔 4를 거쳤다가 다시 4가 되는 것을 알수 있다. 마찬가지로 두번째 6의 경우는 3 -> 2를 거쳐서 돌아오고, 세번째 2의 경우 6->3을 거쳐서 자신으로 돌아온다. 이는 자신으로 돌아올때까지 만나는 모든 숫자는 같은 횟수를 가진다는 의미이므로 이를 이용하면 O(N)으로 중복 계산을 없앨 수 있다.

tc = int(input())
for _ in range(tc):
    n = int(input())
    p = list(map(int, input().split()))
    res = [0]*n
    for i in range(n):
        if res[i] == 0:
            ans = 1
            pos = p[i]
            cycle = [i]
            while pos != i+1:
                cycle.append(pos-1)
                ans += 1
                pos = p[pos-1]
            for c in cycle:
                res[c] = ans
    print(*res)

1941C1

1941C2

3진법으로 표기했을 때 2가 없으면 그대로 출력하고, 2가 있으면 2가 있는 자리까지는 0으로 바꾸고 자릿수 Carry를 올려주는 방식으로 풀었다.

tc = int(input())
for _ in range(tc):
    n = t = int(input())
    nums = []
    while n:
        nums.append(n % 3)
        n //= 3
    if 2 not in nums:
        print(t)
    else:
        carry = 0
        for i in range(len(nums)):
            nums[i] += carry
            carry = 0
            if nums[i] >= 2:
                for j in range(i + 1):
                    nums[j] = 0
                carry = 1
        if carry:
            nums.append(1)
        ans = 0
        for i in range(len(nums)):
            ans += nums[i] * (3**i)
        print(ans)

1249D1

인덱스를 앞에서 부터 조사해 나가다가 겹치는 부분이 k보다 크면 가장 긴 세그먼트를 제거해주면 된다.
입력 크기가 크지 않아 O(N³)로 풀어도 된다.

n, k = map(int, input().split())
segs = [0] * n
max_idx = 210
cnt = [0] * max_idx

for i in range(n):
    l, r = map(int, input().split())
    segs[i] = (l, r)
    cnt[l] += 1
    cnt[r+1] -= 1

for i in range(max_idx-1):
    cnt[i+1] += cnt[i]

ans = [0] * n
for i in range(max_idx):
    while cnt[i] > k:
        pos = -1
        for p in range(n):
            if not ans[p] and segs[p][0] <= i <= segs[p][1] and (pos == -1 or segs[p][1] > segs[pos][1]):
                pos = p
        for j in range(segs[pos][0], segs[pos][1]+1):
            cnt[j] -= 1
        ans[pos] = 1

print(sum(ans[0:n]))
for i, v in enumerate(ans):
    if v:
        print(i+1, end=' ')

입력 받으면서 세그먼트의 왼쪽 끝 부분은 +1, 오른쪽 끝 다음 칸을 -1 한 후 인덱스 순서대로 숫자를 누적시키면 세그먼트의 누적합을 만들 수 있다.
1 0 0 3 3 5 2 2 4 0 0 1과 같은 형태가 되는데 이때 하나씩 탐색하며 k보다 많이 겹친 부분을 찾으면 모든 세그먼트를 탐색하며 k에 걸친 세그먼트 인지, 이미 삭제된 세그먼트 인지 (ans 리스트에 체크) 확인 후 가장 긴 세그먼트를 pos에 넣고 그 세그먼트의 누적합을 제거한다.

1249D2

위쪽 문제와 동일하나 입력 크기가 크다. 세그먼트의 왼쪽 인덱스를 기준으로 오른쪽 인덱스가 가장 긴 순서로 쌓아놓고, 인덱스의 처음부터 순회하며 세그먼트가 있을때마다 추가하고, 만약 세그먼트의 중복 크기가 k를 넘으면 가장 오른쪽으로 긴 세그먼트를 제거한다. 가장 긴 세그먼트를 제거해야하므로 추가 후 순서가 정렬되어 있어야 한다. 이 부분이 가장 시간소모가 크므로 heap을 이용해서 삽입과 동시에 정렬이 최적화 되도록 한다.

import sys
from heapq import *

n, k = map(int, input().split())
N = int(2e5 + 2)
ll = [[] for _ in range(N)]
rr = [[] for _ in range(N)]
vis = [0] * N

for i in range(n):
    l, r = map(int, sys.stdin.readline().split())
    ll[l].append((-r, i + 1))
    rr[r].append(i + 1)

q = []
ans = []
size = 0

for i in range(1, N):
    for j in ll[i]:
        heappush(q, j)
        size += 1

    while size > k:
        cur = heappop(q)
        while vis[cur[1]]:
            cur = heappop(q)
        vis[cur[1]] = 1
        ans.append(cur[1])
        size -= 1
    for j in rr[i]:
        if not vis[j]:
            vis[j] = 1
            size -= 1

print(len(ans))
print(*ans)

입력속도가 빠른 stdin으로 입력 받지않으면 그냥 처리하다가 TLE 나므로 주의한다. 입력받을때 세그먼트의 왼쪽 끝 위치의 인덱스에 오른쪽 끝 인덱스와 세그먼트의 순서를 쌍으로 집어넣는다. 이때 -r으로 집어넣어야 나중에 최대값을 꺼낼때 편하다. (Python heap이 기본적으로 min heap이므로..) 이후 입력을 전부 순회하며 heap에 세그먼트를 넣고, 만약 heap의 크기가 k보다 커지면 heap에서 뽑아낸다. 마지막 for 문과 swhile문 안의 while은 현재 조회하는 인덱스가 세그먼트의 오른쪽 끝을 넘었다면 해당 세그먼트를 제거하는 역할을 한다.

1249E

간단한 dp 문제 2차원 리스트를 만든 후 이전 상태와 현재 상태의 최소 시간을 비교하면 된다. dp[0]은 엘레베이터 -> 걷기, 걷기 -> 걷기 중 최소값을 dp[1]은 걷기 -> 엘레베이터, 엘레베이터 -> 엘레베이터 최소값을 저장한다. 이후 dp[0]과 dp[1] 중 최소값을 층별로 출력하면 된다.

n, c = map(int, input().split())
dp = [[0] * n, [0] * n]

a = list(map(int, input().split()))
b = list(map(int, input().split()))

dp[0][0] = 0
dp[1][0] = c
for i in range(n-1):
    dp[0][i + 1] = min(dp[1][i] + a[i], dp[0][i] + a[i])
    dp[1][i + 1] = min(dp[1][i] + b[i], dp[0][i] + b[i] + c)

for i in range(n):
    print(min(dp[0][i], dp[1][i]), end=' ')

1249F

파이썬으로 못풀겠음. 푼 다른 사람도 없다. PS고급문제 하려면 C++은 필수인듯