Log for everything - Day

USACO 2015 February (Bronze)

03 Mar 2020 | Python USACO PS

USACO 2015 February

1. Censoring

글자에서 해당 문자가 나타나는지 확인 후, 나타나면 삭제하는 문제. 문제에서 주어진 순서대로 문자를 삭제할 경우, 문자열 전체를 훑어야 하므로 TLE가 뜬다. 결과 문자열의 뒷부분이 일치하는지를 확인하는 방식으로 시간을 줄일 수 있다.

with open("censor.in", "r") as f:
    s = f.readline().strip()
    t = f.readline().strip()

r = ''
for i in range(len(s)):
    r += s[i]
    if len(r) >= len(t) and r[-len(t):] == t:
        r = r[:-len(t)]

with open("censor.out", "w") as f:
    f.write(r+"\n")

2. Cow

C가 나타나면 C의 개수를 하나 올리고, O가 나타나면 지금까지 센 C의 개수만큼 O의 개수를 올리고, W가 나타나면 O의 개수만큼 W를 증가시키면 W의 갯수가 총 COW의 개수이다.

with open("cow.in", "r") as f:
    n = int(f.readline().strip())
    s = f.readline().strip()

c = o = w = 0

for i in range(n):
    if s[i] == 'C':
        c += 1
    elif s[i] == 'O':
        o += c
    elif s[i] == 'W':
        w += o

with open("cow.out", "w") as f:
    f.write(str(w)+"\n")

3. Cow Hopscotch

N이 15이하로 매우 작으므로 BFS 이용해서 0, 0에서 도착점까지 도착하는 모든 경로를 세면 된다.

b = []
with open("hopscotch.in", "r") as f:
    r, c = map(int, f.readline().strip().split())
    for _ in range(r):
        b.append(list(f.readline().strip()))

def bfs(y, x):
    if y == r-1 and x == c-1:
        return 1

    ans = 0
    for i in range(y+1, r):
        for j in range(x+1, c):
            if b[i][j] != b[y][x]:
                ans += bfs(i, j)
    return ans

with open("hopscotch.out", "w") as f:
    f.write(str(bfs(0, 0))+'\n')

USACO 2015 January (Bronze)

02 Mar 2020 | Python USACO PS

USACO 2015 January

1. Cow Routing

입력에서 A, B가 순서대로 존재하는지 확인하면서 이동가능한 루트가 존재하면 최소 가격과 비교해서 갱신하면 되는 문제

ans = float('inf')
with open("cowroute.in", "r") as f:
    a, b, n = map(int, f.readline().strip().split())
    for _ in range(n):
        cost, city_num = map(int, f.readline().strip().split())
        cities = list(map(int, f.readline().strip().split()))
        flag = False
        for city in cities:
            if city == a:
                flag = True
            if city == b and flag:
                ans = min(ans, cost)


with open("cowroute.out", "w") as f:
    if ans == float('inf'):
        f.write(str(-1)+'\n')
    else:
        f.write(str(ans)+'\n')

2. Cow Routing II

전 문제와 동일하나 이번에는 두개의 루트를 선택해서 이동 가능. 단순히 A와 B루트를 덧붙여서 1번 문제와 같은 방식으로 돌리면 TLE가 뜨므로 시간을 줄일 방법을 찾아야 함. 루트에 A나 B가 존재하면 A까지의 루트, A 다음의 루트, B 이전의 루트로 루트를 구분 그 이후 A 다음의 루트와 B 이전의 루트의 교집합이 존재하면 A 에서 B로 이동가능하다는 의미이므로 최소값 계산에 이용하면 됨.

ans = float('inf')
routes = []
costs = []
with open("cowroute.in", "r") as f:
    a, b, n = map(int, f.readline().strip().split())
    for _ in range(n):
        cost, city_num = map(int, f.readline().strip().split())
        costs.append(cost)
        routes.append(list(map(int, f.readline().strip().split())))

se = [[set(), set(), set()] for _ in range(n)] # till_a, after_a, till_b,

