PS 연습 2

12/20 ~ 1/18

위 기간 동안 1차 선발고사를 대비해 문제를 풀었다.

작년과 매한가지로 4문제/5시간 셋을 자주 돌았다.

12/20(금) - 1일차

기말고사가 끝난 날이다.

놀다가 코포 Div.1 셋을 시간 제한 없이 돌고, 백준 한 문제를 풀었다.

Codeforces Round 990(Div.1)

시간 제한을 따로 설정하지 않고 A, B, C를 풀었다.

A, B는 무난하게 쉬웠다.

C는 대충 세그먼트 트리 + 스위핑으로 풀 수 있었다.

BOJ 24975 Pair Programming

대충 DP를 짜면 된다.

12/21(토) - 2일차

기말고사가 끝난 다음 날이다.

코포 Div.1 셋을 시간 제한 없이 돌고, ARC 셋 하나를 시간 제한 없이 돌고, 백준 두 문제를 풀었다.

Codeforces Round 980(Div.1)

시간 제한을 따로 설정하지 않고 A, B, C를 풀었다.

역시나 A, B는 무난했다.

C는 모든 정점에 0~k-1의 번호를 매기고, 해시로 빈도 배열을 비교해주면 되는 문제였다.

단순 실수로 1시간동안 디버깅했다.

Atcoder Regular Contest 180

시간 제한을 설정하지 않고 A, B, C를 풀었다.

A는 쉬웠다.

B는 못 풀었고, 풀이에서 역함수를 쓴다는 내용까지 읽고 풀었다.

C는 적당한 DP를 짜면 되는데, 오랜만에 문제를 풀어서 그런지 좀 헤멨다.

BOJ 31751 점프 게임

선발고사에서 못 풀었던 문제를 풀기로 했다.

칸을 K개씩 끊어서 DP를 한다는 아이디어는 얼핏 들었던 것 같고, 나머지는 스스로 해결했다.

K개씩 칸을 나눈 뒤 DP를 하면 유의미한 행과 열이 적기 때문에, 이를 세그먼트 트리로 적절하게 관리하면 된다.

구현할 때 상당히 고생했다.

12/22(일) - 3일차

(22024, 14423, 17707, 17699) 셋을 5시간 동안 돌았다.

다이아 3, 4, 5 문제를 모두 시간 안에 자력으로 풀어서 기분이 좋았다.

BOJ 17707 Employment

대충 오프라인 쿼리 + 좌표 압축 + 세그먼트 트리로 풀 수 있다.

쉬워서 10분만에 해결했다.

BOJ 14423 Rope

중간에 색을 바꾸는 것은 의미가 없다는 것을 관찰하고, 2칸으로 만들 수 있는 배열의 형태를 알아내면 구현은 간단하다.

최종적으로 2칸으로 접을 수 있는 배열은 좌우 최대 한 개의 칸을 제외하고, 나머지 칸은 두개씩 모두 색이 같아야 한다.

BOJ 17699 Long Mansion

뭔가 굉장히 복잡하게 풀었다.

우선 각 칸별로 왼쪽, 오른쪽으로 갈 수 있는 최대 칸을 구한 후, 쿼리를 O(1)에 처리할 것이다.

x에서 y로 이동할 수 있을 필요충분조건을 적당한 2차원에서의 조건으로 변환할 수 있고, 이를 분할정복으로 해결할 수 있다.

구현도 복잡했고, 사고의 흐름도 복잡해서 힘들었다.

이보다 훨씬 효율적인 풀이가 있는 듯 하다.

BOJ 22024 Keys

엄청 어렵게 생겼다.

n, m이 2000 이하인 자명 섭테만 풀었다.

업솔빙 예정이다.

12/23(월) - 3일차

나를 국가대표에서 떨어뜨린 문제인 팰린드롬 찾기 문제를 업솔빙했다.

BOJ 31572 팰린드롬 판별하기

대충 하면 된다. 왜 못 풀었는지 모르겠다.

12/24(화) - 4일차

Keys 문제를 업솔빙했다.

BOJ 22024 Keys

적당한 아이디어와 적당한 자료 구조로 풀 수 있으나, 떠올리지 못했다.

각 정점에 대해 그 정점에서 가지고 있는 열쇠로 갈 수 있는 정점을 아무거나 잡아서 단방향 간선으로 연결한다.

그러한 정점이 없다면 스스로에 연결한다.

이렇게 만들어진 그래프는 functional graph의 형태이기 때문에 사이클 하나에 트리가 달려 있는 형태이다.

사이클의 크기가 2 이상인 경우에는 사이클을 하나의 정점으로 압축할 수 있고, 이 과정을 반복하면 모든 사이클의 크기가 1이게 된다.

그러면 사이클 노드에서는 다른 노드로 이동할 수 없고, 다른 노드에서는 사이클 노드로 이동할 수 있으므로 답의 후보는 크기 1의 사이클 뿐이다.

이 과정을 유니온 파인드 2개 + 큰작을 통해서 해결할 수 있다.

풀이를 읽었을 때는 직관적이게 느껴졌지만, 다시 생각해보니 매우 어려운 것 같다.

SCC를 이용한 다른 풀이도 있는 것으로 알고 있다.

12/26(목) - 5일차

나코더 송년대회에 참가했다.

전체 2등을 해서 버즈를 받았다.

12/28(토) - 6일차

