leo020630의 블로그

매우 유명한 문제이다. 당연히 좋은 풀이글도 많고 다양한 풀이가 존재하지만, 좋은 문제라 정리하는 것이 의미가 있을 것 같아 따로 정리해본다. 더불어, LIS를 \(O(NlogN)\)으로 해결하는 방법에 대한 튜토리얼 글들을 보면 원리를 제대로 설명하지 않은 글들이 많아 이를 정확히 설명하고, 이 문제의 해법까지 이어가는 것이 이 글의 목표이다. 문제 요약 서로 다른 양의 정수로 이루어진 \(2 \times N\) 또는 \(3 \times N\) 행렬이 주어질 때, 각 행에서의 등수가 같도록 뽑을 수 있는 열의 최대 개수를 구하시오. 풀이 가장 윗 행을 기준으로 정렬하고 나면 \(M = 2\)인 경우 LIS (Longest Increasing Sequence), \(M = 3\)인 경우 Pair LIS ..

문제 요약 정점 \(N \leq 1000\) 개로 이루어진 트리가 있을 때, 루트를 제외한 정점 \(K \leq 100\)개를 선택해 순서대로 방문할 것이다. 이 때, 정점 간 이동은 항상 최단거리로 진행한다. 정점 \(K\)개와 순서를 잘 정해 이동거리의 합이 최대가 되게 하여라. 풀이 문제 조건이 독특해 약간 헤멨다. 우선, 제한이 적으므로 \(dp[v][i]\)를 \(v\)번 정점을 루트로 하는 서브트리에서 \(i\)개를 선택해 나올 수 있는 최적해로 정의하자. 이제 각 정점에서 해야 할 일은 자식 노드들의 DP값을 잘 합쳐주는 것이다. 이는 \(dp[v][i]\)를 \(dp[v][j]\)와 \(dp[c][i-j]\)로 분해해서 생각해주면 된다. 두 값은 이미 정해져 있으니 더해주어야 할 값은 두 ..

HeeJaYaa님의 추천으로 Class 9 문제들을 풀고 있다. Class 9 문제들은 인터넷에 풀이가 많지 않은 경우가 꽤 있어 푸는대로 풀이를 작성해보려 한다. 원래 어제부터 풀고 싶던 문제는 https://www.acmicpc.net/problem/9244 인데, 하루동안 생각해도 모르겠어서 넘어왔다. 혹시 저 문제 푸신 분 있으면 힌트 부탁드립니다.. 문제 요약 숫자로 이루어진 문자열이 주어질 때, 다음과 같은 두 쿼리를 처리해야 한다. 1번 쿼리 : 구간 \([l, r]\)에 위치한 숫자 \(x\)를 모두 \(y\)로 바꾼다. 2번 쿼리 : 구간 \([l,r]\)을 읽은 수를 998244353으로 나눈 나머지를 출력한다. 풀이 일단 업데이트 쿼리가 없다고 생각해보자. 그러면 세그트리의 각 노드에..

동방에서 혼자 Class 9 문제들을 보고 있었는데 선배들이 막고라를 신청해 팀 아닌 팀 연습을 하게 되었다. 그 시간에 팀 연습을 하는게 낫지 않나.. 라는 생각도 있었지만, 재밌을 것 같아 하기로 했다. 셋은 2021 KCPC를 사용하였다. https://www.acmicpc.net/category/detail/2881 https://www.acmicpc.net/category/detail/2882 팀 연습이 아니기 때문에, 그냥 내가 푼 순서대로 문제별 후기를 적도록 하겠다. 23758 - 중앙값 제거 (실제 대회 2C-1A, 위 스코어보드에서는 B, S1) 구현 문제처럼 생겼지만, 직접 구현하면 TLE를 받는다. 해당 연산을 반복하면 중앙값 앞의 수들만 바뀌기 때문에, 해당 수들에 대해 2로 몇 ..

가장 빡센 과목을 드랍하고, 알고리즘+이산수학을 듣는 학기라 이번 학기는 로드가 거의 없이 보내고 있다. 그렇기에 PS에 더 집중해야 하는데, 요즘은 정작 무슨 문제를 풀어야 하는지 모르겠다. 코포랑 앳코더는 웬만하면 있을 때마다 치긴 하는데, ICPC를 대비하기 위해서는 여기에 개인 공부도 더 해야 할 것 같다. 1) (미래까지 고려해도 아마 포스텍에서 제일 강할) 현재 팀 구성으로 나가는 마지막 대회이고 2) PS에서 포스텍의 지명도를 조금이나마 올리고 싶다는 목표도 있고 무엇보다도 3) 내가 2021 ICPC 본선, 2022 UCPC 본선, 2022 ICPC 예선 연속 0솔이라는 기록을 달리고 있기에 최대한 ICPC를 잘 치고 싶다는 목표가 있다. 그런데 뭘 해야하는지 모르겠다. 새로운 알고리즘을 ..

