leo020630의 블로그

꽤 오래 전부터 보던 문제인데, 도저히 모르겠어 태그를 까고 생각해보았다. 문제 요약 길 또는 장애물로 이루어진 격자가 주어진다. 이 때 장애물이나 시작, 끝 지점을 포함하지 않으면서 시작점에서 끝점으로 가는 경로를 차단하도록 설치할 수 있는 가장 작은 정사각형 장애물의 크기와 위치를 구하시오. 풀이 가는 경로가 벽으로 생각했을 때 잇는 경로로 바뀐다는 duality는 최근 여러 문제에서 등장한 바 있다. ICPC Sinchon Camp Contest에도 나왔고, 최근에는 코포에서도 한번 본 것 같다. 따라서, 이 문제에서도 같은 방법으로 접근해보자. 뭔가 '가장 작은' 정사각형의 크기를 구하는 것이므로 이분 탐색을 쓰고 싶지만, 그럴 수 없다. 조금만 생각해보면, 조건을 만족하는 장애물의 크기는 연속적..

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

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) 잘 생각..

매우 유명한 문제이다. 당연히 좋은 풀이글도 많고 다양한 풀이가 존재하지만, 좋은 문제라 정리하는 것이 의미가 있을 것 같아 따로 정리해본다. 더불어, 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으로 나눈 나머지를 출력한다. 풀이 일단 업데이트 쿼리가 없다고 생각해보자. 그러면 세그트리의 각 노드에..

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, +) 케이스를 나누면 ..

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를 쓴 결과 블루로 다이빙했다.