leo020630의 블로그

시험기간 탓에 멈춰 있던 Class 9 밀기를 다시 시작했다. 그 동안도 몇 개 푼 문제가 있긴 한데, 좋은 풀이가 많길래 굳이 올리지 않았다. 문제 요약 무방향 그래프가 주어진다. 이 때, 어느 간선을 제거해도 그래프가 하나의 컴포넌트가 되기 위해 추가해야 하는 간선의 최소 개수를 구하고 실례를 구성하시오. 풀이 우선, 제거했을 때 그래프가 나누어지는 간선은 단절선이다. 따라서 단절선이 아닌 간선들은 두 정점을 union한다고 생각하고 그래프를 구성하면 트리가 된다. 단절선만 남긴 그래프이니 이는 당연하다. 단절선을 구할 때 멀티 에지가 들어오는 것만 조심하면 된다. 이제 트리에서 최소한의 간선을 추가해 잘 이어주는 것이 남았다. 개수는 대충 생각해보면 \(\lceil \frac{l}{2} \rceil..

검수진 모집 글이 있길래 무지성으로 넣었더니 되었다. 아쉬웠던 점은, 시험기간과 제대로 겹쳐 시간을 많이 투자하진 못했던 것 같다. 그래도 오픈 전까지는 모든 문제에 AC 코드를 만들어 넣긴 했다. 대회 링크 : https://www.acmicpc.net/category/detail/3214 문제별 후기 A. 안녕 클레오파트라 세상에서 제일가는 포테이토 A번이다. A번답고 좋다. B. 장인은 도구를 탓하지 않는다 검수할 때는 \(N=10\)인거 보고 무지성 완전탐색을 짰는데, 그냥 최솟값 빼고 다 곱하면 되는 것 같다. C. 수렵의 시간이다! 하라는 대로 열심히 짜면 된다. 구현 문제는 짤 때마다 정말 화가 나는데, 티어를 높게 주지 못하는 점이 너무 아쉽다. D. 양과 늑대 멋진 인터랙티브 문제이다. ..

A. Factorise N+M (0:00, +) 홀수면 3, 짝수면 2를 출력하면 된다. B. Jumbo Extra Cheese 2 (0:05, +) 둘 중 작은 쪽을 가로로 쓰는게 항상 이득이고, 세로는 정렬한 모양으로 쓰는 것이 이득이다. 증명은 잘 모르겠다. C. Bricks and Bags (0:16, +) 한쪽 끝에 2개빼고 다 넣고, 남은 2개에 하나씩 넣는게 최적이다. 역시 증명은 잘 모르겠다. 이름이 헷갈려서 해석이 오래 걸렸다. 그냥 Alice Bob 쓰면 될 것을.. D. Knowledge Cards (0:40, +1) 새 카드를 꺼낸 후 보드에 빈 자리가 하나라도 있으면 잘 옮겨줄 수 있다. 구현을 이상하게 해서 1번 틀렸다. E. Hanging Hearts (1:02,+1) 잘 생각..

셋 : https://www.acmicpc.net/category/detail/1840 내가 가운데, qjatn0120 선배가 뒤, slah007 선배가 앞 보고 시작했다. ~0:12 난 E, qjatn0120선배는 H를 보고 있었는데 slah007 선배가 A가 쉬운 것 같은데 해석을 못 하겠다 하셔서 가서 봤다. 다 읽으니 진짜 쉬워서 금방 짜서 맞았다. ~0:22 이후 slah007 선배가 쉬운 C를 짜서 맞았다. ~1:17 E를 qjatn0120 선배가 보겠다 하셔서 난 G로 넘어갔다. 기하 식 정리를 좀 해야 해서 시간이 걸렸는데, 다 짜서 내니 WA를 받았다. 그 후 컴퓨터를 넘겨 slah007 선배가 B를 짜서 맞았다. ~1:27 G에서 빠진 부분을 찾아 AC. ~1:55 내가 G를 짜는 동안..

매우 유명한 문제이다. 당연히 좋은 풀이글도 많고 다양한 풀이가 존재하지만, 좋은 문제라 정리하는 것이 의미가 있을 것 같아 따로 정리해본다. 더불어, 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, 한쪽 끝이 막혀있는 경우 칸 수, 두 끝이 막혀있는 경우 칸 수의 홀짝성이 그런디 수가 된다. 그대로 스프라그 그런디 정리를 적용해주면 된다...