(20089, 17669, 22025, 25441) 셋을 5시간 동안 돌았다.

다이아 5, 4 문제를 풀었다.

Codeforces Round 941 버추얼을 돌았다.

Good Bye 2024 코포에 참가했다.

BOJ 20089 Unscrambling a Messy Bug

분할정복을 잘 해주면 된다.

문제 풀이 생각하는데 오래 걸렸다.

BOJ 25441 디지털 회로

노드 v의 자식의 수를 k라 하고, i번째 자식을 1로 만드는 경우의 수를 $a_i$, i번째 자식을 0/1로 만드는 경우의 수를 $b_i$라 하면

v를 1로 만드는 경우의 수는 $a_i \times b_1 \times b_2 \times \ldots \times b_k / b_i$의 합과 같은데, $a_i$의 계수가 상수이므로 각 리프 정점이 가지는 가중치가 하나로 결정된다.

이후 구간 뒤집기를 지원하는 레이지 세그를 짜면 된다.

생각보다 빨리 풀었다.

BOJ 17669 Meetings

한참 생각했는데 못 풀었다.

풀이는 생각보다 간단하다.

전체 트리에서 일부 정점이 생략된, 일종의 "느슨한" 트리를 관리한다고 하자.

처음에는 0, 1번 정점만 연결되어 있다.

정점 u를 이 느슨한 트리에 추가한다고 하자.

현재 트리의 센트로이드를 c라고 하고, c의 자식을 서브트리 크기가 큰 것부터 v1, v2, ..., vk라고 하자.

처음에 u, v1, v2 쿼리를 날리자.

- 쿼리 결과가 u라면, u는 c-v1 사이에 들어가거나 c-v2 사이에 들어간다. u, c, v1 쿼리를 날리면 둘 중 어딘지 알 수 있다.

- 쿼리 결과가 v1이라면, u는 v1의 서브트리 내에 존재한다. 재귀적으로 해결하면 된다.

- 쿼리 결과가 v2라면, v1인 경우와 같이 재귀적으로 해결하면 된다.

- 쿼리 결과가 c라면, v1, v2 대신 v3, v4로 재귀적으로 해결한다.

- 쿼리 결과가 w(트리에 없는 정점)이라면, w는 v1-v2 경로 내에 존재하므로 첫 번째 경우와 같이 w를 집어 넣고, w에 u를 연결하면 된다.

이 과정을 반복하면 한 노드 당 쿼리를 최대 O(logN)번 날려서 처리할 수 있으므로, O(NlogN)번의 쿼리로 전체 문제를 해결할 수 있다.

Codeforces Round 941(Div. 1)

A, B, C를 풀었다.

A - 정렬하고 차배열을 만들었을 때, 1이 아닌 수가 나오는 첫 번째 수의 위치의 홀짝을 보고 판단할 수 있다.

B - k=1인 경우는 따로 처리하고, k>1인 경우는 k-1 이하의 수를 이진법으로 만들고, k+1 이상의 수는 수의 셋과 최댓값을 관리하면서 구성하면 된다.

C - 1, 0이 나옴에 따라 지그재그로 이동하면서 최소 길이를 구할 수 있다.

Good Bye, 2024!

개조졌다. 따로 후기를 쓰지는 않겠다.

1/1(수) - 7일차

17738, 20346, 21770, 27994로 이루어진 셋을 돌았다.

앞의 두 문제는 풀었고 나머지 두 개는 마지막 섭테 빼고 다 풀었다.

BOJ 17738 Voltage

케이스웍을 잘 해주면 된다.

홀수 사이클이 있는 컴포넌트의 개수를 $o$라고 하자.

$o \ge 2$인 경우, 답은 0이다.

$o = 1$인 경우, 주어진 그래프를 트리로 펴서 트리 엣지와 백 엣지로 나눈 뒤, 홀수 사이클을 만드는 백 엣지를 홀수 간선, 짝수 사이클을 만드는 백 엣지를 짝수 간선이라고 하자. 답은 (모든 홀수 간선의 경로의 교집합) - (모든 짝수 간선 경로의 합집합)이 된다. 이 때, 홀수 간선이 한 개라면 그 간선도 답에 포함되므로 1을 더해주면 된다.

$o = 0$인 경우, 트리의 모든 정점은 다 가능하고, 짝수 간선만 있는 그래프는 짝수 간선 경로에 포함되지 않는 모든 간선이 가능하다.

BOJ 20346 Card Trick

생각보다 풀이가 간단했던 문제다.

사이클 분할을 한 뒤 스왑을 통해 각 사이클의 크기를 ⌈52 / (S+1)⌉로 만든 뒤, 사이클을 따라가며 답을 찾으면 된다.

BOJ 27994 Passport

이 문제는 못 푼게 살짝 아쉽다.

$O(N^2)$의 섭테는 [1, N]의 구간에서 시작하는 0-1 BFS를 돌려서 각 구간까지의 최단 거리를 구하면 된다.

풀 섭테는 [1, N]까지의 경로를 1까지의 경로와 N까지의 경로로 나눠서 생각한다.

1까지의 경로와 N까지의 경로는 특정 위치 x까지는 경로가 공통일 것이고, 이후는 나눠질 것이다.

따라서 이 위치 x를 고정하면 i에서의 답은 (i부터 x까지 거리) + (x부터 1까지 거리) + (x부터 N까지 거리)가 된다.

