AtCoder Beginner Contest 250 후기

A. Adjacent Squares

 간단한 문제다. 어떤 H * W 사각형(사실상 2차원 배열)이 주어질 때, 특정 좌표 (R, C)와 동서남북으로 인접한 사각형의 갯수를 구하는 문제이다

import sys

h,w = map(int, sys.stdin.readline().split())
r,c = map(int, sys.stdin.readline().split())

# 전체 사각형 전처리
arr = [[-1] * w for _ in range(h)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
ans = 0
for i in range(h):
    for j in range(w):
        # 현재 좌표가 (R, C)이면 
        if i == r - 1 and j == c - 1:
            # 4방향 체크
            for k in range(4):
                x, y = i + dx[k], j + dy[k]
                if 0 <= x < h and 0 <= y < w:
                    ans += 1
print(ans)

B. Enlarged Checker Board

 말보다 그림으로 설명하는 편이 빠르다

<그림 1. 문제의 조건을 시각화>

 따라서 N,A,B가 주어졌을 때 그림 1과 같이 출력하면 된다

import sys

# 입력부
n, a, b = map(int, sys.stdin.readline().split())
# arr : 전체 사각형 (N * A, N * B)
# 백색 부분으로 전처리
arr = [['.'] * (n * b) for _ in range(n * a)]

# 전체 사각형을 a행씩 건너뛰면서 순회한다
for i in range(0, n * a, a):
    # 현재 흰색 부분이 먼저 칠해지는 경우
    if (i // a) % 2 == 0:
        # 흰색 부분이 먼저니까 검은색 부분의 시작은 b이다
        for j in range(b, n * b, 2 * b):
            for k in range(a):
                for q in range(b):
                    arr[i + k][j + q] = '#'
    # 현재 검은색 부분이 먼저 칠해지는 경우
    else:
    	# 검은색 부분이 먼저니까 검은색 부분의 시작은 0이다
        for j in range(0, n * b, 2 * b):
            for k in range(a):
                for q in range(b):
                    arr[i + k][j + q] = '#'
for i in arr:
    print(''.join(i))

C. Adjacent Swaps

 단순히 문제의 규칙대로 구현하면 TLE를 피할 수 없는 문제이다. 배열을 2개 만들면 시간 안에 정답을 구할 수 있다. 첫번째 배열은 "특정 수 X가 지금 어떤 인덱스 i에 있는지"를 저장하는 배열이고, 두번째 배열은 "특정 인덱스 i에 지금 어떤 수 X가 있는지"를 저장하는 배열이다. 따라서, 쿼리가 들어올 때마다 적절히 swap해주면 정답을 구할 수 있다. 단, 현지 위치의 오른쪽이 배열이 끝인 경우 왼쪽과 교환이 이루어지는 점만 주의하면 된다

import sys

# 입력부
n, q = map(int, sys.stdin.readline().split())

# num_to_pos : "특정 수 X가 지금 어떤 인덱스 i에 있는지"를 저장하는 배열
num_to_pos = [i for i in range(n + 1)]
# pos_to_num : "특정 인덱스 i에 지금 어떤 수 X가 있는지"를 저장하는 배열
pos_to_num = [i for i in range(n + 1)]

for _ in range(q):
    x = int(sys.stdin.readline())
    pos = num_to_pos[x]
    # swap할 부분이 가장 오른쪽인지에 따라 바꿀 위치 결정
    if pos + 1 > n:
        next_pos = pos - 1
    else:
        next_pos = pos + 1
    next_num = pos_to_num[next_pos]
    # 현재 수, 위치를 다음 수, 다음 위치로 바꾼다
    num_to_pos[x] = next_pos
    pos_to_num[pos] = next_num
    num_to_pos[next_num] = pos
    pos_to_num[next_pos] = x

print(' '.join(map(str, pos_to_num[1:])))

D. 250-like Number

 단순한 수학 문제이다. 우선 소수인 $p,q$가 있고, 항상 $p < q$일 때 $\frac{k} {q ^ 3} = p$를 만족하는 N보다 작은 k의 갯수를 구하면 된다. q에 집중하면 문제가 쉬워진다. 만일 $q^3$이 N을 넘어가면 의미가 있을까? 없다. 왜냐하면 0이하의 소수는 없기 때문이다. 따라서, q의 범위는 최대 $\sqrt[3]{N} \leq 10 ^ 6$이다. 따라서, 실제 q의 후보군들의 갯수는 정확히 백만개보다도 작다. 

 따라서, 백만 이하의 소수를 미리 전처리한다. 추가로 전처리할 때 "현재 수가 X일 때 소수의 갯수"를 저장하는 배열도 전처리한다. 이후에 각 수를 순회하면서 p의 최대값을 계산한다. 그런데, 항상 $p < q$이기 때문에 p의 최대값이 q보다 크면, $q - 1$까지의 소수의 갯수를 더하고 그렇지 않으면 $p$까지의 소수의 갯수를 더하면 시간안에 정답을 구할 수 있다

import sys, bisect

# eratos : num이하의 소수 리스트를 리턴하는 함수
def eratos(num):
    res = []
    check = [False] * (num + 1)
    # now : 현재까지의 소수의 갯수
    now = 0
    for i in range(2, num + 1):
        if check[i] == False:
            now += 1
            for j in range(2 * i, num + 1, i):
                check[j] = True
        # 현재까지의 소수의 갯수를 저장
        cnt[i] = now
    for i in range(2, num + 1):
        if check[i] == False:
            res.append(i)
    return res

# 입력부
n = int(sys.stdin.readline())
# cnt : "현재 수가 X일 때 소수의 갯수"를 저장하는 배열
cnt = [0] * 1000001
temp = eratos(1000000)
ans = 0
size = len(temp)
for i in range(size):
	# bound : p의 상한
    bound = n // pow(temp[i], 3)
    # p의 상한이 q보다 작으니까, p의 상한까지의 소수는 모두 가능
    if bound < temp[i]:
        ans += cnt[bound]
    # p의 상한이 q보다 크거나 같으니까, q-1까지의 소수는 모두 가능
    else:
        ans += cnt[temp[i] - 1]
print(ans)

후기 : "뭔 소리지?"만 겁나 하다가 끝난 대회... 특히 B번의 설명을 이해하지 못해서 당황한 나머지 쉬운 C번의 설명도 꼬아서 생각해서 시간을 두배로 날린듯하다. B가 이해되지 못하고 바로 C로 넘어간건 좋았으나 C문제를 볼 때 더 차분하게 봤으면 어땠을까 싶다. D의 경우도 정해는 약 15분 정도 생각하고 바로 떠올렸으나, 갯수를 구하는 과정에서 바보같이 배열에서 바로 찍는게 아니라 이진 탐색으로 갯수를 구해버려서 페널티를 2번이나 먹었다. CP에서 만약이란건 없지만, 생각한 풀이 그대로 했다면 거의 1000등 중반에 안착할 수 있었을 텐데 아쉽다. 그래도 나머지 A~C까지는 깔끔하게 풀었으니, 사실 당연한 거지만, 최악은 면했다. 다음 대회에는 애초에 E를 풀 생각일랑 하지 않고 A~D까지만 빠르고 정확하게 풀도록 목표를 바꿔야 겠다!