2024. 4. 29. 16:58ㆍCompetitive Programming/AtCoder
지난 번 AtCoder Regular Contest 176에서 옐로우에 가까운 퍼포먼스를 보여주면서 그린 후반으로 점프하더니, 이번에는 말 그대로 인생 라운드를 찍어 버렸다. 실력이 더 높아지기 전까지는 이것보다 높은 성과를 내기는 힘들지 않을까... 하는 느낌.
그리고 여기에 지능을 전부 다 할애해버린 나머지 바로 다음에 있던 Codeforces Round 941에서는 그린 퍼포먼스를 내며 민트 문턱까지 두드리고 왔다. 인생 최고의 라운드와 최악의 라운드를 연달아 치니 끝난 지 만 이틀이 다 되어가는 지금도 기운이 없다.
결과는 한국 10등, 세계 317등으로 AtCoder 민트에 안착했다. AtCoder 민트는 Codeforces 블루와 거의 같은 위치라는데, 이제 AtCoder 레이팅도 올라 올 만큼 올라온 것 같다. 지금부터는 아마 길고 긴 진동이 시작되겠지... 여기서 마음이 꺾이는지 꺾이지 않는지가 앞으로를 가를 것 같다.
반성할 점
이런 라운드라지만 반성할 것이 없지는 않았다. 언어 설정을 잘 보지 않고 제출해서 B, C에 두 번이나 컴파일 에러를 낸 점. 페널티에 큰 영향은 없었지만 그래도 다시 제출하는 과정에서 시간을 허비했던 것을 생각하면, 생각보다 아프지는 않았지만 그래도 조금 아픈 결과가 아닐 수 없다.
그리고 D에서 BFS를 시행할 때 시작한 점을 방문 칸에 넣지 않는 실수를 저질러서 5분짜리 페널티와 디버깅하는 데 든 시간 6분을 낭비해 버리고 말았다. 이건 한 번에 맞았으면 퍼포먼스 120점 정도는 높게 받을 수 있었다는 점에서 정말로 뼈아픈 실수가 아닐 수 없다.
0:00 A AC
print(1+sum(map(int,input().split()))-sum(map(int,input().split())))지금 지거나 비기고 있는 상황에서 끝내기 승리를 거두려면 몇 점을 더 내야 하냐는 문제다. 당연히 상대 팀보다 1점만 더 내면 이기니까, 그 점만 구현 잘 해 주면 된다.
지금 이기고 있는 상황이었으면 생각할 만한 게 한 가지가 더 많아졌겠지만, A번이기 때문에 그냥 믿음으로 제출했다. 앳코더 A번은 1분 이내에 뚫을 수 있을 정도로 구현량이 적고 간단한 문제들이 나왔기 때문에...
0:04 B AC
N = int(input())
A = [input() for _ in range(N)]
B = [input() for _ in range(N)]
for i in range(N):
for j in range(N):
if A[i][j] != B[i][j]: print(1+i,1+j); exit(0)틀린그림찾기 문제이다. 그냥 모든 칸을 전부 순회해 주면서 틀린 칸의 번호만 출력하면 되는 간단한 문제다.
0:04 C AC
N,*li = map(int,open(0).read().split()); stack = [li[0]]
for i in range(1,N):
stack.append(li[i])
try:
while stack[-1] == stack[-2]:
stack.pop(); stack[-1] += 1
except: pass
print(len(stack))스택을 이용해서 직접 하나씩 공을 넣어주고, 만약 인접한 두 공의 크기가 같다면 두 공을 합쳐주는 작업을 매번 공을 넣을 때마다 수행해 줘도 넉넉한 시간 안에 돌아간다.
맨 처음에는 인접한 두 공 자체가 없기 때문에 맨 처음에는 첫 번째 공을 넣어주고 시작하는 것을 잊지 말자.
0:16 E AC
from sys import stdin
input = stdin.readline
N = int(input()); data = [[],[]]
for _ in range(N):
a,b = map(int,input().split())
trig = (a+b)%2
if trig == 1: b -= 1
data[trig].append(((a+b)//2,(a-b)//2))
def sumPairs(arr):
arr.sort()
s = 0; n = len(arr)
for i in range(n-1,-1,-1):
s += i*arr[i]-(n-1-i)*arr[i]
return s
ans = sum(sumPairs(list(item[i//2] for item in data[i%2])) for i in range(4))
print(ans)D랑 E의 점수 차가 별로 나지 않고 D가 처음 보기에는 이상한 그래프 탐색 문제처럼 느껴져서 버렸다. 먼저 E부터 차분히 생각해 보았다.
토끼는 비숍처럼 움직인다. 그 말은 처음 칸과 색깔이 다른 칸은 절대로 밟을 수 없다는 것이다. 색깔을 \(x+y\pmod 2\)로 정의하고, 색깔이 같은 칸끼리 저장해 줘도 상관 없다.
그렇게 둔다 할지라도 모든 거리의 합을 구하는 것은 아직 너무 어렵다. 조금 더 생각을 해 보자. 대각선 움직임이 \(x, y\)좌표를 동시에 변경시키기 때문에 최소 점프 횟수를 구하기 힘들다면, 대각선이 아니도록 좌표축을 재정의해주면 된다. 좌표평면 자체를 45도 회전시키는 방법으로 가능하고, 이 경우 \((x,y)\)는 새로운 좌표평면에서 \((\frac{x+y}2,\frac{x-y}2)\)로 재정의된다.
그렇게 되면 맨해튼 거리의 합으로 나타낼 수 있고, \(x\)좌표와 \(y\)좌표는 서로 독립적이므로 \(\sum_{i<j}|a_i-a_j|\)를 선형 시간 안에 구하는 문제 4개를 동시에 푸는 문제로 환원시킬 수 있다. 이는 순서대로 정렬해버린 뒤에 개 중 \(i\)번째로 작은 원소는 \(j<i\)일 대 더해지고 \(j>i\)일 때 빼진다는 것을 통해서 풀 수 있다.
누가 22878번 문제와 비슷하다고 했던 것 같은데, 조만간 풀 문제가 하나 늘 것 같다는 생각과 이렇게 어려운 문제를 대회 시간 안에 풀 수 있는 실력인 건가? 하는 생각이 동시에 들었다.
0:25 F AC
N,*l = map(int,open(0).read().split())
data = [(i+1,l[i]) for i in range(N)]
data.sort(key=lambda x:-x[1])
ans = 0
tree_num = [0]*(N+1)
tree_sum = [0]*(N+1)
def update(i,diff):
i0 = i
while i <= N: tree_sum[i] += diff; i += (i & -i)
while i0 <= N: tree_num[i0] += 1; i0 += (i0 & -i0)
def prefix_sum(i):
ans = 0
while i > 0: ans += tree_sum[i]; i -= (i & -i)
return ans
def prefix_num(i):
ans = 0
while i > 0: ans += tree_num[i]; i -= (i & -i)
return ans
for idx,num in data:
update(idx,num)
temp = prefix_sum(N)-prefix_sum(idx)
temp -= num*(prefix_num(N)-prefix_num(idx))
ans += temp
print(ans)오히려 E보다는 더 관찰이 쉬운 문제였다.
시그마를 적절히 바꿔 주면 \(S(i)=\sum_{j>i}\max(A_j-A_i,0)\)에 대해서 \(\sum_{i=1}^N S(i)\)가 됨을 알 수 있다. 각 \(S(i)\)를 로그 시간 내에 구하면 이 문제를 풀 수 있다.
이 \(S(i)\)는 다음과 같은 식으로 나타낼 수 있다.
$$\left(\sum_{i<j, A_i\le A_j}A_j\right)-A_i\left(\sum_{i<j, A_i\le A_j}1\right)$$
수와 갯수를 관리해 줄 펜윅 트리 두 개를 만든다. 그리고 큰 수부터 업데이트해 주면 각각 펜윅 트리의 부분합을 통해서 두 개의 \(\Sigma\)를 로그 시간 내에 구할 수 있고, 이를 매번 업데이트해 가면서 반복하면 제한 시간 내에 풀 수 있다.
0:51 D AC (+1)
from collections import deque
H,W = map(int,input().split())
dx,dy = [1,-1,0,0],[0,0,1,-1]
box = [input() for _ in range(H)]
board = [[1]*W for _ in range(H)]
ans = 1
def inbox(x,y):
if x<0 or x>=H: return False
if y<0 or y>=W: return False
return True
def adj(x,y):
for d in range(4):
nx,ny = x+dx[d],y+dy[d]
if inbox(nx,ny):
if box[nx][ny] == '#': return True
return False
def bfs(x,y):
Q = deque(); Q.append((x,y)); vst = set(Q)
while Q:
x,y = Q.popleft()
for d in range(4):
nx,ny = x+dx[d],y+dy[d]
if inbox(nx,ny) and (nx,ny) not in vst:
if board[nx][ny] > -2: vst.add((nx,ny))
if board[nx][ny] > 0: board[nx][ny] -= 1; Q.append((nx,ny))
return len(vst)
for i in range(H):
for j in range(W):
if box[i][j] == '#': board[i][j] = -2
elif adj(i,j): board[i][j] = -1
for i in range(H):
for j in range(W):
if board[i][j] > 0:
ans = max(ans,bfs(i,j))
print(ans)자석과 자석에 인접한 칸은 미리 처리해 주고, 자석에 인접하지 않은 칸들을 중심으로 BFS 돌려 주면 된다.
자석에 인접한 칸은 방문한 칸의 수만 1 키워 주고 큐에는 삽입하지 않음으로서 자석에 붙잡힌 듯한 효과를 낼 수 있다. 바로 이런 이유 때문에 BFS의 시작점은 자석에 인접하지 않은 칸밖에 될 수가 없다.
방문 처리를 제대로 해 준다면 대부분의 칸을 한 번만 방문하는 식으로 시간 초과를 회피할 수 있다.
난 맨 처음에 방문한 정점에 자기 자신을 포함하지 않음으로서 한 번 틀렸다. 이렇게 어이없이 페널티를 집어먹을 줄이야......