for i in range(n):
    s = set()
    s2 = set()
    flag = False
    for city in routes[i]:
        s.add(city)
        s2.add(city)
        if city == a:
            se[i][0] = s
            s = set()
            flag = True
        if city == b:
            se[i][2] = s2
            s2 = set()
        if city == b and flag:
            ans = min(ans, costs[i])
    se[i][1] = s

for i in range(n):
    for j in range(n):
        if i == j:
            continue
        if se[i][0] and se[j][2] and (se[i][1] & se[j][2]):
            ans = min(ans, costs[i]+costs[j])

with open("cowroute.out", "w") as f:
    if ans == float('inf'):
        f.write(str(-1)+'\n')
    else:
        f.write(str(ans)+'\n')

3. It’s All About the Base

뭔가 신박한 알고리즘이 있을지 알고 고민하다가 떠오르는게 없어 정답을 봤는데 전혀 그런거 없다. 단순하게 두 숫자를 10진법부터 변환하고 크기가 더 작은 수에 대해 진법을 하나씩 더 올려 계산하며 같은 숫자를 찾으면 된다. python으로 3초 가까운 시간이 걸리는데도 TLE가 뜨지 않는다.

res = []
with open("whatbase.in", "r") as f:
    k = int(f.readline())
    for _ in range(k):
        x, y = f.readline().strip().split()
        X = Y = 10
        while X <= 15000 and Y <= 15000:
            num_x = int(x[0])*X*X + int(x[1])*X + int(x[2])
            num_y = int(y[0])*Y*Y + int(y[1])*Y + int(y[2])
            if num_x < num_y:
                X += 1
            elif num_y < num_x:
                Y += 1
            else:
                res.append([X, Y])
                break


with open("whatbase.out", "w") as f:
    for r in res:
        f.write(str(r[0])+" "+str(r[1])+"\n")

4. Meeting Time

N이 1~16개 이고 단방향으로 가므로 Bessie와 Elsie에 대해 목적지까지 가는 패스를 전부 계산해서 cost를 저장한 후, 두 패스 중 겹치는 최소값을 찾으면 된다. BFS를 이용해서 경우의 수를 찾고, 해당 값을 set에 저장한 후 교집합의 최소값을 출력하는 방식으로 해결했다.

from _collections import deque
b_cost = set()
e_cost = set()
path = dict()
with open("meeting.in", "r") as f:
    n, m = map(int, f.readline().strip().split())
    for i in range(n):
        path[i] = []
    for _ in range(m):
        a, b, c, d = (map(int, f.readline().strip().split()))
        path[a].append([b, c, d])

q = deque([[1, 0]])

while q:
    cur, cost = q.popleft()
    if cur == n:
        b_cost.add(cost)
    else:
        for p in path[cur]:
            q.append([p[0], cost+p[1]])

q = deque([[1, 0]])
while q:
    cur, cost = q.popleft()
    if cur == n:
        e_cost.add(cost)
    else:
        for p in path[cur]:
            q.append([p[0], cost+p[2]])

with open("meeting.out", "w") as f:
    if b_cost & e_cost:
        f.write(str(min(b_cost & e_cost))+"\n")
    else:
        f.write("IMPOSSIBLE\n")

USACO 2014 december (Bronze)

25 Feb 2020 | Python USACO PS

USACO 2014 December

1. Marathon

전체 좌표들의 총 맨하탄 거리를 계산한 후 순서대로 한 점씩 뺀 상태로 계산해서 최소값을 찾으면 된다. 즉 A, B, C 가 있을 경우 B를 뺀다고 가정하면 A-B 거리와 B-C 거리를 빼고 A-C 거리를 더하는 방식으로 O(n)으로 훑으면 된다.

pos = []

with open("marathon.in", "r") as f:
    n = int(f.readline())
    for _ in range(n):
        pos.append(list(map(int, f.readline().strip().split())))

res = []
for i in range(1, n):
    res.append(abs(pos[i-1][0]-pos[i][0]) + abs(pos[i-1][1]-pos[i][1]))
ans = tot = sum(res)

for i in range(1, n-1):
    ans = min(ans, tot - res[i-1] - res[i] + abs(pos[i-1][0]-pos[i+1][0]) + abs(pos[i-1][1]-pos[i+1][1]))

