qwerasdfzxcl의 ps 블로그 qwerasdfzxcl의 ps 블로그

8/28 ~ 9/4에 헝가리에서 열린 IOI 2023에 한국 국가대표로 참가했다. 한국 팀 멤버는 박상훈(qwerasdfzxcl), 반딧불(79brue), 이동현(lisifu/kizen), 이성호(puppy/windva)였고, 작년에 비해 꽤 강한 멤버였기 때문에 4금을 노려볼만하다고 생각했다. 나와 동현이는 금메달을 받았고, 딧불이와 성호는 은메달을 받으면서 2금2은의 성적을 기록했고, 국가 순위 5등을 했다. 작년에도 IOI에 참가했지만 코로나 이슈로 온라인으로 참가하게 되어서 대회만 치고 끝났는데, 올해는 오프라인으로 직접 헝가리도 가고 여러 행사나 관광을 즐길 수 있어서 매우 좋았다. 솔직히 말하자면 관광은 별 거 없어서 재미없었고 공통 관심사를 가진 외국인 친구들을 많이 만날 수 있었던 것이 너..

(2023.06.11 online IHT with linear memory 문단 추가) 이 글에서는 imos법을 확장한 imos-Hanbyeol Trick (IHT)의 개념과 응용에 대해 설명한다. imos법 imos법이란 구간 덧셈 업데이트를 빠르게 처리하는 테크닉이다. 다음과 같은 문제를 생각해보자. 0으로 초기화된 $N \times N$ 크기의 $2$차원 배열 $A$가 주어진다. 다음 연산을 $Q$개 처리한 후 배열을 출력하여라. $x_1$ $y_1$ $x_2$ $y_2$ $z$: $A[x_1:x_2][y_1:y_2]$에 $z$를 더한다. (앞으로 모든 : notation은 닫힌 구간이다.) 나이브하게 했을 때 시간복잡도는 최악의 경우 $O(QN^2)$이지만, imos법을 사용하면 $O(Q+N^2)..

CEOI 2016을 돌았다. 0:00 ~ 1:47 1번과 2번을 읽었다. 1번은 나이브가 쉽고 풀태는 바로 안 떠올라서 2번을 읽고 풀었다. 나이브랑 풀태 모두 자꾸 틀려서 시간을 많이 날렸다. 처음에 dnc opt 풀이랑 덱dp 풀이를 내서 둘다 짰는데 둘다 틀린 풀이였다. 100점 받으려면 대충 비트스트링 들고 다니면서 적당히 dp 돌려주면 O(NTS)에 문제를 해결할 수 있다. 1:47 ~ 3:34 3번을 읽었다. input 노드 루트개 / output 노드 루트개 연결하는 노드들을 만들고 연결하면 47점을 받을 수 있다. 100점을 받으려면 이를 다중으로 해주면 된다. i번째 층의 노드는 input 노드 P^(i/k)개, output 노드 P^((k-i)/k)개를 연결하는 노드라고 놓으면 추가 노..

BOI 2022 Day 1을 돌았다. 0:00 ~ 0:17 1번 문제를 읽었다. 순열을 쿼리로 날리면 inversion 개수를 알 수 있을 때 N번 이하의 쿼리로 원래 순열을 복원해야한다. 순열을 N번 rotate하면서 넣으면 각 원소의 등수를 알 수 있기 때문에 쉽게 풀린다. 0:17 ~ 1:05 2번 문제를 읽었다. 섭태 풀이가 대부분 쉬웠고 100점 풀이도 쉬울 것 같아서 조금 고민해보기로 했다. 시작에서 끝으로 가는건 최적화하기 까다로워서 거꾸로 끝에서 시작으로 가는 방식을 생각해봤고 문제가 더 간단해졌다. 스파스테이블을 이용한 100점 풀이를 바로 짰고 AC를 받았다. 1:05 ~ 3:52 3번 문제를 읽었다. 가중치가 -M이상 M이하의 정수로 bound되어있을 때 M에 대한 다항시간으로 냅색을..

ROI18에서 4문제 뽑아서 5시간동안 돌았다. 1. Decryption 2. Quick sort 3. Quantum teleportation 4. Addition without carry 0:00 ~ 0:14 1번 읽고 바로 짜서 맞았다. 0:14 ~ 1:52 234번을 읽고 3번을 고민했다. 대충 다익스트라를 이용한 세제곱/64 풀이랑 제곱로그/64 풀이를 냈다. 일단 나이브인 세제곱/64를 짜고 디버깅을 했더니 67점이 긁혔다. 제곱로그/64를 짜고 100점을 받을까 생각해봤지만 x좌표나 y좌표 같은 점이 있으면 안 되는 풀이라는걸 깨닫고 그냥 넘어갔다. 1:52 ~ 2:07 4번은 섭태가 너무 많아서 일단 2번 버블소트로 50점을 긁었다. 2:07 ~ 2:54 2번을 좀 더 고민하니 대충 로그복잡..

USACO 23 us open 골드 123번 / 플래 13번으로 구성된 5문제 셋을 5시간 동안 돌았다. 문제 번호는 순서대로 붙어있다. 0:00 ~ 1:00 초반 1시간에는 문제를 다 읽고 바로 풀이가 보이는걸 짜려고 했다. 근데 풀이가 명확히 보이는건 없어서 일단 1번을 생각해봤다. 키를 배치하는 전략을 찾는 것은 어려울 것 같아서 다른 방향으로 생각해보다가 거꾸로 돌리면 되지 않을까 라는 생각을 하게 되었다. 그 아이디어가 핵심이었고 정방향 / 역방향 탐색을 해주면 문제가 쉽게 풀린다. 1:00 ~ 1:30 2번을 고민했다. 2번과 4번이 컨셉이 같은 문제인데 2번이 요구하는게 적어서 더 쉬울 것 같았다. 조금 고민하니까 2번 풀이가 나왔고 금방 짜서 맞았다. dp를 잘 돌리면 된다. 1:30 ~ ..

BOI 2023을 돌았다. Day 1 0:00 ~ 0:27 문제를 다 읽었다. 1번은 원 그려진거 보고 바로 넘겼고 2번은 인터렉티브라서 일단 넘겼다. 3번은 간단한 dp일 것 같다는 느낌을 받아서 3번부터 풀었다. 한 지점에서 p의 배수가 될 때까지 기다리거나 기다리지 않고 넘어가거나 둘 중 하나만 해도 되기 때문에 간단한 제곱 dp를 짤 수 있다. 이걸 짜면 27점을 받는다. 0:27 ~ 0:43 dp[i] = min_{j

BOJ 17728 (Walls)각 방벽에 대해 계산하는 쿼리 문제라고 생각하자. 방벽의 이동 경로는 왼쪽 -> 오른쪽 -> 왼쪽 -> 오른쪽 -> ... 과 같은 형태로 나타난다. 시작점이 INF 또는 -INF일 때 경로에서 꺾이는 점을 관리하면 문제를 해결할 수 있다. 방벽의 길이가 증가하면서 꺾이는 지점의 삭제가 일어나고, 이는 연결리스트와 같은 형태로 관리해줄 수 있다. pq를 사용하면 삭제되는 원소를 빠르게 구할 수 있고, 세그를 이용해서 답을 계산할 수 있다. BOJ 17667 (Virus Experiment)풀이가 다양하다. 풀이 1: https://qwerasdfzxcl.tistory.com/24 (타잔 알고리즘과 비슷하다.) 풀이 2: 풀이 1과 비슷한데, scc를 유파로 전부 들고 있으면..