이 때 N+1번 정점을 만들어 모든 정점까지의 거리를 1까지 거리와 N까지 거리의 합으로 놓은 뒤, 다익을 돌려서 N+1부터 1~N까지 거리를 구하면 된다.

이 때, 간선의 형태가 a와 [b, c]의 모든 정점이 연결된 형태이므로, 세그먼트 트리를 이용해 간선을 줄이는 테크닉을 사용하면 된다.

BOJ 21770 Fake Plastic Trees 2

 

신기한 문제인 것 같다.

정점 N개로 이루어진 트리에서 $0 \le i \le K$인 모든 i에 대해 간선을 i개 끊어서 각 컴포넌트의 가중치 합이 $[L, R]$에 포함되는 것이 가능한지 출력해야 한다.

에디토리얼은 복잡하게 써있는데, 결국 어떤 트리 dp를 최적화하는 것이다.

길게 쓰긴 귀찮으니, 대충 검은 돌 dp와 R-L 뭉탱이에서 두 개만 관리하는 방식으로 풀면 된다는 것만 짚고 넘어가겠다.

1/2(목) - 8일차

16783, 17168, 17705, 20078로 이루어진 셋을 돌았다.

20078 제외 나머지 세 문제를 풀었다.

BOJ 16784 Bulldozer

Bulldozer Trick으로 흔히 불리는 테크닉의 원본 문제인 것으로 알고 있다.

생각보다 별 건 없고, 그냥 금광 세그를 관리하면서 기울기 순으로 직선을 돌려주고, 순서를 잘 뒤집어주면 $O(N^2logN)$에 풀 수 있다.

BOJ 17168 Water Knows The Answers

물의 양이 가장 많아지는 형태는, 좌우에 직사각형을 위로 길게 놓고, 가운데에 나머지 직사각형을 좌우로 길게 놓는 것이다.

왼쪽, 오른쪽에 놓는 직사각형의 번호를 i, j라 하면, 물의 양은 f(i)+g(j)+h(i)k(j)의 형태가 된다. 따라서 CHT로 문제를 해결할 수 있다.

BOJ 17705 Memory 2

일단 Pi=i인 섭테를 먼저 생각해보면, 처음에 2i와 2i+1(0<=i<N)의 쿼리를 날린다. 0부터 N-1까지 순서대로 보면, 쿼리 값이 i인 쌍은 한 개 또는 두 개 존재할 것이다. 쌍이 한 개라면 그냥 그 쌍의 두 수가 i가 되고, 쌍이 두 개라면, 3번의 쿼리를 추가로 날려 각 쌍의 어떤 값이 i인지 알 수 있다. 그리고 남은 두 개의 수들은 다시 쿼리를 날려 저장해 놓는다.

비슷한 논리로 전체 문제를 풀 수 있는데, 쿼리 값이 i인 쌍이 두 개 존재한다면, 위와 같은 방법으로 해결할 수 있고, 그런 i가 없다면 모든 쿼리 값에 대해 쌍이 한 개 존재하므로 각 쌍은 쿼리 값에 해당함을 알 수 있다.

BOJ 200178 Toy Train

게임 이론 문제다. 아직도 이런 문제는 어떻게 접근해야 하는지 잘 모르겠고, 풀이를 보고 업솔빙을 했음에도 풀이가 100% 와닿지는 않는다. 그냥 납득만 된 정도인 것 같다.

A가 무슨 짓을 해도 충전소에 도달하지 못하는 시작 정점의 집합을 S라고 하고, A가 무슨 짓을 해도 무조건 S의 정점에 도달하는 시작 정점의 집합을 S'이라고 하자. S, S'은 위상정렬하듯이 구할 수 있다.그러면 S'은 무조건 답의 부분집합일 것이다. 이 때 충전소가 S'에 포함된다면, 그 충전소는 충전소의 의미를 잃게 된다. 따라서 그 정점을 충전소가 아니라고 하고 다시 S, S'을 구해야 한다. 이 과정을 반복하면 O(NM)에 문제를 해결할 수 있다.

1/3(금) - 9일차

17693, 18434, 20062, 27460으로 이루어진 셋을 돌았다.

27460을 해결했고, 17693을 시간이 끝난 후 풀이를 따로 보지 않고 풀었다.

BOJ 27460 Where Is The Root?

일단 리프 정점에 쿼리를 날리면 루트가 리프에 있는지 리프가 아닌 정점에 있는지 알 수 있다. 이후는 이분 탐색으로 구하면 된다.

그러나, 이렇게 하면 쿼리 수는 9+1=10이 되므로 다른 방법을 고민해야 한다.

리프 정점을 벡터에 쭉 넣고, 리프가 아닌 정점을 벡터에 쭉 넣는다고 하자.

그러면 이 벡터의 prefix에 대해 쿼리를 날리면 답이 그 prefix 안에 있는지, 뒤에 있는지 알 수 있다.

그러면 그냥 선형 이분탐색을 하면 되므로 9번의 쿼리로 해결할 수 있다.

BOJ 17693 Port Facility

두 구간이 ABAB와 같이 겹친다면 두 구간 사이에 간선이 있다고 보자.

홀수 사이클이 생기는 경우 답은 0이고, 그렇지 않은 경우 답은 2^(component) 개수이다.

