오늘의 PS (22) - 220815~21

블로그를 너무 방치해 둔 것 같아 오늘의 PS 글을 하루에 하나는 아니더라도, 일주일에 하나 정도는 써보려고 한다. UCPC가 끝난 이후부터는 개인 PS 공부를 정말 거의 하지 않아서 쓸 내용이 없었지만, 그래도 이번주부터는 뭐라도 해보려고 한다. SCPC 대비도 해야 하고.. 이번주에는 백준에서 셋 2개정도를 풀고, 코포 1번과 앳코더 2번을 쳤다. 코포는 2번이 더 있었으나 노느라 치지 못했고, 앳코더는 두 번 모두 쳤다.

 

BOJ

화요일에는 동아리 연습용 셋으로 던져 놓은 2021 IUPC 를 풀었다. 마지막 문제 빼고는 모두 화요일에 풀었고, 마지막 문제는 귀찮아서 미루다가 오늘 풀었다.

 

23080 스키테일 암호

브론즈 문제이다. 잘 구현해주면 된다.

 

23081 오델로

실버 구현 문제인데, 제한이 작아 널널한 풀이를 짜도 잘 돌아간다. 무난한 구현 문제인 것 같다.

 

23082 균형 삼진법

머리를 잘 써줘야 하는 문제이다. 이런 문제에 익숙하다면 구현을 깔끔하게 할 수 있으나, 아니라면 좀 복잡한 방법으로 해결해야 하는 것 같다.

 

23083 꿀벌 승연이

재미도 감동도 없는 DAG DP 문제이다. 이런 육각 격자 모양의 문제가 종종 있는데, 개인적으로는 별로 좋아하지 않는다. 교육적으로는 괜찮은 문제인 것 같다.

 

23084 IUPC와 비밀번호

코포식 문자열 애드혹 문제다. 슬라이딩 윈도우 등으로 구간의 알파벳 등장 횟수를 잘 관리해주어야 하며, 한 문자를 랜덤으로 바꾼 것과 동치인 조건이 무엇일지 잘 생각해보면 문제를 해결할 수 있다.

 

23085 판치기

개인적으로 이 셋에서 가장 마음에 들었던 문제이다. 앞면인 동전의 수를 정점으로, 뒤집는 것을 간선으로 생각하면 간선의 개수가 \(O(N^2)\)정도인 그래프로 모델링해 BFS 한 번으로 문제를 해결할 수 있다. 깔끔하고 좋은 문제인 것 같다.

 

23086 두 반으로 나누기

파라메트릭 또는 역으로 간선 붙이기의 두 가지 풀이가 있다. 무지성으로 짜기는 파라메트릭이 더 쉬우나 나는 후자의 방법을 사용하였다.

 

23087 최단최단경로

각 정점에 대한 길이를 (길이, 쓴 간선 개수)로 저장해주고 다익스트라를 돌리면 잘 된다. 이 문제 역시 고인물이 볼 때는 노잼 웰노운이지만 교육적으로는 괜찮은 문제인 것 같다.

 

23088 Aging

뭔가 어려운 규칙이 적혀 있다. 이를 잘 구현해주면 되는데, 이런 문제에 약해 애를 좀 먹었다. 구조체에 비교 연산자를 정의하고 pq를 사용해주면 구현 자체는 크게 어렵지 않다.

 

23089 사탕나무

재미있는 트리 DP 문제이다. 풀이는 여러 가지가 있는 것 같은데, 나는 구현을 비효율적으로 해서 실행 시간이 상당히 길다.

 

23090 난민

웰노운 두 개를 합쳐 놓은 문제이다. 두 웰노운을 모두 알면 쉽게 문제를 해결할 수 있다.

 

23091 Calculate! 3

이 셋의 대장 문제이다. 뭔가 많이 본 것 같은 쿼리를 처리해야 한다. 우선, 경로에 대한 XOR은 루트에서 각 정점에 이르는 경로를 XOR한 두 값을 XOR한 것과 같다는 사실을 이용하면 각 수의 등장 횟수의 곱으로 경로의 개수를 세어줄 수 있다. 다행히도, 각 정점에 있을 수 있는 값이 최대 31이다. 따라서 각 수의 등장 횟수를 관리하는 세그먼트 트리를 만들어 이에 Lazy Propagation을 잘 적용해주면 된다.

 

총평

