매주 일요일마다 푼 문제를 정리하려고 한다. 언제까지 갈 진 모르겠다.
2/1 : KOI 문제 하나가 끌려서 잡아서 풀었고, 계절학교 문제 출처 찾아다니다가 P2 1개, D3 1개를 날먹했다.
solved.ac 티어
20240201 기준 : Platinum II (μ = P2 - 0.24, σ = 0.45)
알고리즘 분류
solved.ac : dp, prefix_sum
작성자 풀이 : dp, prefix_sum (dp최적화용)
풀이
제한을 보니 DP인데 DP 식을 세우기에 꽤 까다로워 보인다. 뭐든 간에 관찰을 해서 단순화시켜야 할 것 같다.
먼저 구간(L~R)에 대한 dp식을 세울 지 1~i에 대한 dp식을 세울 지 생각해 봤다. 현재 보고 있는 칸에 쌓을 블록 개수를 고정하면서 앞에서부터 누적하면서 남은 블록(음수면 그만큼 부족) 값을 관리할 수 있다는 사실을 관찰했고, 1~i에 대한 식을 세울 수 있었다.
dp[i][j][k+offset] : 현재 i번 위치이고 바로 이전 높이가 L+j였고 지금까지 누적된 값이 k일 때 가능한 최소 비용
offset은 음수 인덱스를 방지하기 위한 것이다. 이때 k의 범위가 아무리 잘 봐줘도 10^9기 때문에 이 식을 바로 적용하기에는 무리가 있다. 하지만 생각을 해보면, 어차피 모든 값은 L~R 사이여야 되기 때문에 L 미만인 값들을 L로 맞추는 비용, R 초과인 값들을 R로 맞추는 비용을 따로 생각해주면 k의 상태가 O((R-L)N)로 충분하다는 것을 알 수 있고, 이를 이용해 5제곱 정도 시간복잡도에 답을 구할 수 있고 이를 이용해 75점을 얻을 수 있다. 100점을 얻기 위해서는 k의 공간복잡도를 최적화해주고, 반복문을 하나 줄일 수 있다는 관찰을 필요로 한다.
MCO'23 Two Pointers (Hard Version)
겨울학교에 거의 유사한 문제가 있었다. (좌표 범위가 20만이었다)
solved.ac 티어
20240201 기준 : Platinum I (μ = P1 - 0.47, σ = 0.71) *기여 2개
알고리즘 분류
solved.ac : value_compression, dp, segtree (+ lazyprop)
작성자 풀이 : value_compression, dp, lazyprop
풀이
문제 자체는 KOI'03 경찰차인데 1차원에서 진행되고 N <= 3*10^5이다.
일단 경찰차랑 유사한 dp를 정의한다.
dp[i][j] : 1명이 i번, 다른 1명이 j번을 마지막으로 처리했을 때 최소 비용(i>j). 이때 시작지점도 event로 포함해서 구현하는게 편하다.
이는 O(N^2)에 계산할 수 있다. 이제 식을 뚫어져라 쳐다보면 좌표압축을 했을 때 lazy propagation으로 최적화할 수 있는 형태임을 알 수 있고, 3개의 세그를 이용해 O(Nlog10^9)에 열심히 계산해주면 된다. 기존 기여에는 lazy propagation이 없는 것으로 보아 좀 더 깔끔하게도 풀 수 있는 것 같다.
겨울학교 문제이다.
solved.ac 티어
20240201 기준 : Diamond III (μ = D3 + 0.24, σ = 0.73)
알고리즘 분류
solved.ac : dag, planar_graph, topological_sorting
작성자 풀이 : dag, topological_sorting, priority_queue(구현용)
풀이
x좌표가 우선되게 위상정렬을 한 번 해주고, y좌표가 우선되게 위상정렬을 한 번 해줬을 때 p, q 사이 관계가 똑같으면 TAK, 아니면 NIE이다.
라고 겨울학교에서 들었다. 증명은 잘 모르겠던데 기여창에 엄청난 코멘트가 있어서 대충 봤지만 역시 잘 모르겠다..
proof by ac하기 좋은 문제인 것 같다. 물론 실습때는 이상한 문제 때문에 보지도 않았다.
2/2 : KOI'22 주차 타워를 업솔빙하려다 실패했다. 또 oi 플랜디에서 나온 KOI'08 계통 트리를 많은 조건 분기로 풀려다가 많은 시간을 날렸다 :(
자력솔에 실패했다.
solved.ac 티어
20240202 기준 : Platinum I (μ = P1 - 0.44, σ = 0.84)
알고리즘 분류
solved.ac : ad_hoc, hashing graph
작성자 풀이 : ad_hoc, hashing, graph, sorting
풀이
일단 남들과 비슷하게 다음과 같은 관찰은 쉽게 했다.
두 정점 사이 거리가 2라는 것은, 자기 자신을 포함한 인접 리스트가 완전히 동일하다는 말과 동치이다.
계통 트리에서 생각해보면 거리가 2라는 것은 부모 노드가 같다는 말이 되고, 그 이후에 나타나는 모든 정점 사이 거리가 같아지게 된다. 따라서 위 사실이 참임을 알 수 있다.
그래서 일단 인접리스트가 같은 애들끼리 묶어주고 시작한다. 이건 해싱이나 std::map 같은 걸로 할 수 있다.
이 다음부터가 문제다. 이제 거리가 3인 것만 잘 판단해주면 되는데, 여기서 너무 복잡하게 생각한게 문제였다.
복잡하게 생각했던 이유는 크게 2가지였던 것 같다.
1. 생각하던 풀이가 부모-자식 관계를 중요하게 생각하는 방향이었어서, 간선을 이을 때 너무 많은 케이스를 고려하게 된다. (쉽게 말하면 무방향인데 방향처럼 생각했다)
2. 내가 멍청하다. 1번 때문에 수많은 케이스가 생겼고 이 풀이를 버릴 생각을 안했다. -> 더 꼬인다.
아무튼 복잡하게 생각할 필요 없이, 그냥 입력으로 주어진 그래프에서 연결되어 있는데 거리가 2가 아니라면 3이므로, 그냥 묶어주면 된다...
풀이를 알고 정당성에 대해 생각해보니까 당연하다... 왜 안될 거라고 생각한걸까.
트리 같은 것들은 전략이 직감적으로 확신이 안들어서 이런 문제 풀 때 더 고생하는 것 같다.
2/3 : 일단 KOI'23 지그재그를 업솔빙했다. 그 뒤에 골랜디를 몇개 돌렸는데 유익하진 않아서 생략.
중등부 4번, 고등부 2번이었다. 고등부는 2번, 3번 난이도가 역전된 것으로 유명하다.
solved.ac 티어
20240203 기준 : Platinum I (μ = P1 + 0.14, σ = 0.57)
알고리즘 분류
solved.ac : combinatorics, tree_set
작성자 풀이 : combinatorics, tree_set(BBST)
풀이
O(N^3)까지는 dp로 어떻게 할 수 있다. 그 풀이는 아마 이 글에 있을텐데 설명이 부족하다.
O(N^2)은 앞 서브태스크와는 전혀 다른 풀이로 접근해야 한다.
g(x) 각각을 빠르게 구하는 방법을 고려하자. 이를 위해서 더블 카운팅 비슷한 것을 할 것인데, 모든 f(x,y,z)의 가장 긴 지그재그 부분수열의 길이를 구해서 더하는 것이 아니라, x 이하의 원소들 중 각각이 가능한 모든 f(x,*,*)의 답에 몇 번 들어가는 지를 세줄 것이다. 그런데 어떤 f(x,y,z)는 가장 긴 지그재그 부분 수열이 여러 개일 수 있으므로 일단 가능한 답을 하나로 고정하자. 이를 위해서는 f(x,y,z)의 답을 구성하는 법을 알아야 한다. 그 중 하나는 다음과 같다.
1. 앞에서부터 가능한(x 이하인) 모든 원소를 순서대로 넣는다.
2. 넣다가 지그재그 수열이 아니게 될 경우, 마지막 3개의 원소가 순서대로 a,b,c일 때 a<b<c 또는 a>b>c이므로 a를 없앤다. b,c를 없애는 것보다 a를 없애는 것이 이득임을 증명할 수 있다.
f(x,y,z)의 답이 위 방식으로 만들어진다고 하자. 그럼 A[i] <= x인 i가 세지는 횟수는 다음과 같이 구할 수 있다.
1.i가 포함되는 모든 f(x,*,*)의 답에 i에 포함된다고 생각하고 답에 i * (n-i+1)을 더해준다.
2.i가 포함되지 않는 경우를 빼준다. 이는 A[i]가 구성 과정에서 사라지는 경우이다. A[j] <= x, A[k] <= x이면서 i<j<k이면서 최소인 두 인덱스 j,k에 대하여(다시 말해 i,j,k는 A에서 x 이하인 원소만 남겼을 때 인접하다) A[i], A[j]의 대소 관계와 A[j], A[k]의 대소 관계가 같다면 A[i]는 답에 포함되지 않을 수 있다. 그러한 f(x,*,*)의 개수는 i * (n-k+1)임을 알 수 있으며 답에서 이만큼을 빼준다.
이제 A[i] <= x인 모든 원소에 대하여 답을 구하면 g(x)를 O(N)에 구할 수 있으며 O(N^2)에 문제를 해결할 수 있다.
//이해를 위해 g(i)를 구하는 코드를 첨부한다.
typedef long long ll;
typdef pair<ll,ll> P;
#define X first
#define Y second
ll g(ll x){
vector<P> v;
for(int i = 1 ; i <= n ; i++){ //v에는 a[i] <= x인 원소만 있다.
if(a[i] <= x)v.push_back({i,a[i]});
}
ll ret=0;
for(int i = 0 ; i < v.size() ; i++){
ret += v[i].X * (n-v[i].X+1);
if(i+2 < v.size() and (v[i].Y < v[i+1].Y) == (v[i+1].Y < v[i+2].Y))ret -= v[i].X * (n-v[i+2].X+1);
}
return ret;
}
이제 O(NlogN)은 간단하다. g(x)를 통해 g(x+1)을 구하면 된다. 이건 원소 추가 및 이로 인해 바뀌는 값들을 처리해주면 된다.
std::set 등으로 구현할 수 있다.
2/4 : solved.ac Grand Arena #4 (mirror of GA Party) — Division 2 · Arena #19를 G 제외하고 풀었다. div1은 대부분 div2에서 제한이 강화된 문제들인데 어려워서 구현이 다 만만치 않아 보여서 안 풀었다. 이후 월간 향유회 문제를 몇개 풀었다.
A,B번은 생략한다.
+4WA
solved.ac 티어
20240204 16:55:07 기준 : Gold III (μ = G3 + 0.14, σ = 0.71)
알고리즘 분류
solved.ac : simulation
작성자 풀이 : simulation
풀이
원래 visited[x][y][방향]을 관리하고 사이클 찾으면 마지막으로 먼지를 제거했을 때 이동 수를 출력하려 했으나 왜인지 모를 구현 미스로 그냥 2*(nm)^2번 시뮬레이션했다. 증명은 에디토리얼에 있다.
+2WA
solved.ac 티어
20240204 17:00:03 기준 : Gold III (μ = G3 + 0.18, σ = 0.40)
알고리즘 분류
solved.ac : polygon_area(다각형의 넓이), prefix_sum
작성자 풀이 : polygon_area, prefix_sum
풀이
일단 답이 존재한다는 건 자명하다. 꼭짓점 하나를 잡고 볼록다각형을 N-2개의 삼각형으로 쪼갠 뒤, 끝에서부터 보면서 누적 넓이가 전체의 절반이 넘는 시점을 찾으면 넓이 비를 이용해 내분점을 출력해주면 된다.
+3WA
solved.ac 티어
20240204 17:03:10 기준 : Gold II (μ = G2 - 0.44, σ = 0.53)
알고리즘 분류
solved.ac : dfs, data_structures
작성자 풀이 : dfs, stack
풀이
그냥 생각나는 대로 구현하면 된다. 대신 잘못 생각하면 좀 고생한다. 본인은 파일이 열려 있으면 그냥 바로 아래 자식으로 내려가고, 닫혀있으면 어디로 이동해야 되는지를 미리 구해놓은 후에 이동하면서 스택에 넣고, 커서가 위로 갈 때 스택을 빼면서 구현했다
좋은 문제라고 생각한다.
solved.ac 티어
20240204 17:08:20 기준 : Platinum V (μ = P5 + 0.00, σ = 0.71)
알고리즘 분류
solved.ac : greedy, sorting, parametric_search
작성자 풀이 : greedy, sorting, parametric_search, prefix_sum
풀이
일반적인 그리디 솔루션이 잘 보이지 않는다. 결정 문제를 고려하자.
f(x) : x대 이상이 전기를 공급받을 수 있는가?
결정 문제를 바꿨을 때 쉬워진 점을 생각해보자. 원하는 대로 아무렇게나 x개를 골라서 이들만 잘 넣으면 된다. 그러므로 가장 넣기 쉬운 x개를 골라보자. D[i]가 큰 순서대로 x개를 고르는 것이 이득임을 알 수 있다.
이제 이 x개를 어떻게 채울 지 생각해보자. 먼저 멀티탭은 동시에 고려하자. 즉 멀티탭을 0개 거친 경우, 1개 거친 경우, ... 를 순서대로 고려하자. D[i] = k인 기기는 멀티탭을 0~k개 거친 경우 중 하나에 들어가야 하므로 k+1개 거친 경우 전까지 자리가 확보되어야 한다. 이를 모든 기기에 대해 고려하면 "언제까지 얼마 만큼의 공간을 확보해야 한다" 라는 정보를 알려주는 배열을 얻을 수 있다. 이를 P라고 하자. (P는 누적 합으로 쉽게 얻을 수 있다)
이제 이 배열에 맞춰서 그리디하게 멀티탭을 연결해보자. 먼저 A[i]가 큰 멀티탭부터 쓰는 것이 이득이라는 사실을 알 수 있다. 그러므로 순간순간마다 공간에 여유가 있고 멀티탭이 남았다면 항상 멀티탭을 꽃아주자. (여유가 있다는 것은 P 배열에서 확보해야 할 공간을 다 고려했을 때 공간이 남아있다는 것이다.) 이것이 최적임을 알 수 있으며, 이 때 x대를 모두 꽃을 수 있는 지에 따라 true/false를 반환하면 이분 탐색을 통해 문제를 해결할 수 있다.
solved.ac 티어
20240204 17:20:57 기준 : Gold I (μ = G1 + 0.08, σ = 0.27)
알고리즘 분류
solved.ac : math (to proof time complexity)
작성자 풀이 : segment tree + binary search
작성자 풀이
어떤 곰곰이가 처음으로 귤을 딸 수 없게 되면, 이후로도 계속 딸 수 없게 된다. 이는 요세푸스 문제와 유사하며 비슷하게 생각해볼 수 있다.
생각해보면, 누군진 모르지만 누군가가 처음으로 딸 수 없게 되는 턴으로 바로 이동할 수 있다. 그건 바로 (남아있는 A[i]들 합) > m인 경우 m에서 합을 빼고 다음 턴으로 넘길 수 있다. 즉, m을 m mod (남아있는 A[i]들 합)으로 생각할 수 있다. 이 상태에서는 누군진 모르지만 일단 누군가가 빠지게 된다는 사실을 알 수 있다. 이때 사라지는 한 곰곰이를 O(N)보다 빠르게 어떻게 찾을 수 있다면 문제를 풀 수 있을 것 같다. (곰곰이가 N명이므로 찾는 데에 O(T)가 걸린다면 O(NT)에 문제를 해결할 수 있다.) 이 때 현재 상태에서 "귤을 따지 못하는 가장 왼쪽 위치"를 이분 탐색으로 구하고, 이 위치를 제거하는 전략을 생각해볼 수 있다. 이는 이분 탐색 + 세그먼트 트리로 해결할 수 있으며 세그먼트 트리이므로 삭제까지 바로 처리할 수 있다. 세그 이분 탐색 시 O(NlogN), 그냥 이분 탐색 + 세그 시 O(Nlog^2N)이다. (이 시간 복잡도가 정확한진 모르겠다)
공식 풀이
위 풀이에서 m을 m mod (남아있는 A[i]들 합)으로 생각할 수 있다는 사실을 알았다. 이 말은 즉, 고려해야 할 m이 O(logm)개 라는 것이다. 즉 그냥 O(logm)번을 O(N)에 시뮬레이션하면 된다.. 시간 복잡도는 O(NlogM)이다.
맞왜틀로 디버깅 고생 좀 했다.
solved.ac 티어
20240204 20:07:15 기준 : Diamond V (μ = D5 - 0.38, σ = 0.52)
알고리즘 분류
solved.ac : dp_bitfield, game_theory
작성자 풀이 : dp_bitfield, game_theory
풀이
N <= 150에 주목하자. 또한 1을 제외하면 같은 수는 1번만 고를 수 있으므로 M <= 10^5는 원소가 1일때만 의미가 있다는 사실을 생각하고 시작하자.
서로소는 항상 소인수분해 했을 때 지수보다는 소인수 집합에 더 의미를 둬야 한다. 150까지의 소수의 개수는 35개이며, 이 중 75 이하는 21개이다. 75 초과는 골라도 상관 없는 "조커" 처럼 취급할 수 있다. 또한 1도 조커로 취급할 수 있다.
따라서 21개의 소수만 생각해주면 되는데, 앞서 말했듯이 집합 개념에서 생각해보면 2^21개의 서로 다른 집합과 조커 카드 개수의 기우성을 상태로 가지는 bitmask dp를 생각해줄 수 있다.
즉 dp[i][j] := 현재 bitmask 집합 상태가 i이고, 조커 카드의 기우성이 j일 때 현재 턴이 이기는가? 로 정의하고 구현하면 된다. 이 때 각 수를 미리 소인수분해 해놓는 것이 편하며, 소인수 집합이 같은 값 끼리는 하나 빼고 없애놓는 것이 편하다.
그 외에도 구현에 고려할 만한 케이스 몇 가지가 있다.
1이 여러개인 경우
같은 값인 75 초과의 소수가 여러개인 경우
인덱스 처리
등등 때문에 많이 고생했다.