component의 개수를 센 뒤, 홀수 사이클을 판별한다고 하자.

한 구간에서 시작해 bfs를 돌린다고 하자. max 세그먼트 트리로 각 구간을 l에 대해서 r을 관리하고, r에 대해서 l을 관리한다고 하면, O(logN)의 시간복잡도로 인접한 다음 구간을 구할 수 있다. 이 때, 모든 구간의 색을 1, 2로 칠하고, 다음 구간으로 이동할 때 현재 구간과 반대의 색을 칠할 것이다. 그리고 각 구간에 도달했을 때에는 그 구간의 정보를 세그먼트 트리에서 삭제할 것이다.

이렇게 O(NlogN)의 시간복잡도에 문제를 해결할 수 있다.

시간 중에는 O(Nlog^2N)을 짰다가 터졌다. ㅜㅜ

1/4(토) - 10일차

기말고사가 끝나고 다시 ps를 시작한지 벌써 10일차가 되었다.

실력이 점점 늘어가는게 느껴지...지는 않고 아직 침체기인 것 같다.

10841, 25434, 25440, 26415로 이루어진 셋을 돌았다.

25434, 26415를 풀었다.

BOJ 25434 Magic Cards

한참 고생했다.

대충 (K-1)!을 만들 수 있음은 자명하다.

그런데 7!=5040이고 N<=10,000이므로 반으로 줄일 방법을 찾아야 한다.

mod 7로 보면 비둘기집 원리에 의해 나머지가 같은 두 수가 항상 존재한다.

그 두 수의 차이를 +쪽과 -쪽 중 작은 것으로 하면 5000으로 줄일 수 있고, 두 수 사이의 값은 7의 배수이므로 7로 나눈 값으로 해도 된다.

즉, 5000/7~=720 정도로 줄일 수 있고, 이는 6! 이하이므로 문제를 해결할 수 있다.

BOJ 26415 Ghost

못 풀면 좀 슬펐을 뻔한 문제이다.

일단 외곽 순환 도로 문제의 아이디어를 빌려오면, 이진 트리일 때 2N 이하의 트리를 construct한다면 일반적인 트리에 대해서 대충 4N 이하에 풀 수 있음을 알 수 있다.

따라서 이진트리만 해결하겠다.

이진트리에서 Naive한 방법을 떠올리면, 모든 정점이 자신과 부모 정점을 가지고 있고, 연결이 필요한 리프 노드에 대해 두 리프 노드의 경로에 하나의 리프 노드를 모두 추가하는 것이다.

이렇게 하면 하나의 노드에 들어가는 값은 자신(1), 부모(2) + 이 노드를 지나는 리프 노드 경로 3개(3, 4, 5)이므로 최대 5개이다. 이를 해결하는 방법이 필요하다.

이는 생각보다 간단하게 해결이 가능한데, 자식이 두 개인 모든 노드에 대해, 그 노드를 세 개의 노드로 분할하면 된다.

이 노드를 v라 하고, 왼쪽 노드를 l, 오른쪽 노드를 r이라 하면 v와 l 사이에 vl을 추가하고, v와 r 사이에 vr을 추가하자.

v에 v를 넣고, vl에 v, l을 넣고, vr에 v, r을 넣으면 v는 리프 경로 최대 3개, vl과 vr은 리프 경로 최대 2개가 통과하므로 각 노드의 집합은 크기가 최대 4라는 것을 알 수 있다.

1/5(일) - 11일차

IOI 2023 Day 2를 돌았다.

31+100+35 = 166점을 받았다.

Robot Contest 문제가 아주 재밌는 것 같다.

그리고 현재 폼이 괜찮은 것 같다.

BOJ 29749 Overtaking

65점까지는 간단하게 해결할 수 있다.

우선 N번 버스가 없다고 가정하고 0~N-1번 버스의 각 지점 별 도착 시간을 구해 놓자.

N번 버스가 0~N-1번 버스의 도착 시간에 영향을 줄 수는 있지만, 이 영향이 다시 N번 버스에 영향을 줄 수는 없다는 사실을 관찰할 수 있다.

따라서 0~N-1번 버스의 도착 시간은 그대로라고 가정하고 N번 버스의 도착 시간을 구하면 O(QMlogN)에 문제를 해결할 수 있다.

이제 전체 문제를 풀어 보자.

문제를 들여다 보면, y=x+a에 계단이 여러 개 있는 함수 M-1개를 합성하는 문제와 같음을 알 수 있다.

이 때 계단이 A개 있는 함수와 계단이 B개 있는 함수는 O((A+B)log(A+B))에 간단하게 합성할 수 있다.

이를 순서대로 합성하면 O(N^3logN)이 돼서 터지고, 분할 정복으로 빠르게 합쳐주면 O(N^2log^N)이 되어 시간 내에 문제를 해결할 수 있다.

시간 복잡도가 이 모양이라 살짝 불안했는데, 바로 맞아서 기뻤다.

BOJ 18434 Olympic Bus

1/3에 못 푼 문제를 업솔빙했다.

풀이는 생각보다 매우 간단한데, 시간 중에 못 푼게 좀 아쉽다.

각 간선을 뒤집었을 때 1부터 N까지 최단 경로를 구하자.

1부터 N까지 최단 경로를 먼저 하나만 찾고, 현재 뒤집고자 하는 간선이 최단 경로에 포함되는지 아닌지로 경우를 나눌 것이다.

