tl;dr 글이 너무 길어서 읽기 귀찮다면 결론만이라도 읽자. 개요 요즘 커뮤니티 대회에 관해 말이 많다. 최근 여러 대회에서 대회 이후에 문제 오류가 발견되는 상황이 있었고, 현재의 대회 검수 시스템에 대한 전반적인 재정비의 필요성이 시사된 바 있다. 나 역시 현재의 검수 시스템에 문제가 있음에 동감하는 바이지만, 이 글에서 이야기하고자 하는 바는 아니다. 이 글에서 이야기하고자 하는 것은 문제의 질에 관한 것이다. 조금 민감한 주제일 수 있다는 것을 인지하고 있고, 이 글에 적힌 건 어디까지나 내 의견일 뿐, 절대적인 것이 아님을 전제로 읽어주셨으면 한다. (비고: 글을 올리기 전 몇몇 사람들에게 피드백을 받은 결과, "좋은 문제"의 의미가 조금 모호하다는 이야기를 들었다. 내가 이 글에서 이야기하고..
친구들과 함께 연습셋을 돌았다. 그 중 다이아 이상 문제 몇 개에 대해 간단히 정리해 둔다. BOJ 8473. Monopoly 좌표평면에 $N$개의 점이 주어질 때, 택시 거리가 $c$ 이하인 점들을 간선으로 연결하자. 연결 성분의 개수와 가장 큰 연결성분의 크기를 구하면 된다. 일단 좌표평면을 45도 회전해 생각하면 택시 거리는 체비셰프 거리 $\max(\Delta x, \Delta y)$ 가 된다. 이렇게 변형하면 한 점과 간선으로 직접 연결될 수 있는 점의 영역을 가로/세로 $2c$인 정사각형으로 생각할 수 있다. 이제 이러한 영역 안의 점을 빠르게 찾을 수 있는 방법을 생각해 보자. 위의 좌표 변환을 통해 다음처럼 문제를 변형할 수 있다. 각 점 $(a, b)$가 있고, $x$ 범위가 $[a-c,..
BOJ 8481. Generator
제목만 들어도 모두가 아는 이 전설의 문제는 ONTAK 2010에 출제된 문제다. ONTAK은 폴란드 국가대표 선발 캠프라고 알고 있는데, 자세한 내용은 찾아도 잘 안 나와서 딱히 깊이 알고 있지는 않다.문제는 단순하다. 10개의 파일이 있고, 정수 하나를 입력받아 $(0 \le N \le 10)$ 그저 대응되는 파일의 내용을 출력하기만 하면 된다. 단 코드의 길이는 10만 바이트를 넘을 수 없고, 출력 파일은 예제 파일 $(N = 0)$을 제외하고 모두 20만 바이트를 가뿐히 넘는다는 게 특징.gen0.out그냥 출력하면 된다.gen1.out파일이 너무 커서 웬만한 프로그램으로 열려고 해도 열기 힘들다. 경험상 Visual Studio Code가 이럴 때 정말 좋은 역할을 해 준다.파일을 열어 보면, ..
2월 3일에 열린 솔브드 아레나 파티 Div.1에 미러로 참가했다. 대회 장소가 집에서 멀기도 하고 아레나 #10~#16에 전혀 참가하지 않아서(Arena #16 운영 제외) 선정될 확률도 없었던 터라 본 대회에 참가 신청을 하진 않았다. 대회 결과 5솔브로 본 대회+미러 합산 8등을 했다. 막판에 H를 풀었다면 등수가 크게 올랐을 것 같아서 아쉽다. A. 정렬된 연속한 부분수열의 개수 (0:02) 문제의 조건을 만족하는 모든 $(i, j)$에 대해, $[i, j]$가 다음 조건을 만족하는 $[l, r]$ 중 정확히 하나의 부분구간임을 보일 수 있다. $A_l A_l$ $r=N$이거나 $A_r > A_{r+1}$ 다르게 말..
Problem Solving Diary #16 - ICPC Seoul Regional 2021
이제 곧 ICPC에 참가해야 하기 때문에 ICPC 입문을 조금 해 보기로 했다. 입문 셋으로 ICPC Seoul Regional 2022를 골랐다. 시간은 딱히 재지 않고 문제를 쉬운 것부터 풀어보았다. J. Parentheses Tree 입력으로 주어지는 괄호 문자열을 파싱하는 문제이다. 스택으로 트리를 만들고 DFS를 돌리는 방법도 있지만 시간이 오래 걸릴 수 있다. 트리를 만드는 과정에서 깊이를 관리하면 상수가 더 작고, 따로 스택을 관리할 필요도 없다(실제 트리의 구조를 만들지 않아도 되므로). 시간 복잡도는 $O(|S|)$이다. F. Frog Jump KOI 2019 중등부 2번 문제에 비슷한 게 있었던 것 같다. 서로 겹치는 구간들의 번호가 인접하기 때문에, 이들을 그룹으로 묶어 준다. 이렇게..
https://www.acmicpc.net/problem/18344$G=(V, E)$에서 정점 $1$부터 $N$으로 이동하는 최단거리를 찾아야 한다. 단, 이동 중 시작점과 끝점을 포함해 정확히 여덟 개의 서로 다른 정점을 방문해야 한다.서브태스크 1 (1점)방문하는 정점을 $[v_1, v_2, v_3, v_4, v_5, v_6, v_7, v_8]$이라고 하고, 이때 사용하는 7개의 간선 번호를 $[e_1, e_2, e_3, e_4, e_5, e_6, e_7]$이라 하자. (단, $v_1 = 1$, $v_8 = N$)$e_2$를 고정하면 $(v_2, v_3)$ 또는 $(v_3, v_2)$가 고정된다. 마찬가지로 $e_4$와 $e_6$을 고정하면 ${ v_4, v_5 }$와 ${ v_6, v_7 }$이 고..
KOI 2023 2차 대회 문제들을 풀었다. 초/중/고등부에서 서로 다른 문제는 7개였다. BOJ 28323. 불안정한 수열 어떤 구간 $[l, r]$에 대해 그 안에 있는 수들의 홀짝성이 모두 같다면 이 구간에서는 수를 최대 하나밖에 뽑을 수 있다. 따라서 홀짝성이 같은 인접한 수들은 하나만 남겨도 문제가 없고, 이렇게 합치고 난 뒤 모든 인접한 수들을 고를 수 있고, 이때 남은 수의 개수가 답이 된다. 즉, 첫 수를 고르고, 그 이후로 홀짝성이 바뀔 때마다 고르는 게 최적이다. BOJ 28324. 스케이트 연습 맨 마지막부터 보면서, $i$번 위치에서 속도는 $i+1$번 위치 속도에서 1 늘릴 수 있으면 늘리고, 아니면 최대 제한으로 설정하는 것이 최적이다. 따라서 단순한 순회 한 번으로 $\math..