Atcoder Beginner Contest 269 후기

A. Anyway Takahashi

 매우 간단한 사칙연산을 한 이후 Takahashi를 출력하면 되는 매우 간단한 문제이다

import sys

a, b, c, d = map(int, sys.stdin.readline().split())
print((a + b) * (c - d))
print('Takahashi')

B. Rectangle Detection

 입력으로 N x M 사각형이 들어오고, A x B의 사각형이 내부에 있을 때, A와 B를 구하는 문제이다

<그림 1. 입력 예시>

 위 그림 1에서 N=M=5이고, A=B=2이다. N x M이 최대 10 x 10이기 때문에, 단순한 반복문으로 쉽게 해결할 수 있다

import sys

arr = [list(sys.stdin.readline().rstrip()) for _ in range(10)]
a, b = [], []
for i in range(10):
    if '#' in arr[i]:
        a.append(i)
for i in a:
    for j in range(10):
        if arr[i][j] == '#':
            b.append(j)
print(min(a) + 1, max(a) + 1)
print(min(b) + 1, max(b) + 1)

C. Submask

 특정 수 x가 입력으로 주어질 때, x를 이진수로 표기하였을 때 켜진 비트의 자릿수가 같은 수들을 오름차순으로 출력하는 문제이다. 그런데 입력값이 $2^{60}$이기 때문에 가능한 모든 수를 for문으로 순회해서는 정답을 절대로 시간안에 도출할 수 없다. 하지만 x를 이진수를 표기하였을 때의 길이는 최대 60이기 때문에, 백트래킹으로 문제를 해결할 수 있다

<그림 2. idx = 0일 때>

 위 그림 2는 백트래킹의 초기상태를 나타낸 그림이다. 백트래킹의 상태 공간은 현재 수가 num이고, 현재 위치가 x의 이진수 표기 기준으로 idx번째인 상황이라고 정의하자.

<그림 3. idx = 1일 때>

 위 그림 3은 그림 2에서 idx가 한번 움직인 이후를 나타낸 그림이다. idx=0일 때, x의 비트는 켜져있으므로(x의 가장 왼쪽 비트) num에도 비트를 켜줄 수 있지만 반대로 아무런 동작을 하지 않을 수 있다. 따라서 새로 생긴 $1000_{(2)}$를 정답에 추가한다.

<그림 4. idx = 2일 때>

 위 그림 4는 그림 3에서 idx가 한번 움직인 이후를 나타낸 그림이다. idx가 1일 때 x의 비트는 꺼져있으므로(x의 왼쪽으로부터 2번째 비트) num에 비트를 켜줄 수 없다. 왜냐하면 조건을 위반하기 때문이다. 따라서 정답에 추가된 숫자는 없다. 그런데 $0000_{(2)}$이 계속 되니까 정답에 이미 숫자가 있으면 pruning을 하는게 좋지 않을까?

<그림 5. idx = 3일 때>

 그렇지 않다. 만약 $0000_{(2)}$를 pruning을 했더라면 위 그림 5에서 $0010_{(2)}$를 얻을 수 없기 때문이다. 따라서 백트래킹을 통해 정답을 구할 수 있다

import sys

# go : 현재 수가 now이고 idx번째 비트인 경우 정답을 저장하는 함수
def go(now, idx):
    # 현재 수 저장
    ans.add(int(''.join(now), base=2))
    # Base Case : x의 길이만큼 이동한 경우
    if idx == m:
        return
    # Recursive Case : 비트가 켜진 경우, 현재 수에도 비트를 킴
    if arr[idx] == '1':
        now[idx] = '1'
        go(now, idx + 1)
        now[idx] = '0'
        
    # Recursive Case : 비트의 켜짐 유무와 관계 없이 현재 수에 비트를 끔
    go(now, idx + 1)

# 입력부
n = int(sys.stdin.readline())
arr = list(bin(n).replace('0b', ''))
m = len(arr)

# temp : 가능한 수의 이진수 표기를 나타내기 위한 배열
temp = ['0'] * m
ans = set()
go(temp, 0)

# 정답 출력
ans = sorted(ans)
for i in ans:
    print(i)

D. Do use hexagon grid

 일반적인 사각형 격자가 아닌, 육각형 격자가 주어질 때, 주어진 좌표들을 통해 연결 요소의 갯수를 구하는 문제이다. 기본적인 bfs로 해결할 수 있으며, 주의해야 할 점은 vis배열을 일반적인 2차원 배열이 아닌 dictionary로 해야 구현이 편리하다.

import sys, collections

# 입력부
n = int(sys.stdin.readline())
dx = [-1, -1, 0, 0, 1, 1]
dy = [-1, 0, -1, 1, 0, 1]

