2022 IOI 국대교육 2주차 (06/27 ~ 07/01)

06/27

학교 수업시수 채워야 해서 불참했다.

 

06/28

BOJ 8243 (POI 12/13 Arch) / O

왕이 1번 노드에서 시작해서 트리 위를 움직이는데, 왕이 도착한 노드는 색칠이 된 상태여야 한다. 현재 왕의 위치는 알 수 있지만, 왕이 어디로 갈지는 모른다. 하루에 칠할 수 있는 노드의 최대 개수를 $X$개라고 할 때, 조건을 만족하도록 할 수 있는 $X$의 최솟값을 구해야한다. 

 

$X$에 대한 이분탐색 + 트리 dp로 해결가능하다.

 

BOJ 11746 (Landscape Improved) / O

돌 $N$개를 바위들 위에 적절히 쌓아서 꼭대기의 높이를 최대화해야 한다.

 

답에 대한 이분탐색을 한다고 가정하고, 각 x좌표에 대해 그 지점에 꼭대기가 있을 경우 돌이 몇 개 필요한지를 세그트리 + 이분탐색으로 계산할 수 있다. 투 포인터를 이용해서 푸는 풀이도 존재하는 것 같은데 그건 잘 모르겠다.

 

BOJ 17366 (%) / X

올바른 괄호문자열 중간에 '.'을 넣은 문자열이 주어진다. $a$번째 문자에서 $b$번째 문자까지 가는 최단경로를 출력하는 쿼리를 $Q$개 처리해야 한다.

 

괄호문자열은 트리 형태로 표현할 수 있다는 사실이 잘 알려져있다. 트리로 바꾸고 쿼리를 잘 처리하면 된다.

 

BOJ 17723 (JOISC 14/15 AAQQZ) / X

문자열이 주어지는데, 어떤 구간 $[i...j]$를 잡아서 그 구간에 있는 문자들을 오름차순 정렬할 수 있다. 이 시행을 정확히 1번 해서 얻은 문자열에서 찾을 수 있는 가장 긴 팰린드롬의 길이를 구해야 한다.

 

오름차순 정렬한 구간이 답이 되는 팰린드롬의 중심과 경계를 포함하는지 여부에 따라 케이스를 나눠서 각각 계산하는 방식으로 풀 수 있다. 총 케이스는 4가지고 각각에 대해 빠르게 계산하는 방법을 찾아서 코딩해야 한다.

 

BOJ 17681 (JOISC 17/18 Fences) / X

이미 지어진 울타리가 있고, 울타리를 완성하기 위해 필요한 최소 비용을 계산해야한다.

 

유의미한 점들을 생각해보면

1. 선분의 양끝점

2. 선분의 끝점에서 다른 선분에 내린 수선의 발

이라는 것을 알 수 있고, 이 점들을 다 잡고 그래프를 만든 다음 다익스트라를 돌려서 한바퀴 도는 비용을 계산하면 된다고 한다.

 

BOJ 17735 (JOISC 13/14 Stamps) / X

0번 기차역에서 $N+1$번 기차역까지 가면서 도장 $N$개를 모두 모으는 최소 비용을 구해야 한다.

 

어떤 기차역에서 상행 플랫폼 -> 하행 플랫폼으로 간 경우와 하행 플랫폼 -> 상행 플랫폼으로 간 경우가 동시에 존재할 수 없다. (최적이 아님)

또한, 방향을 바꾸는 지점을 전부 설정해주면 경로도 결정된다.

따라서, $dp[i][j]:=($현재 $i$번째 기차역까지 봤고, 쓸 수 있는 하행 -> 상행이 $j$개 일 때 최소 비용$)$ 과 같은 형태로 dp를 잡으면 문제를 풀 수 있다.

 

06/29

BOJ 1839 (POI 03/04 Strings) / O

트리를 최소 개수의 끈으로 만들어야 하고, 사용하는 끈의 길이의 최댓값을 최소화해야 한다.

 

사용하는 끈의 길이의 최댓값을 지정해두면 트리 dp로 필요한 끈의 개수를 알 수 있고, 이를 이용하여 이분탐색하면 문제를 해결할 수 있다.

 

BOJ 14449 (USACO 17Gold Balanced Photo) / O

조건을 만족하는 $i$의 개수를 출력하는 문제다.

 

세그트리를 써서 각 $i$가 조건을 만족하는지 확인하면 된다.

 

BOJ 16000 (섬) / △

각 섬에 대해 안전한지 위험한지 판별해야 한다.

 

풀이가 여러 가지 있는데 내가 푼 방식은 그래프를 새로 만들고 단절점을 찾는 방식이다.

 

BOJ 20389 (CEOI16 ICC) / O

초기에 $N$개의 점이 있고, 간선을 하나씩 추가하면서 트리를 만든다. 어떤 간선이 추가되었는지를 쿼리를 날려서 알아내야 한다.

 

연결성분을 하나의 정점으로 보고 새로 번호를 붙이자. 추가되는 간선은 다른 정점을 연결하기 때문에, 두 정점 번호를 보면 다른 비트가 존재한다. 이 비트를 찾는건 $\log{N}$번의 쿼리로 찾을 수 있고, 이 비트를 찾으면 두 집합 $A$, $B$에 대해 끝점이 $A$에 1개, $B$에 1개 있도록 두 집합을 잡을 수 있다. 이제 $A$와 $B$에서 각각 이분탐색을 돌리면 $2\log{N}$번의 쿼리로 실제 간선을 찾을 수 있다. 따라서, 총 $3\log{N}$번의 쿼리로 간선 1개를 찾을 수 있고, 실제로는 상수가 더 작기 때문에 쿼리 횟수는 더 적다. 이 풀이를 구현하면 100점을 받을 수 있다.

 

BOJ 3316 (CEOI10 MP3) / O

버튼을 $N$번 눌러서 최종 볼륨이 $V_2$가 되었다고 한다. 이를 만족하는 최대 $T$의 값과, 그 때 가능한 $V_1$값 중 최댓값을 구해야 한다.

 

버튼 $K$개를 눌렀을 때, 초기 볼륨을 $x$값으로 두고 최종 볼륨을 $y$값으로 둬서 그래프를 그려보면, 최솟값으로 일정하다가, 기울기 1인 직선으로 증가하고, 최댓값에 도달해서 다시 일정해지는 형태라는 것을 알 수 있다. 꺾이는 지점과 최솟값, 최댓값을 저장하면 그래프를 저장할 수 있고, 그래프 2개를 상수시간에 합칠 수 있다. 따라서, 이 그래프로 세그트리를 만들면 문제를 해결할 수 있다.

 

여담으로 나는 대회 때 IOI21 candies의 풀이를 그대로 짜서 맞았다.

 

BOJ 19681 (CEOI20 Star Trek) / O

먼저 게임을 시작하는 사람이 이기는 경우가 몇 가지인지 계산하는 문제이다.

 

풀이가 설명하기엔 너무 길어서 설명하지 않겠다. $D=0$인 경우, $D=1$인 경우, $D \le 10^5$인 경우, $D \le 10^{18}$인 경우를 차례로 풀어보자.

 

06/30

작성중

 

07/01

작성중