오늘의 PS (27) - 231226-240101

써야지 써야지 하다가 밀려서 그냥 1주일동안 한 것을 정리한다.

 

USACO 2023 December Contest (12/26~29)

Bronze

 

1. Candy Cane Feast *G3

 

쭉 순회하며 사탕을 먹이는 정상적인 \(O(N)\) 과정을 거치면 가장 앞 사탕은 적어도 길이가 2배가 됨을 알 수 있다. 따라서 이러한 과정은 최대 \(logX\)번 일어나고, 그 이상부터는 반드시 첫 사탕 선에서 막힌다.

 

2. Cowntact Tracing 2 *G3

 

우선 시키는 대로 1 덩어리들로 묶어준 후, 가장 작은 덩어리에 맞춰주자. 이 때 양 쪽 끝에 붙은 덩어리에 유의해야 한다.

 

3. Farmer John Actually Farms *G2

 

순서를 strict하게 잘 정해주어야 하므로 정렬된 결과에서 인접한 직선끼리만 봐 주어도 된다. 그러면 조건을 만족하는 영역이 각 쌍마다 반직선 형태로 구해지는데, 이 반직선들의 교집합을 구하면 된다.

 

Silver

 

1. Bovine Acrobatics *G2

 

큰 소부터 보면서 잘 쌓아주면 된다. 정확히는 이미 쌓인 소 탑의 꼭대기 무게와 개수를 pair로 관리하며 존재하는 탑 중 나보다 \(K\) 이상 무거운 탑이 있다면 그 탑을 최대한 이용해 쌓아주면 된다. 각 무게에 대해 나를 모두 쓰는 연산은 최대 1번 일어나고, 각 무게에 대해 어떤 탑을 모두 쓰지 못하는 연산 역시 최대 1번이라 시간 내에 잘 동작한다. 다만 구현도 set에 익숙하지 않다면 어렵고, 시간 복잡도를 보이는 것도 테크니컬하다고 생각한다.

 

2. Cycle Correspondence *G2

 

둘 모두에서 등장하지 않는 번호는 반드시 가능하다. 둘 중 하나에서만 등장하는 번호는 반드시 불가능하다. 둘 모두에서 등장하는 번호는 다이얼을 돌리는 느낌으로 최대한 잘 맞춰주어야 하는데, 등장 순서의 차이를 저장해 가장 많이 등장하는 값의 등장 횟수를 더해주면 된다. 순서가 뒤집힐 수도 있음에 유의하자.

 

3. Target Practice *P4

 

문제에서 요구하는 것을 하면 된다. 이 과정에서 다량의 케이스 워크와 누적합 배열이 필요하였다. 자세한 설명은 생략한다.

 

Gold

 

1. Flight Routes *G2

 

인덱스 차이가 적은 것부터 보며 \(O(N^3)\) DP로 해결해주면 된다. 상수도 작고 사용하는 연산도 비트 레벨이라 시간 안에 충분히 돈다. bitset을 사용할 수도 있을 것 같은데 그렇게 나오지 않아 다행이다.

 

2. Minimum Longest Trip *P1

 

쉽지 않은 문제였다. 처음으로 생각해낸 것은 각 state의 이전 state를 저장해 sparse table처럼 관리하는 것이었다. 여기에 해싱을 끼얹으면 하라는 대로 할 수야 있을 것 같은데, 정해가 아닌 것 같아 조금 더 생각해보기로 했다. 우선, longest path 중에서만 찾으라는 것이 꽤 좋은 조건이었다. Route에 대한 사전순 비교를 해야 하는 정점 그룹이 정해져 있다는 뜻이기 때문이다. 각 정점 그룹은 같은 longest path 길이를 가진다. 이러한 그룹끼리 묶어 놓으면, 이 그룹들의 이전 정점 역시 모두 같은 그룹이므로 여기서의 정렬 결과를 활용해 각 정점의 사전 순 순서를 정할 수 있다. 따라서 위상 정렬을 할 때 pq등을 이용해 longest path 길이가 적은 정점부터 진행하며, 한 그룹에 대한 처리가 모두 끝나면 사전순 우열 관계를 정해주는 식으로 구현하면 된다.

 

3. Haybale Distribution *P4

 

이러한 꼴의 함수는 Convex함이 널리 알려져 있으니 삼분탐색을 사용하였다.

 

USACO 문제는 대체적으로 퀄리티가 굉장히 좋고, 문제가 Unknown함을 추구한다. 내가 생각하는 좋은 문제의 정의에도 대체로 부합하고, USACO 같은 문제를 잘 푸는 것이 약간 PS 실력의 진리에 가깝다는 생각도 들어서 열심히 연습해 볼 예정이다.

 

SciOI 2023 Open Contest · Arena #16 (12/30)

 

 

 

A-1. 비 오는 날 (0:10, +1) *S4

 