현재 간선이 최단 경로에 포함되는 경우, 다시 다익스트라를 돌리면 된다.

현재 간선이 최단 경로에 포함되지 않는 경우, 원래 최단 경로와 뒤집힌 간선을 이용한 최단 경로 중 작은 값이 된다. 이 때 뒤집힌 간선을 이용한 최단 경로는 전처리로 구할 수 있다.(1부터 x까지 최단 경로, y부터 N까지 최단 경로)

1/6(월) - 12일차

10717, 17697, 18435, 29203으로 이루어진 셋을 돌았다.

17697 빼고 다 풀었다.

밤에 10841을 업솔빙했다. 금방 푼듯

BOJ 29203 테마파크

대충 큰작으로 풀 수 있다.

priority_queue<pair<int, vector<int>>>를 빠르게 합쳐주면 된다.

계속 시간 초과가 떠서 고생했는데, 결론적으로 vector<int>를 vector<int>*로 고치니 맞았다.

벡터를 넘기면서 시간 초과가 발생한 것 같다.

BOJ 10717 성벽

각 위치에서 상하좌우로 갈 수 있는 최대 칸을 구하고, 대각선별로 보면서 대충 세그로 풀면 된다.

BOJ 18435 Fire

A[i]의 왼쪽 원소 중 A[i]보다 크면서 i에 가장 가까운 원소까지의 거리를 l[i]라고 하고, 오른쪽 원소까지의 거리를 r[i]라 하자.

A[i]가 점유하는 칸을 x축이 i, y축이 t인 xy 평면에 나타내면 가로 rv, 세로 lv인 평행사변형이 된다.

이제 스위핑으로 문제를 해결할 것이다.

이 때 rv>lv인 경우 (i, t) 평면에서 lv개의 값만 고려하면 되고, rv<lv인 경우 (i, t-i) 평면에서 rv개의 값만 고려하면 된다.

즉, min(lv, rv)개의 값을 업데이트하면서 스위핑하면 된다.

min(lv, rv)의 합은 대충 NlogN쯤 되기 때문에, Nlog^2N+QlogN에 문제를 해결할 수 있다.

BOJ 10841 매트

전에 셋을 돌 때 시간이 부족해서 못 풀었던 문제를 풀이를 보지 않고 업솔빙하는 것에 성공했다.

대충 위 조각을 A, 아래 조각을 B라 하겠다.

A, B 각각 오른쪽 끝점을 기준으로 정렬해서 DP를 할 것이다.

D[i][j] : A는 i까지, B는 j까지 봤을 때 최댓값이라 하자.

이 때 D[i][j]에서 D[k][j] 또는 D[i][k]로 업데이트될텐데, 오른쪽 끝점이 더 작은 인덱스가 바뀌는 방향만 업데이트할 것이다.

이렇게 하면 A, B 사이에 겹치는 것을 고려하지 못하는 경우가 배제된다.

또한 D[i][j]에서 업데이트되는 다음 인덱스를 D[x][y]라 하면(x=i 또는 y=j), x와 y가 겹치는지는 고려하지 않고, 나중에 D[x][y]에 도달했을 때 무시하는 방식으로 처리할 것이다.

이렇게 하면 O(N^3) DP가 간단하게 차려진다.

이제 뿌려주는 DP를 가져오는 DP로 바꾸고 비슷하게 처리하되 모든 k를 다 돌지 말고, 유효한 k의 조건을 적당히 구해서 누적 max 배열로 구하면 된다.

이 때, D[i][j]에서 i가 더이상 움직이지 않겠다고 마음 먹은 경우 j의 오른쪽 끝이 i의 오른쪽 끝보다 더 큼에도 불구하고 j가 움직일 수 있다. 이를 예외처리해주는 과정이 필요하다.

1/7(화) - 13일차

계절학교가 시작했다!

계속반인데, 3시간 5문제를 주는데 3시간 동안 350을 받았다.

이후 다른 문제들의 풀이를 듣고 다 업솔빙했다.

계학 문제를 다 풀고 14521, 19556, 16781, 31442로 이루어진 셋을 돌았다...가 졸려서 때려치고 다음날로 미뤘다.

BOJ 14521 Zagarde

센트로이드 분할을 하면 된다.

대충 하면 된다.

1/8(수) - 14일차

계절학교 둘째 날이다!

오늘은 4문제 중 200점을 받았다.

이후 다른 문제들 교수님의 힌트를 살짝씩 듣고 풀었다.

계학 문제 다 풀고 어제 돌던 셋을 마저 돌았다.

BOJ 20042 Hotspots

계학 문제다.

좌우로 스위핑하면서 각 지점별로 유효한 반지름 개수를 N개씩 남길 수 있다.

이후 DP를 하면 O(N^2)에 문제를 해결할 수 있다.

여기서 아이디어를 잘 쓰면 O(N)에도 풀 수 있다고 하고, 그 문제는 Hotspots 2이다.

BOJ 30852 Apricot Seeds

계학 문제다.
이 문제는 거의 자?력이다.

l~r에서 버블 정렬을 k단계까지 하면 prefix sum이 특정 구간에서 가장 작은 수 몇 개의 합으로 표현된다.

이는 PST를 이용해 구할 수 있다.

BOJ 16781 Skyscraper

셋 도는 시간 내에 자력으로 풀었다.

