Red Army 1
안녕하세요, 반갑습니다. 소프트웨어 멤버십 블로그에 글을 쓰는 것은 처음이네요.
서울대학교의 Problem Solving 동아리 SNUPS에서 봄학기동안 열린 스터디 red army에서 선별한 문제 풀이를 연습하던 중, 재미있는 문제가 몇 개 있어 문제와 풀이, 그리고 풀이 코드를 소개하려 합니다. 모두 코드포스(https://codeforces.com/)에 수록된 문제이며, div1 C 정도의 난이도입니다.
Cutting Rectangle
Thinkoff Internship Warmup Round 2018 and Codeforces Round #475 Div.1의 C번입니다.
(https://codeforces.com/contest/963/problem/C)
가로 길이가 A, 세로 길이가 B인 직사각형이 하나 있습니다. 이 직사각형을 가로로 몇 번, 세로로 몇 번 잘랐습니다. 가로선 또는 세로선들의 간격이나, 자른 횟수는 알 수 없습니다. 하지만, 한 번 자를 때는 항상 처음부터 끝까지 잘랐다는 사실과, 결과물에서의 서로 다른 조각들의 크기와 개수만 알고 있습니다.
직사각형은 결과적으로 _n_개의 조각 묶음으로 표현됩니다. 각 조각 묶음은 가로 길이 $w_i$, 세로 길이 $w_i$, 그리고 개수 $c_i$로 나타나며, 동일한 조각은 항상 같은 묶음이고, 각 조각은 회전시키지 않은 형태만 고려합니다. _n_개의 조각 묶음에 대한 정보가 모두 주어지면, 원래 직사각형의 크기인 (A,B)가 될 수 있는 페어 (A,B)의 개수를 모두 구하면 됩니다. 이 때, (A,B)와 (B,A)는 A!=B라면 다른 페어입니다.
각 제한은 $n <= 2 * 10^5$, $1 <= w_i, h_i, c_i <= 10^{12}$ 입니다.
풀이
이 문제에서 중요한 포인트는, $h$가 서로 다른 조각 묶음들에 대해, $w$를 나열하였을 때 그 집합이 항상 동일해야 한다는 점입니다.
어떤 직사각형을 가로선 5개, 세로선 6개로 임의대로 잘라 위와 같은 모습이 되었다고 합시다.
이 때, 모든 잘린 행에 대해 해당 행에는 $w_1, w_2, w_3, w_4, w_5, w_6, w_7$이 순서대로 등장해야 합니다. 만약 h가 동일하여 묶여서 등장하는 그룹이 있다면(위 그림에서는 $h_1 == h_2$ 라고 가정합니다) 각 “개수”가 두 배가 될 뿐, $w$들이 순서대로 등장해야 한다는 점에는 변함이 없습니다.
이 문제에서 모든 묶음은 $w, h, c$로 표시되므로, $h$가 서로 다른 묶음에 대해 $w$들의 집합이 모두 일치하는지 확인합시다. 일치하지 않는다면, 그러한 결과를 내는 방법이 없으므로 답은 0입니다.
또한, $h$가 다른 서로 다른 묶음에 대해, $w$를 순서대로 모두 맞춰 놓았다면, 개수의 비율이 동일해야 합니다. 예를 들어, 위 그림에서 $w_2 == w_3, w_3 == w_4$라고 가정한다면, 모든 행에 대해 $w$와 $c$만 나열하였을 때, $w_1 = x, w_2 = 3x, w_5 = x, w_6 = x, w_7 = x$를 만족해야 합니다. 구성이 동일한지는 먼저 확인했으므로, 개수의 비율이 일치하는지만 다시 확인합시다. 마찬가지로, 일치하지 않는다면 불가능하므로 답이 0입니다.
개수의 비율까지 일치했다면, 이제 아래 그림을 봅시다.
위와 같은 경우, 서로 다른 묶음은 총 4가지, $(a,c,6), (a,d,9), (b,c,4), (b,d,6)$이 존재합니다. 높이가 같은 묶음끼리 묶어 놓고 $w$와 $c$만 표기할 경우, $h=a : (c,6), (d,9) / h=b : (c,4), (d,6)$ 으로 표현됩니다. 앞서 보았듯이, $w$의 집합이 $(c,d)$로 동일하며, 개수의 비율이 $2:3$으로 동일함을 알 수 있습니다. 위와 같이 배치하면, $(3a + 2b, 2c + 3d)$가 원래 직사각형의 크기가 됩니다. 이제 답이 나오는 원리는 알았습니다. 하지만 가능한 서로 다른 경우의 수를 모두 세어야 합니다.
만약 조건을 모두 만족한다면, 이러한 페어를 몇 개나 만들 수 있을까요?
위의 예제와 같은 그림에서는 $(3a+2b,2c+3d)$ 하나 뿐이지만, 답이 하나가 아닌 예시를 만들면 아래와 같습니다.
위 그림의 경우, 입력은 $(a,c,8), (a,d,16), (b,c,4), (b,d,8)$입니다. 보이는 바와 같이, $(2c+4d, 4a+2b)$가 답 중 하나가 됩니다. 다른 답은 어떻게 생겼을까요?
다른 답 하나는 이렇게 생겼습니다. 행에 $c$가 2개, $d$가 4개 있던 상황에서, 행에 $c$가 1개, $d$가 2개 있는 직사각형을 좌우로 붙인 모습으로 바꾼 형태입니다. 이 직사각형을 의미하는 페어는 $(c+2d, 8a+4b)$가 됩니다.
이 외에도, 반대로 시행하여 행에 $c$가 4개, $d$가 2개 있도록 하고, 열에는 $a$가 2개, $b$가 1개 있도록 하는 방식도 가능합니다. 상하로 긴 직사각형이 될 것입니다.
위 세 가지 외에는 답이 존재하지 않습니다. 따라서 위 케이스의 경우, a, b, c, d의 값과는 관계없이 항상 답이 3입니다.
이러한 변경이 한 번 일어나는 과정에서 추론할 수 있는 사실이 있습니다. 각 행에 대하여, 행을 분할하여 좌우로 늘어놓거나, 열을 분할하여 상하로 늘어놓는 방식으로 답의 페어를 만들 수 있습니다. 이런 작업을 좀 더 formal하게 말하면, 주어진 개수들을 모두 나눌 수 있는 어떤 정수 $g$를 고르고, $g$의 배수 단위로 행을 배치함으로써 서로 다른 원래 직사각형을 얻을 수 있습니다. 예를 들어 위 케이스에서는, $g=1 : (4c+8d,2a+b)$, $g=2 : (2c+4d,4a+2b)$, $g=3 : (c+2d,8a+4b)$과 같이 답을 구할 수 있습니다.
따라서, 만약 답이 0이 아니라면, 답은 주어진 모든 개수들의 최대공약수를 구한 뒤, 해당 최대공약수의 약수의 개수가 됩니다. 이 값은 커봐야 $10^{12}$이므로, $O(sqrt(10^{12}))$ 정도에 답을 계산할 수 있습니다.
소스 코드
코드 전문은 아래와 같습니다. 답이 0이 되는지를 먼저 판정하고, 0이 아니라면 주어진 모든 $c$들의 최대공약수에 대해 약수의 개수를 구해 답으로 출력합니다.
#include <stdio.h>
#include <assert.h>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
using namespace std;
typedef long long lli;
typedef pair<lli,lli> ip;
map<lli,vector<ip> > d;
lli gcd(lli a, lli b) {
return b?gcd(b,a%b):a;
}
int main() {
int n;
scanf("%d",&n);
lli cc=0;
for(int i=0;i<n;i++) {
lli w, h, c;
scanf("%lld %lld %lld",&w,&h,&c);
d[h].push_back(ip(w,c));
cc=gcd(cc,c);
}
vector<ip> prev;
for(map<lli,vector<ip> >::iterator it=d.begin();it!=d.end();it++) {
vector<ip>& v=it->second;
sort(v.begin(),v.end());
if(prev.empty()) prev=v;
else {
if(prev.size()!=v.size()) {
puts("0");
return 0;
}
for(int i=0;i<prev.size();i++) {
if(v[i].first!=prev[i].first) {
puts("0");
return 0;
}
}
}
}
lli g=prev[0].second;
for(int i=1;i<prev.size();i++) {
g=gcd(g,prev[i].second);
}
for(int i=0;i<prev.size();i++)
prev[i].second/=g;
for(map<lli,vector<ip> >::iterator it=d.begin();it!=d.end();it++) {
vector<ip>& v=it->second;
lli g=v[0].second;
for(int i=1;i<v.size();i++)
g=gcd(g,v[i].second);
for(int i=0;i<v.size();i++) {
if(v[i].second/g!=prev[i].second) {
puts("0");
return 0;
}
}
}
int res=0;
for(lli i=1;i*i<=cc;i++) {
if(cc%i==0) {
res++;
if(i*i!=cc) res++;
}
}
printf("%d\n",res);
return 0;
}
Freelancer’s Dreams
Codeforces Round #335 (Div.1)의 C번, (Div.2)의 E번입니다.
(https://codeforces.com/problemset/problem/605/C)
프리랜서 한 명이 돈과 경험을 쌓으려 합니다. 프리랜서가 만족하기 위해서는 최소 $P$의 돈과 $Q$의 경험이 필요합니다.
프리랜서가 할 수 있는 일은 $n$가지가 있습니다. 각 일은 이 일을 했을 때 1초당 얻을 수 있는 돈의 양 $p_i$와 1초당 얻을 수 있는 경험의 양 $q_i$로 표시됩니다. 프리랜서는 한 순간에 하나의 일만 할 수 있으며, 각 일을 꼭 정수 시간만큼 할 필요는 없습니다. 일한 시간에 비례하여 해당 일을 했을 때 얻을 수 있는 돈과 경험을 모두 얻게 됩니다.
프리랜서가 최적으로 일을 했을 때, 최소 $P$의 돈과 $Q$의 경험을 얻을 수 있는 가장 빠른 시간을 찾아야 합니다. 이 때, 정답과 절대/상대 오차가 $1e-6$ 이하인 경우 정답으로 인정합니다.
각 제한은 $1 <= n <= 10^5$, $1<= P, Q, p_i, q_i <= 10^6$입니다.
풀이
각 일을 실수 시간만큼 할 수 있다는 조건이, 정수 시간만큼 할 수 있는 것보다 더 쉬운 조건이라는 것을 캐치해야 합니다. 만약 일이 두 개, 즉 $n = 2$라면, 프리랜서가 1초동안 얻을 수 있는 모든 서로 다른 (돈,경험)의 집합은 어떻게 표현될까요?
이를 직관적으로 보는 가장 편한 방법은, 돈을 $x$축으로, 경험을 $y$으로 하여 좌표평면 위에 직접 그려 보는 것입니다. 각 일을 1초간 했을 때 얻을 수 있는 돈과 경험인 $(p_i,q_i)$를 좌표평면 위에 찍어 봅시다.
두 점의 위치가 위와 같다고 합시다. 두 점을 가로지르는 선분은 무엇일까요?
이 선분은 $ t * (p_1,q_1) + (1-t) * (p_2,q_2) $ 와 같은 방식으로 만들어집니다. 이 때, $ t + (1-t) = 1 $ 이므로, 두 개의 일을 1초간 적당히 나눠 했을 때 얻는 돈과 경험치의 총량이 바로 이 선분입니다. 만약 1초가 아니라 $t$초만큼 일을 진행한다면, 모든 점의 좌표를 $t$배하기만 하면 됩니다.
즉, $n=2$인 경우에는, 해당 선분이 영역 $x >= P, y >= Q$ 를 처음으로 지나게 하는 최소의 $t$값을 계산하면 되며, 이는 간단한 케이스 분류로 풀 수 있습니다.
여기서 놀랍게도, 점이 두 개를 넘어 $10^5$개가 되더라도 위의 풀이는 성립합니다. 좌표평면 위에 $n$개의 점이 있을 때, 원점을 시점으로, 각 점을 종점으로 하는 벡터들에 대해 계수의 합이 1이 되도록 선형결합한 벡터의 종점은, 결국 해당 점들을 포함하는 볼록 껍질의 경계 또는 내부에 놓이게 되기 때문입니다.
예시와 함께 설명하면, 위의 그림에서, 1번과 같은 결과를 얻기 위해서는 $(p_2,q_2)$에 해당하는 일만 진행하면 되며, 2번과 같은 결과는 모든 일을 1/5씩 하면 됩니다. 3번과 같은 결과는 $(p_4,q_4)$와 $(p_5,q_5)$를 반반씩 진행하면 됩니다.
이제 문제가 간략해졌습니다. 주어진 모든 일을 좌표평면에 plot한 후, 볼록 껍질을 구합니다. 각 점의 좌표를 $t$배하였을 때, 볼록 껍질과 영역 $ x >= P, y >= Q $의 교집합이 생기는 최소의 $t$를 구하면 됩니다. 이는 이분 탐색을 통해 $t$를 찾는 방식으로 쉽게 구할 수 있습니다.
단, 여기에서 주의할 점이 있습니다. 단순히 볼록 껍질이 점 $(P,Q)$를 포함하는지의 여부를 체크한다면 아래와 같은 반례가 생기게 됩니다.
위는 볼록 껍질이 점 $(P,Q)$를 포함하지 않지만, 영역 $x>=P, y>=Q$와는 교집합이 있는 경우입니다. 위와 같은 경우를 처리하기 위해, 어떤 점 $(a,b)$를 볼록 껍질이 포함한다면, $x$좌표가 $a$ 이하이며, $y$좌표가 $b$ 이하인 모든 영역 또한 포함하는 것으로 생각합시다. 문제에 비추어 생각하면, 돈과 경험을 의도적으로 덜 받는 행위이며, 이는 답에 영향을 미치지 않습니다. 이를 그림으로 표현하면 아래와 같습니다.
볼록 껍질에 대해, $x$좌표가 가장 큰 점을 기준으로 $x$축에 수선을 내리고, $y$좌표가 가장 큰 점을 기준으로 $y$축에 수선을 내린 형태입니다. 이와 같은 작업은 $(max(x),0), (0,max(y)), (0,0)$을 원래의 점 집합에 포함시킨 뒤 볼록 껍질을 구함으로써 쉽게 처리할 수 있습니다. 이 이후에는, 단순히 볼록 껍질이 점 $(P,Q)$를 포함하는지를 체크하는 것만으로 답을 판정할 수 있게 됩니다.
매번 이분 탐색을 할 때마다 볼록 껍질을 만들면 시간복잡도가 $O(nlognlogt)$ 가 되어 시간 초과를 받게 됩니다. 모든 점을 $t$배한 후의 볼록 껍질은, 볼록 껍질을 구한 뒤 모든 점을 $t$배하는 것과 동일하다는 점을 이용해, 볼록 껍질은 한 번만 구한 후, 해당 볼록 껍질을 이분 탐색 내에서 항상 사용하는 방식으로 시간복잡도를 $O(nlogn + nlogt)$로 줄일 수 있으며, 여기까지 구현하면 정답을 받을 수 있습니다.
소스 코드
위와 같은 방식으로 정답을 받은 소스 코드는 아래와 같습니다.
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define INF 1e9
class p {
public:
double x, y, d;
p()
{}
p(double x, double y)
:x(x), y(y)
{}
};
bool cmp(const p &i, const p &j) {
if (i.d != j.d) return i.d < j.d;
else if (i.y != j.y) return i.y < j.y;
else return i.x < j.x;
}
bool ccw(p a, p b, p k) {
double d = (a.x*b.y + b.x*k.y + k.x*a.y) - (a.x*k.y + b.x*a.y + k.x*b.y);
return d > 0.0;
}
bool in(vector<p>& v, double t, p a) {
for (int i = 0; i < v.size(); i++) {
int j = (i + 1) % v.size();
if (!ccw(p(v[i].x*t, v[i].y*t), p(v[j].x*t, v[j].y*t), a)) return false;
}
return true;
}
double P, Q;
p a[100000];
int n;
int main() {
scanf("%d %lf %lf", &n, &P, &Q);
for (int i = 0; i < n; i++)
scanf("%lf %lf", &a[i].x, &a[i].y);
vector<p> v;
double x = -1e9, y = -1e9;
for (int i = 0; i < n; i++) {
v.push_back(a[i]);
x = max(x, a[i].x); y = max(y, a[i].y);
}
v.push_back(p(x, 0)); v.push_back(p(0, y)); v.push_back(p(0, 0));
sort(v.begin(), v.end(), [](const p& i, const p& j) {
if (i.y != j.y) return i.y < j.y;
else return i.x < j.x;
});
for (int i = 1; i < v.size(); i++) {
if (v[i].x == v[0].x) v[i].d = INF;
else {
v[i].d = (v[i].y - v[0].y) / (v[i].x - v[0].x);
if (v[i].d < 0) v[i].d += 2.0*INF;
}
}
v[0].d = -INF;
sort(v.begin(), v.end(), cmp);
vector<p> conv;
conv.push_back(v[0]); conv.push_back(v[1]);
for (int i = 2; i < v.size(); i++) {
while (conv.size() >= 2 && !ccw(conv[conv.size() - 2], conv.back(), v[i])) conv.pop_back();
conv.push_back(v[i]);
}
double lo = 0.0, hi = 2e6 + 1e-3;
for (int it = 0; it < 60; it++) {
double mid = (lo + hi) / 2.0;
if (in(conv, mid, p(P, Q))) hi = mid;
else lo = mid;
}
printf("%.10f\n", hi);
return 0;
}
A Simple Task
마지막으로는, 간략하고 짧은 구현 연습 문제를 가져왔습니다. Codeforces Round #312 (Div.2)의 E번입니다.
(https://codeforces.com/problemset/problem/558/E)
문제 제목처럼, 문제가 굉장히 짧습니다.
알파벳 소문자 $n$글자로 이루어진 문자열 $S$가 있습니다. 다음의 두 질의를 $q$번 처리해야 합니다.
- 0 i j : 문자열의 [i,j] 구간을 오름차순으로 정렬
- 1 i j : 문자열의 [i,j] 구간을 내림차순으로 정렬
모든 질의가 끝난 후, 문자열 $S$의 상태를 한 줄에 출력하면 됩니다.
제약 조건은 $1 <= n <= 10^5, 0 <= q <= 50000$입니다.
풀이
우선, 문자열이 바이너리 스트링(0과 1만으로 이루어진 문자열)이라고 가정하면, 이 문제를 풀 수 있을까요?
간단히 풀 수 있습니다. 합을 계산할 세그먼트 트리를 두 개 만들고, 구간 내의 0의 개수와 1의 개수를 따로 저장하도록 합니다. [i,j] 구간을 오름차순으로 정렬해야 한다면, 구간 내의 0의 개수와 1의 개수를 구한 뒤, [i,i+cnt(0)-1]은 0으로 덮어씌우고, [i+cnt(0),j] 구간은 1로 덮어씌우면 됩니다. 즉, 구간 대입과 합 연산을 지원하는 세그먼트 트리가 있다면, 바이너리 스트링에 대해서 쉽게 문제를 풀 수 있습니다.
이는 매우 쉽게 일반화가 됩니다. 원본 문자열이 알파벳 소문자로만 이루어졌다면, 위와 같은 작업을 26번 하면 됩니다. [a-z]에 대해 각각 개수를 구하고, 그 개수만큼 구간 내에 차례대로 덮어씌우는 작업을 거치면 각 질의를 $O(26qlogn)$에 처리할 수 있습니다.
이 문제에서 중요한 점은, 풀이가 아닌 구현입니다. 구간 대입 연산과 구간 합 연산을 모두 지원하는 세그먼트 트리를 실수 없이 구현할 수 있다면 쉬운 문제이지만, 그렇지 않다면 시행착오가 있을 수 있는 문제입니다.
소스 코드
아래는 제가 구현한 소스 코드입니다.
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int bt[26][1 << 18], buf[26][1 << 18], sz = 1, n;
int s[1 << 18], e[1 << 18];
char p[100001];
void maketree(int* bt, int l, int r) {
if (l + 1 == r) return;
for (int i = l; i < r; i += 2) {
bt[i / 2] = bt[i] + bt[i + 1];
s[i / 2] = s[i];
e[i / 2] = e[i + 1];
}
maketree(bt, l / 2, r / 2);
}
void upd(int* bt, int* buf, int cur, int l, int r, int w) {
if (s[cur] > r || e[cur] < l) return;
if (s[cur] == l && e[cur] == r) {
buf[cur] = w;
bt[cur] = (r - l + 1)*w;
cur >>= 1;
while (cur) {
if (buf[cur * 2] >= 0) bt[cur * 2] = buf[cur * 2] * (e[cur * 2] - s[cur * 2] + 1);
if (buf[cur * 2 + 1] >= 0) bt[cur * 2 + 1] = buf[cur * 2 + 1] * (e[cur * 2 + 1] - s[cur * 2 + 1] + 1);
bt[cur] = bt[cur * 2] + bt[cur * 2 + 1];
cur >>= 1;
}
return;
}
if (buf[cur] >= 0) {
bt[cur] = (e[cur] - s[cur] + 1)*buf[cur];
buf[cur * 2] = buf[cur];
buf[cur * 2 + 1] = buf[cur];
buf[cur] = -1;
}
upd(bt, buf, cur * 2, l, min(e[cur * 2], r), w);
upd(bt, buf, cur * 2 + 1, max(s[cur * 2 + 1], l), r, w);
}
int qry(int* bt, int* buf, int cur, int l, int r) {
if (s[cur] > r || e[cur] < l) return 0;
if (buf[cur] >= 0) {
bt[cur] = (e[cur] - s[cur] + 1)*buf[cur];
if (cur * 2 < sz * 2) buf[cur * 2] = buf[cur];
if (cur * 2 + 1 < sz * 2) buf[cur * 2 + 1] = buf[cur];
buf[cur] = -1;
}
if (s[cur] == l && e[cur] == r) return bt[cur];
return qry(bt, buf, cur * 2, l, min(e[cur * 2], r)) + qry(bt, buf, cur * 2 + 1, max(s[cur * 2 + 1], l), r);
}
char res[100001];
int main() {
int q;
scanf("%d %d %s", &n, &q, p);
while (sz < n) sz *= 2;
for (int i = 0; i < n; i++)
bt[p[i] - 'a'][sz + i] = 1;
memset(buf, -1, sizeof(buf));
for (int i = sz; i < sz * 2; i++)
s[i] = e[i] = i;
for (int i = 0; i < 26; i++) maketree(bt[i], sz, sz * 2);
int c[26];
while (q--) {
int l, r, k;
scanf("%d %d %d", &l, &r, &k);
l--; r--;
for (int i = 0; i < 26; i++)
c[i] = qry(bt[i], buf[i], 1, sz + l, sz + r);
int sum = 0;
for (int i = (k ? 0 : 25); (k ? i < 26 : i >= 0); (k ? i++ : i--)) {
if (c[i] == 0) continue;
upd(bt[i], buf[i], 1, sz + l, sz + r, 0);
upd(bt[i], buf[i], 1, sz + l + sum, sz + l + sum + c[i] - 1, 1);
sum += c[i];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < 26; j++) if (qry(bt[j], buf[j], 1, sz + i, sz + i)) {
res[i] = j + 'a';
break;
}
}
puts(res);
return 0;
}
구현의 방식에는 여러 가지가 있을 수 있지만, 저는 전역에 26개의 트리를 만든 뒤, 포인터를 이용해 접근하는 방식을 사용하였습니다. 구간 대입이 가능한 합 트리의 구현은 upd 함수에서 볼 수 있습니다. 구간에 어떤 값이 대입되는 것을, 26개의 트리 중 하나에 대해 해당 구간에 1이 메워지는 것으로 계산하는 방식입니다. 구간을 갱신한 뒤, 부모 노드를 타고 올라가며 업데이트된 구간을 포함하는 모든 부모 구간에 대한 합을 재계산해줍니다.
마무리
모든 문제에 대한 링크를 따로 모아보았습니다.
- Cutting Rectangle : https://codeforces.com/contest/963/problem/C
- Freelancer’s Dreams : https://codeforces.com/problemset/problem/605/C
- A Simple Task : https://codeforces.com/problemset/problem/558/E
감사합니다.