A. Equal Hamming Distances (0:04, +) *357 케이스를 나눠준 후 그리디하게 처리해주면 된다. 두 수가 같을 때는 무조건 0, 다를 때는 횟수를 잘 세며 최대한 0부터 써주면 된다. B. A < AP (0:19, +) *1333 앞에서부터 보면서 Union Find로 연결하며 개수를 잘 세면 되는데, 정해는 이렇게 복잡한 방법으로 할 필요 없이 대칭성을 이용하는 것이었다. C. 01 Game (0:48, +) *1940 케이스를 잘 분석해주면 각 상황에서의 그런디 수를 구할 수 있다. 양 끝이 같은 수인 경우 1, 다른 수인 경우 0, 한쪽 끝이 막혀있는 경우 칸 수, 두 끝이 막혀있는 경우 칸 수의 홀짝성이 그런디 수가 된다. 그대로 스프라그 그런디 정리를 적용해주면 된다...

하루에 대회 3개를 쳤기 때문에 묶어서 정리하려고 한다. BOJ - 초콜릿컵 A. 초콜릿 피라미드 (0:12, +) 차분히 식정리를 해주면 된다. B. 초콜릿과 나이트 게임 (0:32, +) \(XY=0\)인 경우, \(X=Y\)인 경우, 그 외의 경우로 나뉜다. 앞 두 케이스는 7번, 뒤 케이스는 15번만에 게임을 끝낼 수 있다. 구현이 좀 귀찮은데, 난 그냥 cout을 29개 썼다. C. 예쁜 초콜릿과 숫자놀이 (1:51, +3) 제한이 애매하게 커서 완탐도 안될 것 같고(사실 된다), \(O(N^2 MOD)\) DP는 생각이 나지 않아 그냥 \(O(N^3 MOD)\) DP에 비트셋을 박았다. 왠지는 모르겠지만 실행시간 1등이다. 비트셋 최고 D. 초콜릿 나눠 팔기 (2:09, +) 케이스를 나누면 ..

셋 : https://www.acmicpc.net/category/detail/1978 내가 뒤, qjatn0120 선배가 앞, slah007 선배가 가운데를 보고 시작했다. ~1:05 나는 I, slah007 선배는 E, qjatn0120 선배는 A를 보고 시작했다. I를 딱 봤는데, 내가 PPC에 낸 신기한 숫자 문제와 상황이 거의 똑같았다. 그래서 바로 짰는데, TLE를 받고 전문 분야인 아호코라식을 잡은 qjan0120 선배에게 키보드를 넘겼다. 허나 바로 되지는 않았고, 그래서 내 J와 qjatn0120 선배의 A가 번갈아서 코딩된 결과 1시간 쯤에 둘 모두 AC를 받았다. ~1:45 이후 I를 보다가, 에라토스테네스 체 두번+포함배제를 잘 쓰면 개수를 셀 수 있을 것 같았다. 그렇게 AC를 받..

A. Make A Equal to B (0:02, +2) 적당히 케이스워크를 잘 해주면 된다. 난 완전히 같을 때, 구성만 같을 때, 그렇지 않을 때로 분류하였다. B. Playing with GCD (0:42, +5) \(B_i\)는 \(lcm(A_{i-1}, A_i)\)일 때가 최적이다. 따라서 이를 만들어준 후 확인해주면 된다. 나는 이상하게 해서 많이 틀렸다. C. Good Subarrays (0:28, +1) 투포인터처럼 생각해주면서 잘 구현해주면 된다. C2는 좀 봤는데 모르겠어서 넘어갔다. D. Equal Binary Subsequences (0:55, +) 뭔가 어렵게 생긴 조건인데, 이게 Div. 2 D라는 것과 코포라는 점을 생각하며 가장 쉬운 풀이를 찾아보자. 똑같게 나눌 수 있는 가..

A. Continuous 1 (1:50, +7) *952 앳코더에서 뭐 이런게 나오지? 싶었다. 역시 나답게 케이스워크를 환상적으로 한 후 결국 1시간쯤에 B로 넘어갔다. B 풀고 난 후 돌아오니 반례가 보여 고쳐서 맞았다. B. Better Students Are Needed! (0:06, +) *1466 시간이 꽤 지나 풀이가 구체적으로 기억나진 않지만, 식 정리를 잘 하면 가능한 비율로 \(\lfloor \frac{B}{i} \rfloor\) 꼴만 봐도 되었던 것 같다. 저 꼴에서 나오는 서로 다른 수의 개수가 \(O(\sqrt{N})\)임은 이제 유명하다. A에서 1시간+a를 쓴 결과 블루로 다이빙했다.