대충 connected component DP를 하면 된다.

10분 동안 식 짜고 구현하니 바로 맞았다.

1/9(목) - 15일차

BOJ 19556 Colors

업솔빙을 했다.

이분탐색을 아주 잘 하면 된다.

이런 문제가 매우 어려운 것 같다.

1/10(금) - 16일차

BOJ 32384 Pair Sorting

계절학교 문제였다.

대충 될 법한 해를 찾을 수 있다.

제한이 $0.7n^2$으로 매우 빡빡해서 가능한 경우가 몇 가지 없음을 알 수 있다.

BOJ 18275 Sob

계절학교 문제였다.

그리디를 하면 맞는다.

BOJ 22025 Fountain Parks

70점까지는 스스로 풀었고, 만점은 풀이를 보고 업솔빙했다.

70점까지는 각 벤치에 매칭되는 도로가 최대 2개이므로, 아무렇게나 spanning tree를 구성한 뒤 잘 매칭해주면 된다.

만점은 모든 벤치를 체스판으로 칠하고, 검은 벤치는 무조건 위/아래 도로에 매칭하되 위 도로의 우선순위를 높게 하고, 흰 벤치는 무조건 좌/우 도로에 매칭하되 좌 도로의 우선순위를 높게 하면 무조건 모든 점이 연결됨을 증명할 수 있다.

체스판 아이디어가 좀 중요한 것 같다.

BOJ 32071 양손에 V

DP를 잘 해주면 O(N^2)에 해결할 수 있다.

구현이 좀 골치아픈 문제였다.

BOJ 15844 Land of the Rainbow Gold

오일러 공식(V-E+F=C+1)을 사용하고, PST를 이용해 2D 쿼리를 계산하면 된다.

오타 하나 때문에 계속 틀렸다..

BOJ 31442 좋은 수열

답이 될 필요충분조건을 잘 관찰하고 이를 세그먼트 트리로 옮기면 되는 문제이다.

문제가 매우 아름답고, 풀기도 어려웠다.

1/11(토) - 17일차

겨울학교 모의고사를 봤다.

따로 백준 문제를 풀지는 않았다.

1/12(일) - 18일차

15865, 31820, 17643, 16983으로 이루어진 셋을 돌았다.

BOJ 25021 알록달록한 괄호열

전에 못 풀었던 문제를 업솔빙했다.

적당히 O(N^2) 상태 공간의 DP 식을 중복을 고려하여 잘 세우고, 이를 O(N^3)에 잘 계산하면 된다.

BOJ 15865 Genetics

각 문자열에 랜덤한 가중치를 부여하고, 각 위치별로 각 문자가 있는 문자열의 가중치의 합을 구해 놓는다.

이후 각 문자열별로 그 문자열이 답의 후보로 가능한지를 판별할 수 있다.

문자열이 1개 남을 때까지 위 과정을 반복하면 되는데, 생각보다 금방 답이 나온다.

BOJ 17643 Amusement Park

우선 DAG의 개수를 세면, 답은 (DAG의 개수)*M/2가 된다.(임의의 DAG는 모든 간선을 뒤집어도 DAG이기 때문이다.)

D[i]를 i의 모든 정점으로 만들 수 있는 DAG의 개수라고 하면, i의 정점 중 outdegree=0인 정점을 j라 했을 때, D[i]는 D[j]의 합이 된다. 이 때 중복이 발생하므로 포함과 배제의 원리로 잘 세주면 된다.

생각보다 간단한 문제였는데, 발상이 어려운 것 같다.

BOJ 16983 Coin Collecting

개쩌는 그리디를 하면 풀린다.

나도 완전히 발상까지 이해하진 못했고, 어느 정도 납득만 한 수준이다.

사람에 따라 느껴지는 난이도가 매우 다양할 것 같다.

BOJ 12008 262144

문제 제목이 "262144"이다.

과일 게임 문제를 업솔빙하기 전에 풀어봤다.

1/13(월) - 19일차

32130, 23063, 16780, 20194로 이루어진 셋을 돌았다.

BOJ 31284 과일 게임

선발고사 때 5점을 받은 슬픈 기억이 있는 문제다.

그 때는 될 것 같은 금광을 1시간 동안 짜다가 터지고 결국 기본 서브태스크도 다 못 풀었다.

지금은 48점을 가볍게 받을 수 있었고, 전체 문제 풀이도 해설을 보고 구현해보았다.

일단 a가 b개 연속해 있으면 (a, b)의 쌍으로 표현하자.

핵심적인 아이디어는 a>c, b>c인 a, b, c에 대해 (a, x), (c, y), (b, z) 쌍이 연속해 있으면 c는 최대한 합쳐도 된다는 것이다. 이 때 y가 짝수라면 (c, y)를 (c+1, y/2)로 만들면 되고, y가 홀수라면 (c, y-1), (inf, 1), (c, y-1)로 만들면 된다.

이를 반복하면 (inf, 1)로 분리된 bitonic한 수열의 형태가 나오고, bitonic한 수열에서는 작은 과일부터 합치면서 최댓값을 계산할 수 있다.

이 때 만들 수 있는 수의 최댓값이 30 이하이므로, bitonic한 수열의 길이는 60 이하임을 알 수 있다.

이를 금광 세그로 구현하면 된다.

구현이 좀 복잡한데, 어떻게 꾸역꾸역 풀었다.