BFS를 돌릴까도 생각했지만, A번이라 조금 더 생각해보았다. 적절한 그리디 전략으로 시뮬레이션해주면 된다. 코너 케이스를 이상하게 처리해 한 번 틀렸다.

 

A-2. 다오의 경주 대회 (0:12, +) *B1

 

A1보다 좀 더 짧고 티피컬한 유형이라 바로 풀었다.

 

A-3. 균형 잡힌 등급 (0:39, +) *P5

 

우선 몇 가지 자명한 생각을 했다. 그룹을 나눌 수 있는 지점의 후보들이 있고, 하나를 고정하고 뒤에서 하나를 고르면 된다. 뒤에서 하나를 고르는 방법이 중요한데, 가운데를 고르면 된다는 반 쯤의 확신이 있었지만 증명을 하고 싶어 짜지 않았다. 결국 잘 모르겠어서 조금 더 확실한 삼분탐색을 갈겼다. 아마 코포였으면 그냥 짰을 것 같다.

 

B-1. 라면 배달하기 (1:00,+) *P3

 

전형적인 아이디어 몇 개를 쓰면 풀린다. 더블 카운팅, 그리고 돌아오는 거리에 대한 처리를 잘 해주자. 대충 ABC E번쯤에 있을 법한 문제다. 크게 어렵지는 않았다.

 

C-1. 카탈란 게임 (2:16, +3) *P3

 

B1이 ABC에 있을 것 같이 생겼다면, C1은 ARC에 있을 것처럼 생겼다. 우선 간단한 생각을 통해 문자열 길이가 짝수일 때는 후공이 무조건 이긴다는 것을 알아내었다. 홀수일 때가 문제인데, 가운데를 포함하는 2개의 길이 2인 substring 중 하나라도 ()라면 선공이 무조건 이긴다는 추측을 하였다. 이는 맞는 얘기지만, 필요충분조건은 아니었다. 이 생각에 꽤 매몰되어 있다가 가운데를 포함한 문자열이 RBS여도 선공이 이긴다는 것을 발견해내었다. 맞을 것 같다는 강한 확신이 들어서 바로 짰더니 맞았다. RBS 판별은 생각하기 귀찮아 \(O(1)\) RMQ Sparse Table을 박았다.

 

이후 컨디션도 좋지 않고, 여러 개의 브루트 포스 코드로 연명하기는 싫어서 그냥 10점만 긁고 쉬었다.

 

Good Bye 2023 (12/30)

 

A. 2023 (0:03, +) *800

 

잘 구현해주면 된다. 프리텟이 약하다는 이슈가 있었던 것 같다.

 

B. Two Divisors (-1) *900

 

식 하나로 깔끔하게 끝낼 수 있는데, 지능 이슈로 \(T\) 제한도 확인하지 않고 \(O(\sqrt{N})\) 의 멍청한 풀이를 짰다가 터졌다. 덕분에 레이팅을 50점 정도 날려먹었다.

 

C. Training Before the Olympiad (0:21, +) *1200

 

지금까지 등장한 홀수 개수에 따라 전체 합에서 조금 빠진다는 것을 알 수 있다. 자세한 식은 대충 몇 개 해보면 알 수 있다.

D. Mathematical Problem (0:31, +) *1700

 

이런 문제에서는 브루트 포스를 짜는 것이 옳다는 사실을 여러 번의 성공 경험으로 인해 학습했다. 짜고 대충 쉬운 방법 골라서 냈다.

 

E. Happy Life in University (1:11, +2) *2300

 

일단 스투라를 방향으로 잡았는데 뭔가 잘 되지 않았다. 더 생각해 보니 ETT랑 레이지도 있어야 할 것 같아서 그냥 다 박아서 풀었다. 새 색이 칠해질 때 1을 더하되, 내 밑 가장 최근의 같은 색에는 동시에 -1을 하는 식으로 구현하면 된다. 다만 스투라는 필요 없었다고 한다. 2번 틀린 것은 스투라인데 크기를 비교하고 swap하는 if문을 넣지 않아서 TLE를 받았다. 정말 정신이 제대로 나갔음을 체감할 수 있었다.

 

F는 낮에 본 아레나 A4번 하위호환 같았고, H1은 사람들이 많이 풀어서 구글링을 열심히 했으나 별 소득을 얻지 못했다. 두 가설 모두 참임이 밝혀졌고, 이 라운드는 전설이 되었다. 역사상 최고. 

 

Good Bye, BOJ 2023! (12/31)

 

A. 2023은 무엇이 특별할까? (0:01, +) *B4

 

짜면 된다.

 

B. 거짓말 (0:05, +) *G5

 

해외 리저널에서 비슷한 문제를 본 적이 있어 풀이를 빨리 찾았다. 일단 거짓말하는 사람 수를 고정하면, 조건에 위배되는 사람 수는 이분탐색이나 누적합으로 구할 수 있다.

 