# arr : 특정 좌표를 key, 좌표의 연결 요소번호를 value로 하는 dictionary
arr = dict()
vis = set()
for _ in range(n):
    a, b = map(int, sys.stdin.readline().split())
    arr[(a, b)] = -1
q = collections.deque()
cnt = 0
for i in arr:
    # 방문하지 않은 좌표인 경우 새로운 연결 요소
    if i not in vis:
        cnt += 1
        q.append(i)
        vis.add(i)
        arr[i] = cnt
        # bfs
        while q:
            x, y = q.popleft()
            for j in range(6):
                nx, ny = x + dx[j], y + dy[j]
                if (nx, ny) in arr and (nx, ny) not in vis:
                    arr[(nx, ny)] = arr[(x, y)]
                    vis.add((nx, ny))
                    q.append((nx, ny))
# 정답 출력
print(max(arr.values()))

 

E. Last Rook

 N x N의 체스판이 주어지고, n-1개의 룩이 서로가 공격할 수 없도록 배치되어 있을 때 마지막 룩을 놓을 좌표를 찾는 문제이다. 단, 채점 시스템에 질의할 수 있는 횟수가 최대 20번으로 제한된다. N의 최대값은 1000이다

 브루트 포스로 좌표를 계산하게 되면 $O(N^2)$이 걸리게 된다. n이 크지 않기 때문에 일반적인 상황이라면 상관이 없으나, 우리는 $O(20)$으로 문제를 해결해야 하기 때문에 브루트 포스로는 조건을 만족하면서 문제를 해결할 수 없다. 그런데, row와 column을 고정시키면서 이분 탐색을 진행한다면, $\log 10^3 \approx 10%$이고, row를 구한 후 column을 구하면 되기 때문에 최종 연산 횟수는 $2\log 10^3 \leq 20%$을 만족한다.

<그림 5. n = 5인 경우>

 위 그림 5에서 X는 이미 존재하는 룩의 좌표이고, O는 아직 놓지 않은 룩의 위치인 경우를 나타낸 그림이다. 우선 column을 고정한 채 row를 계산해보자. (3, 0) ~ (4, 4)의 영역에서 룩의 갯수는 2개이다. 그림에서 파란색 영역을 또 다른 사각형이라고 생각해보면, 2 X 5 크기의 직사각형이고, 가능한 룩의 갯수는 min(2, 5)=2개이므로, 현재 파란색 영역에는 마지막 룩을 놓을 위치가 없다.

 따라서, (4, 0) ~ (4, 4) 역시 마지막 룩을 놓을 위치가 없다. 결국 어떤 영역에 대하여 룩을 놓을 수 없다면 그 영역보다 더 작은 영역은 굳이 확인하지 않아도 된다

<그림 6. n = 5인 경우>

 위 그림 6에서 파란색 영역에서 가능한 룩의 갯수는 4개이지만, 실제로는 3개이다. 따라서, (1, 0) ~ (4, 4) 영역 중 어떤 하나의 row가 마지막 룩이 있을 곳이 될 가능성이 있다. 따라서, 현재 파란색 영역보다 더 큰 영역, 예를 들어 (0, 0) ~ (4, 4)의 영역을 탐색할 필요는 없다. 왜냐하면 그 때 역시 하나의 룩이 빠져있기 때문이다. 결국, i번째 row부터 n번째 row까지 이분탐색을 하면서 마지막에 얻는 i번째 row가 결국 마지막 룩이 위치할 row가 된다. 같은 논리에 의해 column도 쉽게 구할 수 있으므로 최대 20번의 연산내에 마지막 룩의 위치를 파악할 수 있다

import sys

# row_check : 첫번째 row부터 num번째 row까지 룩이 빠짐 없이 있는지 체크하는 함수
def row_check(num):
    print('?', 1, num, 1, n)
    sys.stdout.flush()
    t = int(sys.stdin.readline())
    return t == num

# col_check : 첫번째 col부터 num번째 col까지 룩이 빠짐 없이 있는지 체크하는 함수
def col_check(num):
    print('?', 1, n, 1, num)
    sys.stdout.flush()
    t = int(sys.stdin.readline())
    return t == num

# 입력부
n = int(sys.stdin.readline())
while True:
    # row 기준 이분 탐색
    row_left = 1
    row_right = n
    while row_left < row_right:
        mid = (row_left + row_right) // 2
        if row_check(mid):
            row_left = mid + 1
        else:
            row_right = mid
    
    # column 기준 이분 탐색
    col_left = 1
    col_right = n
    while col_left < col_right:
        mid = (col_left + col_right) // 2
        if col_check(mid):
            col_left = mid + 1
        else:
            col_right = mid
    
    # 정답 출력
    print('!', row_right, col_right)
    sys.stdout.flush()
    break