BOJ 20077 Wiring

어쩌다 보니 오늘 푼 문제들은 잡담이 많은 것 같다.

일단 이 문제는 백준에 같은 문제가 2개 정도 있다.

놀랍게도 2007년 한국 ICPC 문제와 겹치는데, 이런 문제가 IOI에 나왔다는 것이 신기하긴 하다.

적당한 그리디를 짜면 되는데, 이 그리디가 매우 어렵다.

귀찮아서 풀이를 적지는 않겠다.

BOJ  16780 Selling RNA Strands

주어진 문자열들 중 Prefix가 P이고, Suffix가 Q인 문자열의 개수를 빠르게 세야 한다.

Prefix와 Suffix 따로 Trie를 만들고 오일러 투어로 넘버링을 하면 Prefix가 P일 조건과 Suffix가 Q일 필요충분조건은 Prefix Trie와 Suffix Trie에서의 번호의 구간으로 나타난다.

즉, 2차원 쿼리로 환원할 수 있고 이는 PST로도, MST로도 풀 수 있다.

나는 MST를 짜서 바로 맞았다.

BOJ 32130 도시

풀이가 간단한데 왜 못 풀었는지 모르겠다.

일단 간단한 $O(N^2L3^N)$ DP를 떠올릴 수 있다. (0 : 개발 x / 1 : 개발 but 도시 불가능 / 2 : 개발 and 도시 가능)

여기서 state의 개수를 줄여야 하는데, 0과 2가 연속하지 못한다는 성질을 이용해 줄일 수 있다.

나는 왜인지는 모르겠지만 상수 최적화를 좀 해야 했다.

1/14(화) - 20일차

일지를 적다 보니 풀이를 점점 대충 쓰는 것 같다.

애초에 풀이를 그렇게 잘 쓸 생각이 없었기에 그냥 진행시키려 한다.

글을 조만간 한 번 끊고 다음 글에서 써야 될 것 같기도 하다.

오늘은 32074, 17687, 17715, 29201로 이루어진 셋을 돌았다.

BOJ 29201 K-정렬 게임

어떻게 열심히 해서 시간 내에 풀긴 했다.

일단 문제를 딱 보면 inversion의 개수와 관련이 깊어 보인다는 생각이 든다.

실제로 K=1인 경우 inversion의 홀짝에 따라 답이 결정된다.

이는 한 번 swap을 진행할 때 inversion의 홀짝이 항상 바뀌기 때문이다.

비슷하게 K가 1이 아닌 경우도 생각해볼 수 있다.

K+1, ..., N에서의 inversion과 1, ..., K에서의 inversion의 합을 이 수열의 inversion으로 정의하자.(일반성을 잃지 않고, A[1], ..., A[K] 중 1이 있다고 가정하자.)

이 때 A[K]=1이면 그냥 수열의 inversion의 홀짝으로 답이 결정된다.

A[K]가 1이 아니고 수열의 inversion이 홀수라면, 답은 무조건 선공이 이긴다.(A[K]와 1을 바꾸면 된다.)

이제 A[K]가 1이 아니고 수열의 inversion이 짝수인 경우에 대해 누가 이기는지를 파악해야 한다.

이 경우 이기기 위해서는 무조건 수열의 inversion이 짝수인 상태로 상대에게 넘겨줘야 한다는 것을 알 수 있고, 그러기 위해서는 A[K]와 A[K+1], ..., A[N] 중 하나를 바꿔야 한다. 이 때, 바꾼 두 수의 홀짝은 같아야 한다.

이 넘겨준 상태에서 선공이 지는 경우의 수가 하나라도 있다면, 나는 이길 수 있다.

따라서 D[i] : A[K]=i, 수열의 inversion이 짝수일 때 이기는가? 로 정의해서 O(N)에 D[A[K]]를 구하고, Fenwick Tree로 전체 수열의 inversion을 구하면 답이 나온다.

대충 관찰하고 풀어서 계속 틀렸다. ㅜㅜ

BOJ 17687 Bitaro's Party

우선 나는 백준에서 100점을 받지 못했고, oj.uz에서 100점을 받았다.

상수 최적화가 좀 쓰레기인 문제인 것 같다.

쿼리에서 주는 수의 개수가 sqrt(N)보다 큰지 작은지로 나눠서 생각하자.

(1) sqrt(N)보다 큰 경우 -> 이 경우는 최대 sqrt(N)번 등장하므로 매번 DP를 다시 돌리면 된다.

(2) sqrt(N)보다 작은 경우 -> 전처리를 통해 각 수까지의 최장 경로 sqrt(N)를 저장해놓으면 된다.

시간복잡도는 O(NsqrtN)인데, N=10만임에도 불구하고 시간초과를 받는 것을 보면 쓰레기 문제임이 확실하다.

BOJ 17715 Worst Reporter 2

이 문제는 시간이 지난 후 풀이를 보지 않고 풀었다.

적당한 그리디로 문제를 해결할 수 있다.

2시간 지난 후의 결과를 +, 5시간 지난 후의 결과를 -로 표현하자.

그러면 적당히 수를 재배정해서 각 수의 +-를 누적했을 때 0 이상이 되게 해야 한다.

-를 쭉 훑으면서 배정될 수 있으면서 -와 같은 수를 가지는 +를 아무거나 배정해주면 되...는 줄 알았다.