with open("marathon.out", "w") as f:
    f.write(str(ans)+"\n")

2. Crosswords

2차원 리스트를 순서대로 돌면서 조건에 맞으면 정답에 추가하는 단순 구현 문제

b = []
with open("crosswords.in", "r") as f:
    n, m = map(int, f.readline().strip().split())
    for _ in range(n):
        b.append(list(f.readline().strip()))

ans = 0
res = []
for i in range(n):
    for j in range(m):
        if b[i][j] == '#':
            continue
        hori = vert = True
        if i-1 < 0 or (i > 0 and b[i-1][j] == '#'):
            for k in range(3):
                if i+k >= n or b[i+k][j] != '.':
                    vert = False
        else:
            vert = False

        if j-1 < 0 or (j > 0 and b[i][j-1] == '#'):
            for k in range(3):
                if j+k >= m or b[i][j+k] != '.':
                    hori = False
        else:
            hori = False

        if hori or vert:
            ans += 1
            res.append([i+1, j+1])

with open("crosswords.out", "w") as f:
    f.write(str(ans)+"\n")
    for r in res:
        f.write(str(r[0])+' '+str(r[1])+'\n')

3. Cow Jog

따라잡히는 속도는 최소값에 의해 좌우되므로 입력을 거꾸로 거슬러 올라가며 최소 속도가 갱신될 때 그룹을 하나씩 추가하면 된다.

a = []
with open("cowjog.in", "r") as f:
    n = int(f.readline())
    for _ in range(n):
        a.append(list(map(int, f.readline().strip().split())))

min_s = 1000000001
ans = 0
for i in range(n-1, -1, -1):
    if a[i][1] <= min_s:
        ans += 1
        min_s = a[i][1]

with open("cowjog.out", "w") as f:
    f.write(str(ans)+'\n')

4. Learning by Example

입력된 소의 무게를 정렬하고, 각각의 무게별 구간을 나눈 후 앞의 소가 점이 있으면 앞 절반의 갯수를 ans에 추가하고, 뒤쪽의 소가 spot이 있으면 뒤쪽 절반의 갯수를 ans에 추가한다. 이때 구간은 [S+1, E]의 형태로 잡아서 같은 점이 두번 잡히지 않게 하며, 중앙을 나눌때는 왼쪽 소에 점이 있으면 [S+1, M]까지 추가하고, 오른쪽 소에 점이있으면 [M+1, E]을 추가한다. 이때 오른쪽 소에만 점이 있고, M이 정중앙에 있으면 M의 값이 추가되지 않을 수 있으므로 예외를 처리해줘야 한다.

c = []
with open("learning.in", "r") as f:
    n, a, b = map(int, f.readline().strip().split())
    for _ in range(n):
        s, w = f.readline().strip().split()
        w = int(w)
        s = 1 if s == 'S' else 0
        c.append([w, s])

ans = 0
c.append([-float("inf"), 0])
c.append([float("inf"), 0])
c.sort()

for i in range(n+1):
    s = c[i][0]
    e = c[i+1][0]
    m = (s+e)//2

    if c[i][1]:
        c_s = max(a, s+1)
        c_e = min(b, m)
        if c_e >= c_s:
            ans += c_e-c_s+1
    if c[i+1][1]:
        c_s = max(a, m+1)
        c_e = min(b, e)
        if c_e >= c_s:
            ans += c_e-c_s+1
    if c[i+1][1] and c[i][1] == 0 and s % 2 == e % 2 and a <= m <= b:
        ans += 1


with open("learning.out", "w") as f:
    f.write(str(ans)+'\n')

2019-10-24 코드포스 라운드

24 Oct 2019 | Python Codeforces PS

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*105으로 증가했다. 위의 방법대로 풀면 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(N3)로 풀어도 된다.

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++은 필수인듯

Google Code Jam 2019

09 Apr 2019 | Python Algorithm CodeJam Google

Code Jam 2019

작년과 마찬가지로 올해도 Code Jam 예선을 참 했다. 예선은 하루종일 진행되어 시간날때 틈틈히 풀면 되서 딱히 부담스럽지 않았다.

예선 문제 리뷰