교육적으로 좋은 셋이지만, 지나치게 웰노운인 문제 (난민, 꿀벌 승연이) 와 제한이 풀이의 핵심인 문제 (사탕나무, Calculate! 3) 들이 조금 있긴 했다. 전자는 사실 쉽고 깔끔한 문제를 만들기 위해서 가장 좋은 선택이라 교내대회에서는 어쩔 수 없는 것 같고, 후자는 나쁘다는 것은 아니지만 내가 그냥 개인적으로 별로 좋아하지 않는다. 

 

 

화요일 이후에는 틈틈이 2022 ICPC Sinchon Winter Algorithm Camp (초급, 중급) 셋을 풀었다. 아직 한 문제를 풀지 않은 상태인데, 해당 문제는 푼 후 풀이를 추가하도록 하겠다. 

 

24510 시간복잡도를 배운 도도

잘 구현해주자. B4급인데 solved.ac 패치 이후의 기여가 아직 적어 B2인 것 같다.

 

24509 상품의 주인은

정렬을 해도 되고, 그냥 4번 돌며 최댓값을 찾아도 된다. 나는 귀찮아서 뇌 비우고 정렬 4번 했다.

 

24511 queuestack

각 자료구조의 크기가 1이기에 stack은 무시해도 되고, queue는 가지고 있던 값을 뱉는다. 이를 생각한 후 예제 입력을 통해 정답을 유추해보자.

 

24512, 24519 Bottleneck Travelling Salesman Problem (Small, Large)

제목과 제한에서 TSP 문제라는 사실을 깨달을 수 있다. 비슷하게 구현해주면 된다. 역추적이 있어 조금 더 까다롭긴 하다.

 

24513 좀비 바이러스

적절한 BFS 변형 문제이다. 문제에서 요구하는 점들을 모두 유의하면서 구현해주면 된다.

 

24514 n번째 숫자 찾기

꽤 머리와 손을 써야 하는 파라메트릭 문제이다. 난 꽤 어렵다고 생각했는데 제한이 작아 쉬운 풀이들이 존재하는 것 같다.

 

24515 히히 못가

갓문제다. 다른 알고리즘을 어설프게 알고 있다면 독이 될 수 있다. 이거 때문에 시간제한도 상당히 빡세게 잡혀 있는 것 같다. 구현이 꽤 복잡하긴 한데, 풀이가 상당히 기발하기 때문에 난이도에 영향을 줄 정도는 아닌 것 같다.

 

24516 잘 알려진 수열 구하기

오픈컨 당시에 풀어서 자세히 기억은 나지 않지만, 대충 될 것 같은 답을 몇 개 찍어보면 될 것 같다.

 

24518 잘 알려진 합 구하기

서로 다른 몫의 개수가 \(sqrt(N)\)개라는 것은 말 그대로 잘 알려져 있다. 뒤 부분을 잘 계산해주면 되는데, 이 부분 케이스 워크가 꽤 귀찮다. 나도 많이 틀린 후 틀린 것 같은 부분을 대충 찍어서 고쳤더니 맞았다.

 

24517 카드 게임과 쿼리

\(K\)의 제한이 매우 작기 때문에 대충 상상 가능한 DP 테이블을 모두 만들어서 돌릴 수 있다. 나는 \(K^3 2^K\) 정도 되는 테이블을 전처리로 만들었다. \(DP[a][b][bit]\)를 \(K=a\)이고, \(b\)만큼을 더 추가해야하며 현재 사용한 카드의 상태가 \(bit\)일 때의 선공의 승리 여부로 정의해주면 된다.

 

24520 Meet In The Middle

Meet In The Middle 문제는 아니고, 전형적인 LCA 문제이다. 이런 문제에서는 LCA를 넘기는 경로를 처리하기가 상당히 귀찮은데, 이 문제에서는 머리를 잘 쓰면 이를 잘 해결해줄 수 있다.

 

24521 스네이크 게임

갓문제.. 까지는 아니더라도 좋은 KMP 연습문제이다. 각 모양을 좌회전, 우회전, 특정 길이만큼 직진으로 바꾸어주면 KMP를 적용할 수 있다. 다만 생각해야 할 부분이 두 가지 정도 있어 이를 잘 처리해주면 된다.

 

24522 토지 구입

플로우같이 생겼다. 해결 후 코멘트 추가 예정

 

총평

Camp Contest의 취지에 맞는 좋은 문제들인 것 같다. 다만 중급의 난이도가 좀 맵다는 생각이 들었다. PS 잘하는 사람이 참 많다..

 

 

Codeforces Round #814 (Div. 1)

