전체 글
-
2023 IOI 멘토교육 3주차일기장 2023. 5. 14. 21:24
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번을 좀 더 고민하니 대충 로그복잡..
-
2023 IOI 멘토교육 2주차일기장 2023. 5. 7. 15:10
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 ~ ..
-
PS 일지 (1/3 ~ 1/23)일기장 2023. 1. 24. 17:07
BOJ 17728 (Walls) 각 방벽에 대해 계산하는 쿼리 문제라고 생각하자. 방벽의 이동 경로는 왼쪽 -> 오른쪽 -> 왼쪽 -> 오른쪽 -> ... 과 같은 형태로 나타난다. 시작점이 INF 또는 -INF일 때 경로에서 꺾이는 점을 관리하면 문제를 해결할 수 있다. 방벽의 길이가 증가하면서 꺾이는 지점의 삭제가 일어나고, 이는 연결리스트와 같은 형태로 관리해줄 수 있다. pq를 사용하면 삭제되는 원소를 빠르게 구할 수 있고, 세그를 이용해서 답을 계산할 수 있다. BOJ 17667 (Virus Experiment) 풀이가 다양하다. 풀이 1: https://qwerasdfzxcl.tistory.com/24 (타잔 알고리즘과 비슷하다.) 풀이 2: 풀이 1과 비슷한데, scc를 유파로 전부 들고 있..
-
Semi-local string comparison (수열과 쿼리 42)알고리즘 2022. 12. 10. 20:25
길이가 각각 $N$, $M$인 두 문자열 $A$, $B$의 LCS (Longest Common Subsequence)을 구하는 문제는 매우 유명한 문자열 비교 문제이며, 이는 간단한 dp로 $O(NM)$에 해결할 수 있음이 알려져 있다. 또한, 이를 더 빠르게 하기 힘들다는 것도 알려져 있다. 이 글에서는 $A$와 $B$의 substring의 LCS를 구하는 문제인 semi-local LCS에 대한 빠른 알고리즘을 설명한다. 내용이 매우 길고 복잡하기 때문에, 이 글에서는 핵심적인 내용만 요약해서 설명할 것이며, 자세한 증명은 모두 생략할 것이다. 목차 1. ALCS algorithm 2. Seaweed braids 3. Unit-Monge matrix distance multiplication 4. P..
-
2022 IOI 국대교육 2주차 (06/27 ~ 07/01)일기장 2022. 7. 3. 15:33
06/27 학교 수업시수 채워야 해서 불참했다. 06/28 BOJ 8243 (POI 12/13 Arch) / O 왕이 1번 노드에서 시작해서 트리 위를 움직이는데, 왕이 도착한 노드는 색칠이 된 상태여야 한다. 현재 왕의 위치는 알 수 있지만, 왕이 어디로 갈지는 모른다. 하루에 칠할 수 있는 노드의 최대 개수를 $X$개라고 할 때, 조건을 만족하도록 할 수 있는 $X$의 최솟값을 구해야한다. $X$에 대한 이분탐색 + 트리 dp로 해결가능하다. BOJ 11746 (Landscape Improved) / O 돌 $N$개를 바위들 위에 적절히 쌓아서 꼭대기의 높이를 최대화해야 한다. 답에 대한 이분탐색을 한다고 가정하고, 각 x좌표에 대해 그 지점에 꼭대기가 있을 경우 돌이 몇 개 필요한지를 세그트리 + ..
-
2022 IOI 국대교육 1주차 (06/21 ~ 06/24)일기장 2022. 6. 25. 02:39
1. 국대교육은 아침연습 3문제, 오후실습 3문제로 구성되어있다. 글에 적힌 순서대로 아침연습 123번, 오후실습 123번이다. 2. O는 대회 시간 내로 AC를 받은 문제, △는 업솔빙을 한 문제, X는 업솔빙 안 한 문제이다. 06/21 이 날은 학교 수행 때문에 교육을 빠졌다. 06/22 BOJ 22491 (Repairing) / X 파이프와 밸브가 여러 개 있고, 밸브를 적절히 잠궈서 끝점에 물이 못 흘러들어가게 해야 한다. 이때, 물이 안 흐르는 구간의 길이의 합을 최소화해야 하고 이 값을 출력해야한다. 대충 그래프를 만들었다고 생각하면 끝점에서 bfs 같은걸 돌려서 가장 가까운 밸브들을 전부 잠근 다음 시작점에서 물을 흘려보내서 계산을 하면 될거같다. AC를 받은 사람이 없어서 맞는지는 잘 모..
-
IOI21 Keys 풀이문제풀이 2022. 6. 17. 23:07
어떤 점 x에서 시작해서 방문할 수 있는 점의 집합을 A_x라고 합시다. A_x의 값이 최솟값이라면, A_x의 임의의 원소 y에 대해 A_y = A_x를 만족합니다. 이러한 집합 A_x들을 "최소 집합"이라고 합시다. 구하고자 하는 집합은 최소 집합의 합집합입니다. dfs를 다음과 같은 규칙에 따라 돌려봅시다. 현재 dfs tree를 만들고 있는 상황이라고 생각하고, dfs(v)가 실행중이라고 합시다. v의 서브트리의 원소를 S_v라고 할 때, 1. S_v와 S_v의 여집합을 연결하는 간선 중, S_v에서 얻은 key를 이용하여 갈 수 있는 간선을 차례로 확인합니다. (주의: S_v는 원소가 계속 추가됩니다.) 2. 그 간선을 타고 가서 나온 정점 w를 방문한 적이 없다면 dfs(w)를 호출합니다. df..