그러나 -가 앞의 +를 가져가버리면서 앞의 -에 대응될 수 있는 +가 없어지는 경우가 발생한다.

따라서 이 조건을 레이지로 적당히 처리하고, 각 -에서는 같은 수를 가지는 + 중 가장 오른쪽 +를 배정해주면 된다.

1/15(수) - 21일차

12754, 21795, 27364, 5814로 이루어진 셋을 돌았다.

BOJ 27364 Floppy

카르테시안 트리를 만들고 각 노드의 좌우 노드 유무를 전달하면 된다.

BOJ 5814 마상시합 토너먼트

우선 쿼리 구간을 원래 배열에서의 구간으로 바꾸자. 이는 레이지 세그로 할 수 있다.

이제 각 위치별로 그 위치에 N번 기사가 올 때 살아남는 횟수를 구해야 한다.

이는 max 세그와 k번째 수를 찾는 세그를 이용해 처리할 수 있다.

BOJ 12754 스왑

oj.uz에서는 100점이 나오는데 백준에서는 68점이 나온다.

또 시간/메모리 최적화 쓰레기 문제 인것 같다.

대충 D[i][j]를 a[i]=j일 때 만들 수 있는 가장 사전순 최소 배열이라고 하면, j와 a[2*i]와 a[2*i+1]의 대소 관계에 따라 적당히 구해줄 수 있다. 이 때 가능한 (i, j)의 쌍이 대충 O(NlogN)개이고, 그 쌍에서 배열 길이의 합이 O(Nlog^2N)이라 그냥 구현해주면 된다.

라고 생각했지만 왜 또 백준에서는 안 나오는지 모르겠다.

풀었다고 생각하고 넘어갔다.

1/16(목) - 22일차

10716, 17670, 17149, 23065로 이루어진 셋을 돌았다.

BOJ 20172 Electric Vehicle

계절학교에 나온 문제이다.

이 문제도 BIKO 서버에서는 돌아가는데 백준에서는 시간초과가 난다.

한 점에서 다른 점까지 이동할 때 항상 최대로 충전하거나 다음 점으로 이동할 정도로만 충전하면 된다는 관찰을 하고 DP를 돌려주면 된다.\

BOJ 17523 Choreography

계절학교에 나온 문제이다.

nmk솔이 나온 쉬운 문제이다.

BOJ 20039 Coronavirus Trend

계절학교에 나온 문제이다.

대충 세그 디피를 하면 된다.

이 문제도 nmk솔이 나온 쉬운 문제이다.

BOJ 23575 Squid Game

좀 재미있었던 문제이다. IMO Short List에 있다고 한다.

문제를 풀 때는 log X번의 연산을 통해 a, b, c 중 최솟값을 절반 이상 줄이는 것을 목표로 하면 된다.

일반성을 잃지 않고, a<b<c라고 가정하자.

b=aq+r(0<=r<a)라고 하자.

i) r<=a/2인 경우

여기서 q를 이진표현하자.

q의 마지막 자리가 0이면 a, c에 연산을 진행하고, q의 마지막 자리가 1이면 a, b에 연산을 진행하자.

이렇게 하면 r을 남길 수 있다.

ii) r>a/2인 경우

b=a(q+1)+r-a라고 하고 비슷하게 진행하면 r 대신 a-r이 남아서 절반 이상 줄어든다.

BOJ 21795 Worst Reporter 4

큰작을 잘 해주면 된다.

사이클 처리가 좀 귀찮다.

BOJ 17670 난

각 사람에 대해 n등분 지점을 구하고, 그 지점이 앞에 있는 사람부터 그리디하게 매칭하면 된다.

BOJ 17149 TENIS

어떤 x가 절대 이기지 못하는 선수가 존재할 필요충분조건은 모든 코트에서 x보다 잘 보는 적폐 순열이 존재하는 것이다.

이는 레이지로 잘 처리해줄 수 있다.

BOJ 10716 코딩 대회

답으로 이분 탐색을 하자.

답이 x이상이 가능한지 확인하기 위해 모든 수를 x 이상이면 1, x 미만이면 0으로 만들자.

여기서 배열을 트리로 펴고 DP를 해주면 된다.

1/17(금)  - 23일차

선발고사 전날이라 따로 셋을 돌지는 않았고, 점검해야 할 알고리즘의 웰논 다이아 5 문제들을 좀 뽑아서 풀었다.

이 날 푼 건 다 자력이었다.

BOJ 1739 도로 정비하기

대충 2-SAT 문제.

BOJ 15333 Black or White

대충 덱 디피 문제.

BOJ 18799 이상한 편집기

대충 해시 이분탐색 + DP + Slope Trick(?) 문제. 꽤 재미있었다.

BOJ 23836 어떤 우유의 배달목록

대충 HLD 문제.

BOJ 14460 소가 길을 건너간 이유 12

대충 분할정복 + 세그 스위핑 문제.

BOJ 17526 Star Trek

대충 CHT 문제. 난 리차오 박았다.

BOJ 27510 택시 여행

대충 센트로이드 트리 + CHT 문제. 분명 지난번에 풀 때는 정말 어렵게 풀었던 것 같은데 다시 보니까 쉽더라.

1/18(토) - 24일차

1차 선발고사를 봤다.

 

 

이 글을 끊고 내일부터는 새로운 글로 갈아타려고 한다.