올해도 파이썬을 이용해 Code Jam에 참여했다.

문제1. Foregone Solution (17점)

4가 들어간 입력을 적절히 분리하여 출력하는 문제였다. 아래와 같이 4를 1과 3이든 2와 2로 분리하든 N = A+B 형태로만 출력하면 되는 문제였다.

4     Case #1: 2 2
940   Case #2: 852 88
4444  Case #3: 667 3777

1 ≤ T ≤ 100.
Time limit: 10 seconds per test set.
Memory limit: 1GB.
At least one of the digits of N is a 4.

Test set 1 (Visible)
1 < N < 10^5.

Test set 2 (Visible)
1 < N < 10^9.

Test set 3 (Hidden)
1 < N < 10^100.

단순히 첫 문자부터 4를 찾을때마다 2와 2로 나누어주는 식으로 구현했고, AC판정을 받았다.

문제2. You Can Go Your Own Way (24점)

미로찾기 문제였는데, 처음 간 사람의 경로를 따라가지 않아야 하는 조건이 붙어있었다. 제일 먼저 떠오른 생각은 그래프로 미로를 표현한 후 BFS로 경로를 탐색하는 것이었는데, 마지막 테스트 셋의 크기가 부담스러웠다. 메모리 제한 및 시간제한에 분명히 걸릴 것 같아서, (안그래도 파이썬으로 풀고있는데..) 다른 방법을 생각해 보았다.

Test set 1 (Visible)
2 ≤ N ≤ 10.

Test set 2 (Visible)
2 ≤ N ≤ 1000.

Test set 3 (Hidden)
For at most 10 cases, 2 ≤ N ≤ 50000.
For all other cases, 2 ≤ N ≤ 10000.

1 ≤ T ≤ 100.
Time limit: 15 seconds per test set.
Memory limit: 1GB.

어떠한 경로든지 겹치지만 않으면 된다고 해서 단순히 처음 간 사람의 경로를 대칭으로 이동하는 방법으로 구현, AC 판정을 받았다.

문제3. Cryptopangrams (25점)

알파벳 암호화와 관련된 문제였다. N까지의 소수중 알파벳 갯수만큼 소수를 선택해 작은 순부터 ABCD에 매핑하고, 이후 그 두 수의 곱을 입력으로 주면 그 입력에서 원래의 문자열을 추출하는 문제였다. 문자열에는 ABC..Z가 최소 한번은 포함되어 있다.

A B C D가 3 5 7 11이라 하면, CAD라는 문자열은 73 311해서 21 33이 주어지는 식이다

 1 ≤ T ≤ 100.
 Time limit: 20 seconds per test set.
 Memory limit: 1 GB.
 25 ≤ L ≤ 100.
 The plaintext contains each English alphabet letter at least once.
 
 Test set 1 (Visible)
 101 ≤ N ≤ 10000.
 
 Test set 2 (Hidden)
 101 ≤ N ≤ 10^100.

제일 먼저 든 생각은 암호화 된 숫자들에서 제일 작은 숫자를 골라서 소인수 분해를 해보자는 생각. 문제는 큰 수에 대한 소인수 분해가 힘들다는것.. 테스트 셋 2를 통과할 가망이 없었다 그다음으로 생각한 것은 숫자들이 AB, BC, C*D와 같은 형태로 이루어져 있고 나머지 두 수는 소수이니, 두 수의 공약수를 찾으면 되겠다는 생각. 공약수야 아무리 큰 수라도 유클리드 호제법을 사용하면 빠르게 찾을 수 있으니, 이걸로 풀면 되겠다는 생각이 들었다. 그래서 처음에는 두 수의 공약수를 찾아가면서 마지막까지 찾아내고, 처음과 끝에 나머지 글자들을 붙여주게 구현을 했는데 실패. 다시 생각해보니 최초 하나의 공약수만 찾아낸 후 그걸로 나머지 숫자들을 계속 나누어주면 더 쉽게 풀리는 문제였다.

