내가 가진 뱃지들 중, 소유자가 1000명보다 작은 뱃지들을 모아봤다. 올해 얻은 뱃지들이 희귀도가 높은 느낌이다.
사실 이 대회에 참여한 건 상반기 대회에서 지급한 '양말대와 핌파티' 뱃지가 마음에 들어서였는데, 비슷하게 생긴 뱃지가 나올 것이라는 예상은 빗나갔지만 그래도 내가 가지고 있던 뱃지들이랑 다른 느낌이고 받은 사람도 별로 없어서 결과적으론 나쁘지 않다.
뱃지를 받은 사람이 별로 없는 이유는, 높은 난이도 때문이었던 것 같다. 보통 A번은 날먹 문제로 나오는데 이번엔 그렇지 않았다. A번인 만큼 브론즈 난이도의 쉬운 문제였지만 거저 주는 문제는 아니었어서 A번만 풀고 뱃지를 받아가던 사람들이 뱃지를 받지 못했고, 받은 사람 수가 크게 줄어든 것 같다.
물론, 대회가 어렵기도 했다. 상반기 대회에 비해 확실히 어려웠다는 의견이 많았다. (나는 상반기 대회 문제를 안 풀어봐서 모른다.)
좋은 대회였지만, 내 퍼포먼스는 그닥 좋지만은 않았던 것 같다. 아무리 그래도 1솔은 좀....
물론 난이도 기준 두 번째 문제부터 골드이긴 했다.
문제별 후기
A. 더블팰린드롬
내가 푼 유일한 문제. 난이도는 B1이다.
B1치고는 뭔가 태그가 여러 개 붙어있다. (구현 태그도 붙어있는데 이건 납득이 잘 안 간다)
사실 수학 문제로 만들 필요가 없는 문제인데, 순서쌍의 갯수를 구하라고 해서 어쩔 수 없이 수학을 써야 하는 문제로 만든 느낌?
문자열 + 애드혹 자체는 신선했다. 사실 처음 문제를 보고 조금 겁을 먹기도 했는데, 생각보다 훨씬 간단한 문제였다.
시간복잡도가 O(n)인 단순한 문제임에도 84ms라는 시간이 나왔다. 보통 브론즈 문제들은 Lua를 사용해도 0ms로 풀리는 걸 생각하면 이례적이다. 데이터가 빡셌던 것 같다.
그나마 다행인 건, N<=10000 이라서 정답이 아슬아슬하게 32비트 정수형의 범위를 벗어나지 않는다는 것이다.
B. 근성아 일하자
무슨 이유인지는 모르겠지만 이 대회는 전반적으로 데이터가 빡센 느낌이다.
좌표 범위가 10^8 인건 그렇다 쳐도, B번인데 N<=200000이다.
이상한 풀이가 통과하는 걸 방지하기 위해 데이터를 빡세게 하는 건 좋은데, Lua를 쓰는 입장에서는 달갑지만은 않다.
대회 참여를 위해 C++로 알고리즘 문제 푸는 연습을 많이 해야겠다는 생각이 들었다. (C++을 모르는 건 아니다. 실제로 C++로도 종종 문제를 풀지만, 익숙하진 않다)
데이터가 조금 빡세긴 했지만, 뭔가 구현으로 풀릴 것 같았다. (일단 문제 상황 자체는 단순하기 때문이다. 물론 단순한 문제를 풀기 위해 복잡한 로직이 들어가는 경우도 많으나, 이건 그런 경우는 아닌 것 같았다.)
예상대로 시뮬레이션 문제가 맞긴 했지만, 트리를 사용한 집합과 맵, 이분 탐색, 두 포인터 등 여러 태그가 붙어있다.
나는 귀찮아서 그냥 넘겼는데, 문제 지문과 알고리즘 분류를 다시 한 번 보니 생각보다 괜찮은 문제인 것 같다.
뭘 풀 지 모르겠을 때 풀면 좋을 것 같다. (사실 풀고 싶은 문제가 이미 많아서 이 문제를 푸는 건 상당히 많은 시간이 지난 후일 것 같다.)
C. 나무가 되고 싶다
이것도 넘어갔는데, B번이랑 다른 이유로 넘어갔다.
일단 N<=500000이다. 이 정도면 Lua로는 풀 수 없다고 봐도 무방할 것 같다.
(실제로, 16ms인 kiwiyou님의 코드를 제외하면 100ms는 그냥 넘어가고, 평균 300ms에 가깝다. C++ 기준으로! 다이아 이상 문제가 아니면 데이터가 이렇게 빡센 문제는 드물다고 알고 있다.)
트리에서 BFS를 돌리면 되는 문제다. 자식 노드를 탐색하면서 정답 값을 1씩 올려주고, 해시테이블에 자식 노드가 있다면 그 자식 노드에서 탐색을 종료하면 된다. 풀이를 떠올리는 건 어렵지 않았다. (골드3 문제다. 나름 기분이 좋다)
노드 번호 제한이 2^60이다. 32비트 정수형을 넘어갈 수 있다는 뜻이다.
Lua에서 64비트 정수형을 지원하는 지는 모르겠으나, 도로의 갯수 문제에서 저 이유로 고생을 했던 기억이 난다.
(결국 Lua로 푸는 데 실패해서 C++로 풀었다.)
또 그런 일을 겪고 싶진 않았고, C++로 문제를 풀자니 내가 너무 바빠서 그냥 넘어갔다.
D. 더워!
틀렸다. 정확히 말하면, "시간 초과" 를 받았다. 로직이 틀렸던 것 같진 않다.
단순 BFS + 해시테이블인 C번과는 달리, 나름 신경쓸 게 많은 BFS 문제인 것 같다.
저번 대회에서 난이도와 상관없이 너무 짧은 코드로만 AC를 받았던 거 같아서 이 문제를 도전하기로 했다.
(BFS 문제는 대체로 코드가 길다. Lua에는 자료형이 테이블 뿐인 관계로, 덱이나 최소힙을 항상 직접 구현해서 쓰기 때문이다.)
상하좌우로 이동하는 경우, 제자리에 앉아서 더위를 식히는 경우로 나눠 무지성 4차원 BFS를 돌렸으나 시간 초과가 나왔고, 디버깅을 통해 원인을 알아냈다.
일반적인 BFS는 방문처리를 하는 배열을 전역변수로 잡는다. 지역변수로 하는 경우는 '우주 탐사선' 이나 '외판원 순회' 같은 특이한 문제들이다. (이런 경우는 방문 배열을 전역으로 할 수 없기 때문이다. 그래서 둘 다 N이 매우 작고, 비트마스킹을 사용한다.)
이 문제의 경우도 N<=100으로 데이터가 작은 것 같아서 방문 처리를 안 했다. 다른 BFS들과 달리 방문했던 곳을 다시 방문하는 경우가 답이 되는 경우가 존재하기 때문이다. 그랬더니 시간 초과가 났다.
그렇다고 전역으로 방문 처리를 할 수도 없다... 그래서 머리를 좀 굴렸다.
방문한 곳을 다시 방문하는 경우가 답이 되려면, 다른 곳에서 더위를 식히고 온 상황이어야 한다.
즉, 다른 곳에 다녀온 경우 중 더위를 식히고 오지 않은 경우는 빼도 된다는 뜻이다. 어차피 Lua에는 불리언 배열이 없으니, 방문 여부를 True랑 False(nil) 로 하지 말고 "해당 칸에 도착했을 때의 불쾌함" 으로 하기로 했다. 다시 해당 칸을 방문하기 전, 불쾌함이 해당 칸의 방문 배열에 저장되어 있는 불쾌함보다 낮은 경우에만 방문해 최솟값을 갱신하도록 한 것이다.
이렇게 하니까 상당히 속도가 빨라졌으나, (아마 이게 정해일 것 같다.) 또 시간 초과가 났다.....
그래서 걍 때려쳤다.
다음은 시간초과 난 개선된 코드이다.
n,m=io.read("*n","*n")
k,c=io.read("*n","*n")
tbl={}
heat={}
tbl[0],tbl[n+1]={},{}
o=io.read()
q={}
qleft,qright=1,2
for i=1,n do
tbl[i]={}
heat[i]={}
local str=io.read("*line")
local j=1
for m in str:gmatch"." do
if m=="S" then sx,sy=i,j end
tbl[i][j]=m
j=j+1
end
end
q[1]={sx,sy,0,0}
dx={1,0,0,-1}
dy={0,1,-1,0}
while qleft<qright do
local nq=q[qleft]
qleft=qleft+1
if heat[nq[1]][nq[2]]==nil then
heat[nq[1]][nq[2]]=nq[4]
else
if nq[4]>=heat[nq[1]][nq[2]] then
goto continue
else
heat[nq[1]][nq[2]]=nq[4]
end
end
if tbl[nq[1]][nq[2]]=="H" then
q[qright]={nq[1],nq[2],nq[3]+1,math.max(nq[4]-k,0)}
qright=qright+1
end
if nq[4]>=100 or nq[4]<0 then goto continue end
for i=1,4 do
local nx,ny=nq[1]+dx[i],nq[2]+dy[i]
if tbl[nx][ny] then
if tbl[nx][ny]=="." then
if heat[nx][ny]==nil then
q[qright]={nx,ny,nq[3]+1,nq[4]+c}
qright=qright+1
elseif heat[nx][ny]>nq[4]+c then
q[qright]={nx,ny,nq[3]+1,nq[4]+c}
qright=qright+1
end
end
if tbl[nx][ny]=="H" then
q[qright]={nx,ny,nq[3]+1,math.max(nq[4]-k,0)}
qright=qright+1
end
if tbl[nx][ny]=="E" then
if nq[4]+c<100 then io.write(nq[3]+1) os.exit() end
end
end
end
::continue::
end
io.write(-1)
억지로 짜낸 솔루션. 나중에 구현해볼 것)
4179번 문제를 풀 때 했던 것처럼 time 변수를 전역으로 한다. 특정 칸을 방문하는 시간이 언제인지 굳이 저장하지 않는다.
이러면 x좌표, y좌표, 불쾌함. 3차원으로 줄어든다.
N<=100이라는 성질을 이용해, 101진법으로 저 세 변수를 표현하면, 세 값을 저장하는 테이블을 인수로 넘겨주지 않아도 되어서 괜찮지 않을까 싶다.
E. 도서 검색 프로그램
파싱 문제. 정규 표현식을 쓴다 쳐도 구현이 좀 많이 빡셀 것 같아 넘어갔다. 플래티넘 난이도라니... 시도해보지 않길 잘 했다.
F. 훈련병의 편지
문제 소재가 마음에 들진 않지만, 문제가 요구하는 로직 자체는 상당히 재미있는 것 같았다. 문자열 알고리즘에 관심이 많던 나라서 고민은 한 번 해봤는데... 답이 전혀 떠오르지 않았다. 그래서 넘어갔다. 정해는 z였다고 하는데, z 문제는 수가 적기에 나중에 꼭 풀어볼 것 같다.
G. 피라미드 게임
마지막 문제! 게임 개발 동아리인 PIMM답게 마지막 문제의 소재는 게임이다.
피라미드 구조를 이용한다는 게 마음에 들어서 더워! 를 풀기 전에 미리 점찍어둔 문제이다.
더워를 푸는 데 실패하고 고민을 조금 해봤으나... 문제를 정독하고 나니 문제 상황 자체가 쉽지 않다는 것을 알게 되었다.
(나는 XOR 연산이 같으면 0, 다르면 1 로 비트를 바꿔주는 연산이라는 건 알지만 XOR 연산의 여러 성질에 대해서는 알지 못한다)
결국 못 풀었으나, 올해가 가기 전에는 꼭, 빠르면 10월 말이나 11월 초 쯤에 이 문제를 다시 풀어볼 것 같다.
태그는 게임 이론, 누적 합, 스프라그-그런디 정리이지만. 에디토리얼에는 dp도 이용한다고 나와 있다.
그건 나중에 볼 것 같다...
나는 2학기 개강 이후 정말 바쁘게 지내고 있다..... 백준을 푸는 데 할당한 시간을 이 글을 작성하는 데 다 써버려서 슬프다.
그래도 대회는 종종 참여할 것 같다.
'코딩' 카테고리의 다른 글
| 월간 향유회 8월 오프 대회 후기 (3) | 2024.09.05 |
|---|