C. 스티커 재배치 (1:13, +6) *G1

 

약간의 그리디가 포함된 구현 문제다. 쓰레기 문제라고 열심히 욕하면서 짜서 많이 틀렸다. 이후 생각하던 것만큼의 쓰레기는 아니었고 쓰레기는 나라는 것을 깨달으며 고쳐서 풀었다. 아래는 내가 이 문제를 해결하는 과정에서 작성한 코드이다. useless code의 예시로 교과서에 들어가도 되지 않을까?

 

쓰레기같은 실수

 

D. 23E (1:50, +4) *P5

 

비슷한 문제를 ARC에서 몇 번 본 적이 있다. 결국 경우를 나누고 몇 가지 연산을 적절히 해 점수를 최대화해야 하는데, 우선순위를 잘 모르겠어서 대충 몇 개를 내 보았더니 다 틀렸다. 정말 모르겠어서 코드를 찬찬히 봤는데 복사 과정에서 if문 하나를 더 썼음을 깨달았다. 이 부분을 지웠더니 이전에 제출한 코드가 모두 맞았음을 확인할 수 있었다.

 

상술한 실수들로 인한 현타, 컨디션 난조, 온사이트 못감 등의 이유로 E, F는 포기했다. E는 Sparse Table 잘 굴리기 같았으며, F는 대충 제곱 DP 같았다. F는 업솔빙했고, E는 추후 진행 예정이다.

 

BOJ 문제 풀기 (1/1)

 

새해 목표인 연간 랭킹 1등을 위한 다수의 브/실 문제와 소수의 영양가 있는 문제를 풀었다. 후자만 리뷰해보도록 하겠다.

 

7577, 13271, 7040 (*D5, *P1, *P1)

 

System of Difference Constraints라고 부르는 테크닉이다. 옛날에 이 문제 에디토리얼을 보면서 갑자기 벨만포드 얘기가 나와서 신기했는데 2년만에 궁금증을 해결하였다. 재밌고 교육적인 내용인 것 같다.

 

1150 백업 (*D4)

 

PS 향유회에서 얘기가 나오길래 그냥 에일리언으로 슥삭했다. 정해도 알아둘 필요가 있어 보여서 공부를 하건 풀어보건 할 예정이다.

 

Codeforces Round 915 (Div. 2) (1/1, Virtual)

 

향유회 디코에서 IBory님과 kongum님이 하고 계시길래 따라 쳤다.

 

A. Constructive Problems (0:02, +) *800

 

좀 그려보니 \(max(n,m)\)이 답인 것 같아 내서 맞았다.

 

B. Begginer's Zelda (0:04, +) *1100

 

문제를 읽고 POSCAT 디스코드에서 스포당했던 문제임이 기억났다. B니까 처음 봤어도 어련히 짰겠지 싶어서 짜고 넘겼다.

 

C. Largest Subsequence (0:16, +) *1400

 

Substring으로 읽어서 좀 헤멨다. 우선 Largest Subsequence를 수동으로 구한 후, 해당하는 위치만 모아 뒤집자. 이 문자열이 곧 최종 문자열이다. 만약 이렇게 완성된 문자열이 정렬되어 있지 않으면 불가능하고, 아니면 가능하며 횟수는 해당 문자열의 길이에서 가장 큰 문자 갯수를 뺀 값이다.

 

D. Cyclic MEX (0:39, +) *2000

 

재밌는 문제였다. 야매 방법으로는 안 되고 정직하게 다 구해야 할 것 같은데, 적절한 방법이 빨리 떠오르지 않았다. 그러던 중 뭔가 우선 0을 오른쪽에 두고 왼쪽으로 한 칸씩 밀면 값이 단조적으로 잘 변한다는 사실을 캐치해 히스토그램과 비슷한 단조 스택으로 구현해 해결하였다. 

 

E. One-X (1:42, +) *2400

 

우선 대충 점화식이 \(f(x) = f(\lceil x \rceil) + f(\lfloor x \rfloor) \) 꼴인데, 이러한 경우 \(x\)가 홀수면 state 개수가 복사가 되어버리는 불상사가 발생한다. 이런 경우 한 state를 계산할 때 \(x\)와 \(x+1\)을 같이 들고 다니면 연속된 2개 값이 자식에서도 유지되어 불상사를 방지할 수 있다. 이 문제에서 배운 테크닉이다. 이제 해당 문제와 비슷하게 해결하면 되는데, 값 2개만으로는 뭔가 잘 되지 않아 각 깊이에 대한 경우의 수를 저장하는 vector를 state로 했다. 구현이 좀 길긴 했는데 예제가 친절해서 한 번에 맞을 수 있었다.

 

셋이 전반적으로 괜찮았고, F도 그러하여서 업솔빙 예정이다.