다시 구현해서 제출하니 또 실패. 정답이라고 생각한 아이디어였는데 계속해서 오답처리가 나니 짜증나서 암호화 문장을 제작하는 프로그램을 작성. TC를 몇개 돌려보니 ABABA와 같은 반복적인 문자열이 나올때, 같은 숫자가 연속되고 최대 공약수가 그냥 그 숫자 자체가 되어버리는 경우가 있다는 것을 발견했다. 이럴 경우 A~Z가 한번은 나오게 되어있다는 가정을 이용하면, 다른 숫자가 나오는 경우가 반드시 있으므로 이때 최대공약수를 구해서 반대로 값을 메꾸어 나가면 된다. 이를 이용한 코드를 제출하여 AC 판정을 받았다.

문제4. Dat Bae (34점)

N개의 컴퓨터 중 고장난 B 대의 컴퓨터를 찾아내는 문제, F번 만큼 쿼리를 날려 응답을 받을수 있다. TEST_STORE 01101 returns 111. TEST_STORE 00110 returns 010. TEST_STORE 01010 returns 100. TEST_STORE 11010 also returns 100. 0번째 3번째 컴퓨터가 고장났다고 가정했을때의 응답은 위와 같다.

4번은 인터렉션 문제이며 채점 서버에 출력을 날린 후 다시 입력을 받아 그걸 가지고 정답을 찾아내야 한다.

Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
2 ≤ N ≤ 1024.
1 ≤ B ≤ min(15, N-1).

Test set 1 (Visible)
F = 10.
Test set 2 (Hidden)
F = 5.

작년에 새로 등장한 인터렉션 문제는 뭔가 로컬에서 테스트 하는 방법부터가 번거로운 느낌이라 영 적응이 되지 않는다. 사실 문제 4번까지 올 시점이 되면 이미 예선은 통과한 시점이라 파이팅이 좀 떨어지기도 한다. (어렵기도 하고…) 하지만 이번 문제들이 접근만 올바르면 몇 줄 안되는 코드로 풀려버리는 문제들이 많아 흥미로웠고, 마지막까지 도전해보기로 했다.

처음 봤을때 든 생각은 비트마스크를 이용하는 문제인가라는 생각. 1,2,3번과 마찬가지로 각각의 테스트 셋을 관통하는 풀이를 찾고 싶었는데 쉽게 접근 방법이 떠오르지 않았다. 일단 N의 크기가 2^1에서 2^10라는 점에서 테스트 셋 1의 F=10이 관련이 있겠구나 싶었는데, 그럼 5번안에는 어떻게 고장난 컴퓨터들을 분별해야 할지 잘 떠오르지 않았다. 고장난 컴퓨터의 수가 min(2^4-1, N-1)이라는 점을 이용할 수 있을 것 같았는데… 결국 해당 문제는 풀지 못했다.

나중에 풀이 접근을 보니 01010… 00110… 00001… 00000… 00000… 00000… 00000… 00000… 00000… 00000… 와 같이 각 10줄의 쿼리에 2진수 0부터 N-1 까지 날려보내면 출력에서 사라진 숫자를 통해 고장난 컴퓨터의 번호를 알수 있다.

문제는 F=5인 경우인데, 5bit으로 표현할 수 있는 크기가 2^5 = 32 뿐이다. 이때 중요한 점은 고장난 컴퓨터의 수가 min(2^4-1, N-1)이므로 고장난 최대 컴퓨터의 수는 15를 넘지 못한다. 이는 5비트 안에 충분히 포함할 수 있는 수이고, 이점을 이용해 01010…010101…10101 00110…001100…10011 00001…000011…01111 00000…000000…11111 00000…111111…11111 0, 1, 2, 3, 4… 16, 17, 18, 19, 20, 21… 27, 28, 29, 30, 31
을 반복해서 날리면, 한 구간이 통제로 소멸될 일이 없으므로 고장난 번호를 알아낼 수 있다.

마치며

알고리즘을 손에서 놓지 않기 위해 매년 참가 신청을 했고, 예선 통과라는 소기의 목표도 이미 달성했지만, 1라운드도 참가해야겠다. 부족한 점은 많고 알고리즘은 항상 어렵지만, 아이디어를 통해 문제를 명쾌하게 풀어낼 때의 쾌감이 있다.