화요일 밤에 친 코포이다. 또 퍼플에 갈 뻔 했다. 한동안 Div. 1이 없는데, 이게 다행인지 불행인지는 모르겠다.

 

A. Burenka and Traditions (00:47, +1)

A1을 좀 보다가 별로 발전 가능한 풀이를 찾지 못해 A2를 한번에 풀기로 했다. 우선 Cost의 성질 때문에  길이가 1 또는 2인 연산만을 사용해도 됨을 알 수 있다. 이를 간파하면 Map DP 같은 것으로 문제를 해결할 수 있는데, 더 간단한 그리디적 방법으로도 잘 되는 것 같다.

 

B. Fibonacci Strings (1:40, +5)

잘 써보다 보면 대충 그리디하게 배분해주는 것이 최적임을 알 수 있다. 이를 PQ 등으로 구현하는 방법이 있고 나처럼 멍청하게 모든 수를 분해한 후 등장 횟수를 잘 세주는 방법이 있다. 이 때, 1+2+5=8과 같이 홀수번째 피보나치 수는 이하의 짝수번째 피보나치 수들로 분해할 수 있음을 고려해주어야 한다. 나는 게다가 멍청한 오타 하나를 30분간 찾지 못해 5번이나 틀렸다.

 

 

AtCoder

 

AtCoder Regular Contest 146

A. Three Cards (0:06, +1) *159

그리디하게 정렬을 해주고 앞 세 수를 차례대로 붙인 후 제출을 하면 틀리다는 것을 알 수 있다. 이 경우 111 22 3과 같이 수의 길이들이 다를 때 문제가 생긴다. 따라서 6가지 경우를 다 봐준 후 제일 큰 값을 출력하면 된다.

 

B. Plus and AND (0:36, +1) *1335

큰 비트부터 봐주면서 만들 수 있으면 만드는 것을 반복하면 된다. 말은 쉽지만, 구현이 꽤 까다롭다. 정렬과 이분탐색을 잘 이용해주면 구현할 수 있다.

 

C. Even XOR *2428

1시간 넘게 이 문제만 생각했는데 벽느끼고 GG쳤다. 너무 어렵다.

 

 

AtCoder Beginner Contest 265

A. Apple (0:01, +) *18

무지성 DP

 

B. Explore (0:04, +) *152

하라는 대로 구현해주면 된다.

 

C. Belt Conveyor (0:08, +) *212

하라는 대로 구현해주면 된다 2. DFS 하듯이 사이클을 판별해주면 된다.

 

D. Iroha and Haiku (0:14, +1) *727

각 \(x\)에 대해 \(y, z, w\)를 이분 탐색으로 찾아주면 된다.

 

E. Warp (0:35, +) *1531

\(DP[i][j][k]\)를 각 연산을 \(i, j, k\)번 썼을 때의 경우의 수로 정의하자. 각 경우에 대한 도착점 좌표는 잘 계산해줄 수 있다. DP 전이식은 도달 가능한 점일 시 \(DP[i][j][k]=DP[i-1][j][k]+DP[i][j-1][k]+DP[i][j][k-1]\)이고, 불가능한 점일 시 0이다. 시간 복잡도는 \(O(N^3)\)이다. 

 

F. Manhattan Cafe (1:30, +) *2290

\(DP[i][a][b]\)를 \(i\)번 인덱스까지 보았을 때 \(p\)와의 거리 차이가 \(a\), \(q\)와의 거리 차이가 \(b\)인 경우로 정의하자. 각 원소가 될 수 있는 값이 -2000~2000이므로 이를 돌며 DP값을 갱신해주면 \(O(ND^3)\)의 시간복잡도가 나온다. 정해에 도달하기 위해서는 여기서 D를 하나 떼주어야 한다. DP값이 갱신되는 형태를 잘 보면 대각선 범위의 값을 각 DP값에 더해주어야 한다는 점을 알 수 있다. 따라서, DP값의 우상향, 우하향 대각선 누적합을 만들어주면 \(O(ND^2)\)에 문제를 해결할 수 있다. 메모리는 토글링을 사용하면 \(O(D^2)\)만 사용해도 된다.

 

 

앳코더 총평

 

앳코더를 약 1달만에 쳤는데, ARC는 여전히 어렵고 D 이후로는 푸는 것이 불가능에 가까워 풀 문제가 너무 없다. ABC는 내 성향이랑 잘 맞아 칠 때마다 등수는 잘 나오는데, 크게 의미 있는 지표는 아닌 것 같다. ARC 또는 Div. 1 버츄얼을 돌아야 할 것 같다.