Welcome to booknu's Blog!

PS & Algorithm 공부, 테크 리뷰

코드포스 Educational Codeforces #66(Div.2) 리뷰

2019-06-06

booknu

PS_Codeforces

PS Codeforces 그리디 이분탐색

개요
A번
B번
C번
D번

개요

대부분의 코드포스 라운드처럼 이번 라운드도 그리디한 생각과 문제를 얼마나 잘 분석하는지가 중점인 라운드였다.

A번

A번 문제: 그리디

숫자가 주어지고, 각 단계마다 숫자에서 $1$을 빼거나, $k$로 나누어 떨어지면 나눌 수 있다.

숫자를 $0$으로 만들려면 최소 몇 단계를 거쳐야하나?

풀이 보기

$n$부터 시작해서 $0$이 될 때까지 다음을 반복한다,

$k$로 나눌 수 있을 때까지 뺀다. ($n - n \% k$)
$0$이 아니면 $k$로 나눈다.

한 단계마다 최소 $k$씩 나누어지므로 한 쿼리 당 시간복잡도는 $\log n$이다.

소스코드 보기

include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL_BOOKNU
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

// ........................macro.......................... //
#define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
#define pb push_back
#define emb emplace_back
#define fi first
#define se second
#define ENDL '\n'
#define sz(A) (int)(A).size()
#define ALL(A) A.begin(), A.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
#define next next9876
#define prev prev1234
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef long long i64;
typedef unsigned long long ui64;
// inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
const i64 MOD = 1e9+7;
inline i64 POW(i64 a, i64 n) {
	assert(0 <= n);
	i64 ret;
	for(ret = 1; n; a = a*a%MOD, n /= 2) { if(n%2) ret = ret*a%MOD; }
	return ret;
}
template <class T> ostream& operator<<(ostream& os, vector<T> v) {
	os << "[";
	int cnt = 0;
	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
	return os << "]";
}
template <class T> ostream& operator<<(ostream& os, set<T> v) {
	os << "[";
	int cnt = 0;
	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
	return os << "]";
}
template <class L, class R> ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
// ....................................................... //

i64 n, m;
void input() {
	cin >> n >> m;
}

int solve() {
	i64 ans = 0;
	while(n) {
		if(n%m != 0) {
			ans += n%m;
			n -= n%m;
		}
		if(n) {
			n /= m;
			++ans;
		}
	}
	cout << ans << ENDL;
	return 0;
}

// ................. main .................. //
void execute() {
	int tt; cin >> tt;
	while(tt--)
	input(), solve();
}

int main(void) {
#ifdef LOCAL_BOOKNU
	freopen("input.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
#endif
	cin.tie(0), ios_base::sync_with_stdio(false);
	execute();
	return 0;
}
// ......................................... //

B번

B번 문제: 그리디 구현

for n : $n$번 반복문
end : 가장 가까운 반복문 종료
add : $x$에 $1$을 더한다. 단, 덧셈 결과가 $2^{32}-1$보다 크면 오버플로가 발생한다.

위 3가지로 이루어진 코드가 있을 때, 코드 실행 후 $x$값을 출력하면 된다.

(단, 중간에 add연산 중 오버플로가 발생하면 OVERFLOW!!!를 출력한다.)

풀이 보기

구현이 은근히 까다로운 문제이다.

일단 기본적인 아이디어는 간단하다.

for n :스택을 통해 값을 계속 쌓아놓으며, 현재까지 쌓인 값의 곱들을 변수 $f$에 저장해두면 된다.
end : 스택 맨 마지막을 뺀 후, $f$에서 그 값을 나누면 된다.
add : $x$에 $f$를 더하면 된다.

구현에서 까다로운 점은, 중간에 $f$값 자체가 엄청나게 커질 수 있다는 것인데, 단순 계산으로는 최대 십진수로 $2 \cdot 10^{5}$ 자리수까지 커질 수 있어, BigInteger을 사용하더라도 그 연산 속도 때문에 시간 초과가 날 것이다.

또 까다로운 점이 $f$가 오버플로가 났다고 해서 답이 꼭 OVERFLOW!!!가 아니라 중간에 add만 이루어지지 않는다면 아무런 문제도 없다.

따라서 for n이 오버플로가 발생한 순간, 스택 포인터 변수에 오버플로가 발생한 변수의 포인터를 저장하고, 앞으로 for n문을 만나면 직접 $f$에 곱하지 않고 그냥 스택에만 쌓아두는 방식을 사용할 것이다.

또한 end를 통해 오버플로가 발생한 스택이 pop 된다면 그 때는 다시 스택 포인터 변수를 아무것도 가리키지 않는 상태로 둘 것이다.

만약 add 시 스택 포인터 변수가 무언가를 가리키고 있다면, 바로 OVERFLOW!!!를 출력하면 된다.

소스코드 보기

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL_BOOKNU
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

// ........................macro.......................... //
#define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
#define pb push_back
#define emb emplace_back
#define fi first
#define se second
#define ENDL '\n'
#define sz(A) (int)(A).size()
#define ALL(A) A.begin(), A.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
#define next next9876
#define prev prev1234
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef long long i64;
typedef unsigned long long ui64;
// inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
const i64 MOD = 0x7fffffffff;
inline i64 POW(i64 a, i64 n) {
	assert(0 <= n);
	i64 ret;
	for(ret = 1; n; a = a*a%MOD, n /= 2) { if(n%2) ret = ret*a%MOD; }
	return ret;
}
template <class T> ostream& operator<<(ostream& os, vector<T> v) {
	os << "[";
	int cnt = 0;
	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
	return os << "]";
}
template <class T> ostream& operator<<(ostream& os, set<T> v) {
	os << "[";
	int cnt = 0;
	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
	return os << "]";
}
template <class L, class R> ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
// ....................................................... //

i64 lp, n, lim;
void input() {
	cin >> lp;
}

int solve() {
	lim = POW(2, 32)-1;
	debug(lim);
	stack<int> sta;
	sta.push(1);
	i64 f = 1;
	int of = -1;
	while(lp--) {
		string t; cin >> t;
		if(t == "add") {
			n += f;
			if(of != -1 || n > lim) {
				cout << "OVERFLOW!!!" << ENDL;
				return 0;
			}
		} else if(t == "for") {
			i64 x; cin >> x;
			if(of == -1) {
				f *= x;
				sta.push(x);
				if(f > lim) of = sta.size();
			} else sta.push(x);
		} else {
			if(of == -1) {
				f /= sta.top();
				sta.pop();
			} else if(of == sta.size()) {
				f /= sta.top();
				sta.pop();
				of = -1;
			} else sta.pop();
		}
	}
	cout << n << ENDL;
	return 0;
}

// ................. main .................. //
void execute() {
	input(), solve();
}

int main(void) {
#ifdef LOCAL_BOOKNU
	freopen("input.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
#endif
	cin.tie(0), ios_base::sync_with_stdio(false);
	execute();
	return 0;
}
// ......................................... //

후기

구현이 좀 까다로워서 당황스러웠는데, 다행히 깔끔하게 처리해서 빠르게 넘어갈 수 있었다.

C번

C번 문제: 그리디

$x$축 위에 $n$개의 점 $x_i$들이 주어진다.

$x$축에서 아무 정수 좌표 $p$를 잡아 $d_i = abs(p - x_i)$들을 구했을 때 그 중 $k$번째로 작은 수를 최소화하고 싶다.

각 쿼리마다 죄표 $p$를 찾으면 된다.

풀이 보기

문제 자체가 겉으로 보기에는 상당히 복잡해보인다.

우선 $p$가 증가함에 따라 $f_k(p)$ 값이 1차 혹은 2차 함수 꼴이 되어 이분/삼분 탐색을 할 수 있나 살펴봤지만, 그런 특성은 없었다.

하지만 잘 살펴보니, $p$를 어디로 잡든 결국은 어느 두 점 $x_{i-1}, x_i$ 사이에 존재한다는 점을 알아냈다.

(물론 $x_1, x_n$ 바깥 쪽에 존재할 수 있지만, 그런 경우는 무조건 손해를 본다는 것을 쉽게 알 수 있다.)

이 때 $d_i$들은 항상 $p$를 기준으로 왼쪽, 오른쪽으로 연속된 $k$개의 점들이 선택된다는 것을 알 수 있다.

이것을 바꿔말하면, $[x_i…x_{i+k-1}]$들이 $p$를 기준으로 $d_1…d_k$가 될 수 있는 점들이라는 뜻이고, 결국 좌표들 중 연속된 $k$개 점들의 구간의 크기가 가장 작은 것의 중점을 $p$로 잡으면 $d_k$가 최소화 된다는 것을 알 수 있다.

소스코드 보기

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL_BOOKNU
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

// ........................macro.......................... //
#define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
#define pb push_back
#define emb emplace_back
#define fi first
#define se second
#define ENDL '\n'
#define sz(A) (int)(A).size()
#define ALL(A) A.begin(), A.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
#define next next9876
#define prev prev1234
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef long long i64;
typedef unsigned long long ui64;
// inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
const i64 MOD = 1e9+7;
inline i64 POW(i64 a, i64 n) {
	assert(0 <= n);
	i64 ret;
	for(ret = 1; n; a = a*a%MOD, n /= 2) { if(n%2) ret = ret*a%MOD; }
	return ret;
}
template <class T> ostream& operator<<(ostream& os, vector<T> v) {
	os << "[";
	int cnt = 0;
	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
	return os << "]";
}
template <class T> ostream& operator<<(ostream& os, set<T> v) {
	os << "[";
	int cnt = 0;
	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
	return os << "]";
}
template <class L, class R> ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
// ....................................................... //

const int MAXN = 2e5+10;
i64 n, k, ar[MAXN];
void input() {
	cin >> n >> k;
	FOR(i, 0, n) cin >> ar[i];
}

int solve() {
	i64 res = -1, cur = -1;
	FOR(i, 0, n-k) {
		if(res == -1 || cur > ar[i+k] - ar[i]) {
			res = i, cur = ar[i+k] - ar[i];
		}
	}
	cout << (ar[res+k] + ar[res]) / 2 << ENDL;
	return 0;
}

// ................. main .................. //
void execute() {
	int tt; cin >> tt;
	while(tt--)
	input(), solve();
}

int main(void) {
#ifdef LOCAL_BOOKNU
	freopen("input.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
#endif
	cin.tie(0), ios_base::sync_with_stdio(false);
	execute();
	return 0;
}
// ......................................... //

D번

D번 문제: 그리디 정렬

$n$개의 수로 이루어진 배열이 주어지고, 이것을 $k$개의 최소한 원소를 $1$개 이상씩 가지고 있는 연속된 부분 배열로 나누어야 한다.

(물론 모든 배열의 원소들은 정확히 하나의 부분 배열에 속해야 한다.)

이 때, $f(i)$를 $a_i$가 속한 부분 배열의 idx라고 할 때 $\sum\limits_{i=1}^n{a_i \cdot f(i)}$ 이 최대가 되도록 부분 배열들을 나누고, 그 값을 찾아야한다.

(부분 배열의 idx는 좌측부터 $1$부터 증가하는 순으로 부여된다.)

풀이 보기

우선 위의 식을 개념적으로 풀어서 이해하면, 일단 세그먼트 단위로 쪼갠 후, 각 세그먼트에 들어있는 원소들의 합에 세그먼트 idx를 곱한것들의 합을 구하는 것으로 바뀐다. 즉,

$\sum\limits_{i=1}^{k} i \cdot sum\_of\_seg(i)$

이것을 그림으로 나타내면 다음과 같다.

하지만 여기서 한 걸음 나아가 관찰 할 수 있는 중요한 사실이 있는데, 세그먼트의 idx는 $1$에서부터 증가한다는 것을 이용해 위의 식을 일종의 누적 합으로 표현할 수 있다.

$\sum\limits_{i=1}^{k} sum(a_{seg\_start}...a_n)$

즉, 다음 그림과 같은 형태다.

이것을 이용해 배열의 끝부분부터 시작하는 누적 합을 구해 우선 세그먼트 $1$은 배열의 전체를 커버하니까 따로 빼서 더하고, 나머지 누적합 중 큰 순으로 $k-1$개를 더하면 그게 바로 최대값이 된다.

소스코드 보기

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL_BOOKNU
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

// ........................macro.......................... //
#define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
#define pb push_back
#define emb emplace_back
#define fi first
#define se second
#define ENDL '\n'
#define sz(A) (int)(A).size()
#define ALL(A) A.begin(), A.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
#define next next9876
#define prev prev1234
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef long long i64;
typedef unsigned long long ui64;
// inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
const i64 MOD = 1e9+7;
inline i64 POW(i64 a, i64 n) {
	assert(0 <= n);
	i64 ret;
	for(ret = 1; n; a = a*a%MOD, n /= 2) { if(n%2) ret = ret*a%MOD; }
	return ret;
}
template <class T> ostream& operator<<(ostream& os, vector<T> v) {
	os << "[";
	int cnt = 0;
	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
	return os << "]";
}
template <class T> ostream& operator<<(ostream& os, set<T> v) {
	os << "[";
	int cnt = 0;
	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
	return os << "]";
}
template <class L, class R> ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
// ....................................................... //

const int MAXN = 3e5+10;
i64 n, k, ar[MAXN], ps[MAXN];
void input() {
	cin >> n >> k;
	RFOR(i, n-1, 0) cin >> ar[i];
}

int solve() {
	FOR(i, 0, n) ps[i] = (i ? ps[i-1] : 0) + ar[i];
	i64 ans = ps[n-1];
	sort(ps, ps + n - 1, greater<i64>());
	FOR(i, 0, k-1) ans += ps[i];
	cout << ans << ENDL;
	return 0;
}

// ................. main .................. //
void execute() {
	input(), solve();
}

int main(void) {
#ifdef LOCAL_BOOKNU
	freopen("input.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
#endif
	cin.tie(0), ios_base::sync_with_stdio(false);
	execute();
	return 0;
}
// ......................................... //

Read All

백준 BOJ 14458 - [USACO Platinum] Cow at Large (Platinum)

2019-05-27

booknu

PS_BOJ

PS BOJ USACO Fenwick 트리 SqrtDecomposition CentroidDecomposition
- 문제
문제

BOJ 15584(https://www.acmicpc.net/problem/15584)

$n$개의 정점을 가진 트리가 있다.

Bessie는 임의의 정점에서 시작하여 아무 $leaf$를 통해 탈출하려고 하고, 농부들은 여러 $leaf$에서 시작하여 Bessie가 leaf에 도달하기 전에 붙잡으려고 한다.

Bessie와 농부는 같은 이동속도를 가지고 있으며, 따라서 Bessie는 정점에서 붙잡히거나 간선을 건너는 도중 붙잡힐 수 있다.

Bessie와 농부는 항상 최선의 수로 움직인다고 하고, 각 정점마다 Bessie가 해당 정점에서 출발할 때 절때 leaf에 도달하지 못하도록 하기 위해 배치해야 할 농부의 최소 수를 구해야 한다.

(Bessie가 leaf에서 시작하는 경우에 대해서도 구해야하며, 이 때는 해당 $leaf$에 농부가 있으면 붙잡을 수 있다.)
Read All
Quick Select : 배열에서 k번째 원소를 O(n)에 찾기

2019-04-26

booknu

알고리즘_Sort

Sort
정렬되지 않은 배열에서 $k$번째 원소를 찾는 문제는 정렬 한 후 배열의 $k$번째 원소가 답이 되기 때문에 정렬 문제보다 쉬운 문제이다.

이 말은 즉, $k$번째 원소 찾기 알고리즘은 최소한 $O(n\log{n})$ 만에 풀 수 있다는 뜻이다.

그러나 Quick Sort의 아이디어를 사용하면 이것을 $O(n)$로 줄일 수 있다.

Quick Sort 활용

Quick Sort는 임의의 $pivot$을 뽑아 투 포인터 형식으로 현재 구간의 양쪽 끝에서 시작한 포인터를 이동시키면서 왼쪽의 $x > pivot$인 원소와 오른쪽의 $y < pivot$인 원소를 swap해가며 구간을 $pivot$보다 작거나 같은 것과 큰 것으로 나누어 나눠진 두 구간에 대해 재귀적으로 이 과정을 적용하는 방식으로 작동한다.

이 때, 우리는 한 가지 생각을 할 수 있다.

$pivot$으로 인해 나눠진 두 구간 중 하나는 아예 재귀를 하지 않아도 되지 않을까?

왜냐하면
- $pivot = k$ : $pivot$의 왼쪽에는 모두 $pivot$보다 작거나 같은 원소가 있고, 오른쪽에는 모두 $pivot$보다 큰 원소가 있으니 $k$번째 원소를 찾은 것이다.
- $pivot < k$ : 똑같은 논리로 $pivot$을 포함한 왼쪽 구간은 확인 할 필요가 없다.
- $pivot > k$ : 역시 $pivot$을 포함한 오른쪽 구간은 확인 할 필요가 없다.
즉, 아래의 그림처럼 연두색 구간에 대해서만 확인을 하면 된다.

(보라색은 그 단계에서의 $pivot$이다.)

($pivot$의 왼쪽은 모두 $pivot$의 이하이고, 오른쪽은 모두 $pivot$의 초과임을 유의하자)

시간복잡도

$pivot$을 아주 잘 잡아서 위의 그림과 같이 이상적으로 구간을 반으로 나눈다고 생각해보자.

그럼 총 시간복잡도는 다음과 같이 선형적으로 된다.

그러나 피벗을 현재 구간의 가장 첫 번째와 같이 최악의 경우로 잡으면, $k=n-1$일 때 시간복잡도가 $O(n^2)$이 된다.

따라서 Quick Sort의 경우와 마찬가지로 $pivot$을 잘 잡는 것이 중요하다.

다행히도 C++ STL에서는 이런 기능을 nth_element 함수로 구현해놓았다.

안정적인 알고리즘

항상 $O(n)$을 보장하는 알고리즘으로는 Median of medians 기법을 활용하는 Intro Select가 있다.

소스코드
```
// k는 0-idx로 가정한다.
int n, ar[MAXN];
int qselect(int k) {
	assert(k < n);
	int s = 0, e = n-1;
	while(1) {
		// pivot = ar[s] (원래는 랜덤하게 뽑아야 하지만, 간단하게 구현하기 위해)
		int i = s, j = e;
		while(1) {
			while(i <= e && ar[i] <= ar[s]) ++i;
			while(ar[j] > ar[s]) --j;
			if(i >= j) break;
			swap(ar[i], ar[j]);
		}
		swap(ar[s], ar[j]);
		// k번째 찾음
		if(j == k) return ar[j];
		// 구간 조절
		else if(j < k) s = j+1;
		else e = j-1;
	}
}
```
Read All

백준 BOJ 14458 - [USACO Platinum] Why Did the Cow Cross the Road

2019-04-26

booknu

PS_BOJ

PS BOJ USACO Fenwick

문제
문제 분석
초기 상태에서의 간선의 교차 세기
k번의 회전
소스코드

문제

BOJ 14458(https://www.acmicpc.net/problem/14458)

이분 그래프 형태로 양 쪽에 정점이 각각 $n$개씩 있고, 각 간선들은 모두 일대일 대응 형태로 주어진다.

양쪽의 정점들은 원형 형태로 회전시킬 수 있으나, 한 쪽만 임의의 $k$만큼 회전시키는게 가능하다.

이 때, 회전을 시킨 후 간선들이 교차되는 최소값을 찾아야 한다.

문제 분석

일대일 대응, 간선의 교차를 보면 가장 먼저 생각나는게 빈도수를 체크하기 좋은 Fenwick Tree이다.

간선의 교차라는 것은 즉, 어떤 간선이 $(u, v)$를 잇고 있을 때

$u$ 이전에서 시작한 간선이 $v$ 이후로 간다.
$u$ 이후에서 시작한 간선이 $v$ 이전으로 간다.

즉, 다음 두 가지 형태 중 하나로 간선의 교차가 이루어진다.

초기 상태에서의 간선의 교차 세기

우선 $k$만큼 정점을 회전시키는 건 나중에 하고, 처음 상태에서 간선의 교차 수를 세보자.

간선의 교차가 이루어지는 방식은 위에서 말한대로이고, 이것을 토대로 총 교차 수를 세면 되는데, 방법은 각각의 정점을 기준으로 $u$이후의 정점에서 시작해서 $v$이전으로 가는 것을 세서 전부 더할 것이다.

위 두 가지 경우 중 하나만 구한 이유는, 두 가지 모두 세버리면 중복이 생기기 때문이다.

이것을 편하게 구현하는 방법은 바로 Fenwick Tree를 이용하는 것이다.

Fenwick Tree의 “$u$이후에서 시작하는 간선들의 끝점”의 idx에 1을 표기해주면, $v$이전의 정점들의 수를 쉽게 계산 할 수 있다.

k번의 회전

양 쪽 중 하나만 회전시킬 수 있으므로, 우선 오른쪽만 회전시키는 경우를 생각하면 왼쪽을 회전시키는 경우는 같은 방법을 사용하여 쉽게 구할 수 있을 것이다.

현재 상태에서의 교차 간선의 수는 이미 구해져있다고 가정했을 때, 다음 $1$번을 회전하면 그 수가 어떻게 변하는지를 알 수 있으면, $n$번 회전을 시켜보며 그 값을 쉽게 구할 수 있을 것이다.

그런데 잘 보면, 회전을 할 때는 오른쪽의 맨 끝 정점만 맨 앞으로 옮겨짐을 알 수 있다.

현재 회전 대상인 정점을 잇는 간선에 대해서 왼쪽 정점의 idx를 $left$, 오른쪽 정점의 idx를 $right$라고 하면

항상 $right = n-1$ 일 것이고, 이 때 현재 이 간선으로 인해 생긴 교차의 수는 $left$개 라는 것을 알 수 있다.

또한 $right$를 $0$으로 회전시켰을 경우 생기는 새로운 교차의 수는 $n-left-1$개 라는 것을 알 수 있다.

즉, 새로운 총 교차의 수는 이전 교차의 수에서 현재 간선으로 인해 생긴 교차의 수를 뺀 뒤 새로 생기는 교차의 수를 더해주면 구할 수 있다.

소스코드

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL_BOOKNU
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

// ........................macro.......................... //
#define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
#define pb push_back
#define emb emplace_back
#define fi first
#define se second
#define ENDL '\n'
#define sz(A) (int)(A).size()
#define ALL(A) A.begin(), A.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
#define next next9876
#define prev prev1234
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef long long i64;
typedef unsigned long long ui64;
// inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
const i64 MOD = 1e9+7;
inline i64 POW(i64 a, i64 n) {
	assert(0 <= n);
	i64 ret;
	for(ret = 1; n; a = a*a%MOD, n /= 2) { if(n%2) ret = ret*a%MOD; }
	return ret;
}
template <class T> ostream& operator<<(ostream& os, vector<T> v) {
	os << "[";
	int cnt = 0;
	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
	return os << "]";
}
template <class T> ostream& operator<<(ostream& os, set<T> v) {
	os << "[";
	int cnt = 0;
	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
	return os << "]";
}
template <class L, class R> ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
// ....................................................... //

struct fenwick {
	int n;
	vi t;
	void init(int _n) {
		n = _n;
		t.assign(n+1, 0);
	}
	void add(int u, int x) {
		for(++u; u < t.size(); u += (u&-u)) {
			t[u] += x;
		}
	}
	int sum(int u) {
		int ret = 0;
		for(++u; u > 0; u -= (u&-u)) {
			ret += t[u];
		}
		return ret;
	}
};

const int MAXN = 1e5+10;
int n, ar[MAXN], br[MAXN], pa[MAXN], pb[MAXN];
fenwick ft;
void input() {
	cin >> n;
	FOR(i, 0, n) {
		int x; cin >> x; --x;
		ar[i] = x;
		pa[x] = i;
	}
	FOR(i, 0, n) {
		int x; cin >> x; --x;
		br[i] = x;
		pb[x] = i;
	}
}

i64 getans() {
	ft.init(n);
	FOR(i, 0, n) ft.add(i, 1);
	i64 sum = 0;
	FOR(i, 0, n) {
		ft.add(pb[ar[i]], -1);
		sum += ft.sum(pb[ar[i]]);
	}
	i64 ans = sum;
	RFOR(i, n-1, 0) {
		sum += pa[br[i]];
		sum -= (n-pa[br[i]]-1);
		ans = min(ans, sum);
	}
	return ans;
}

int solve() {
	i64 ans = getans();
	FOR(i, 0, n) {
		int t = ar[i];
		ar[i] = br[i];
		br[i] = t;
		t = pa[i];
		pa[i] = pb[i];
		pb[i] = t;
	}
	ans = min(ans, getans());
	cout << ans << ENDL;
	return 0;
}

// ................. main .................. //
void execute() {
	input(), solve();
}

int main(void) {
#ifdef LOCAL_BOOKNU
	freopen("input.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
#endif
	cin.tie(0), ios_base::sync_with_stdio(false);
	execute();
	return 0;
}
// ......................................... //

Read All

백준 BOJ 2803 - [COCI] KOŠARE

2019-04-24

booknu

PS_BOJ

PS BOJ COCI bitmask OR 분할정복
문제

BOJ 2803(https://www.acmicpc.net/problem/2803)

$n$개의 $m$종류의 장난감이 들어갈 수 있는 상자가 있다.

각 상자에는 $m$종류 중 일부의 장난감만이 들어 있을 때,

모든 종류의 장난감을 얻을 수 있도록 상자를 선택하는 방법의 수는?

문제 분석

즉, 집합에 $n$개의 $m$-bit 숫자들이 원소로 있을 때,

부분 집합의 원소들의 or 연산 결과가 $m$-bit의 $1111…$이 되는 경우의 수를 세는 문제이다.

DP 아이디어

다음과 같은 DP 식을 사용하면, $O(n \cdot 2^m)$ 시간복잡도로 해결 할 수 있다.

$dp[i][mask] = 현재$ $i$까지 고려했을 때, $mask$ 상태가 되는 경우의 수

하지만, 이렇게 구현하면 시간초과가 날 것이 분명하니, 다른 방법을 생각해야 한다.

분할정복 아이디어

편하게 submask가 되는 방법들을 생각해보자

정확히 $mask$가 되는 경우를 생각하지 말고, $mask$의 $submask$가 되는 경우를 생각하는 것이 더 편할 것이다.

따라서

$b[x] = 수들$ 중 $x$의 서브마스크가 되는 경우의 수

$c[x] = 수들$의 or 결과가$x$의 서브마스크가 되는 경우의 수

$c[x] = 2^{b[x]}$로 구하면 되니까, $b[x]$를 구하는 방법에 대해서만 생각하면 된다.

또한 어찌됐건 or의 결과가 정확히 $x$가 되는 경우도 구해야 하니까, 이것을 $a[x]$라고 하자.

분할정복으로 $b[x]$ 구하기

우선 $b[x]$에는 초기의 $x$자체인 숫자의 수를 넣어주고, 분할정복을 통해 이것을 우리가 원하는 $b[x]$(OR 결과가 $x$의 submask가 되는 경우의 수)로 만들 것이다.

이 때, 이 과정을 각 bit를 순회하며 $b[x의\ ith{-}bit가\ 켜진\ 경우]$에 $b[x의\ ith{-}bit가\ 꺼진\ 경우]$를 더해가는 방법을 사용 할 것인데, 이것을 구현하기 위해 분할정복을 사용 할 것이다.

즉, 다음과 같이 $[0, 2^m)$구간을 분할정복하며 위의 방법을 사용할 것이다.

(다음 그림은 $m = 3$인 경우이다.)

가장 상위 구간 $[000, 1000)$에서는 $1st{-}bit$가 켜진 경우에 그것이 꺼진 경우를 더할 것이고, 아래에서도 재귀적으로 그것을 적용할 것이다.

(즉, 구간을 반으로 쪼개면 $[000, 100), [100, 1000)$이 되는데, 왼쪽 구간의 값을 오른쪽 구간에 더하는 것이다.)

이것이 가능한 이유는 총 구간이 $2^m$(2의 제곱수) 형태이기 때문에, 분할정복을 할 시 각 레벨의 길이는 항상 $2^{m-lv}$이 되고, 그 레벨을 반으로 쪼갤 경우 항상 $(lv+1)$-bit가 켜지고 꺼진 경우로 나눌 수 있기 때문이다.

이렇게 재귀의 끝까지 가면 항상 $b[x]$가 우리가 원하던 “$x$의 $submask$인 수의 수”가 됨을 보장 할 수 있다.

그 이유는 우선 최상위 레벨에서는 $b[x]$가 $1st{-}bit$이 켜지고 꺼진 경우를 포함하게 되고, 다음 레벨에서는 위의 결과를 이어받고, $b[x]$가 $(1,2)th{-}bit$가 켜지고 꺼진 경우를 포함하게 되고, 이를 재귀적으로 반복하면 결국 재귀의 끝에서는 $b[x]$가 $(1..m)th{-}bit$가 켜지고 꺼진 경우를 모두 포함하게 되는데, 이것이 즉 $x$의 $submask$가 되는 경우를 모두 포함한다는 것이다.

결과적으로는 top-down 방식으로 재귀를 하며 $b[x]$를 구해가는 것이다.

$c[x]$, a[x] 구하기

$c[x] = 2^{b[x]}$로 간단하게 구할 수 있다.

그렇다면 정확히 or 결과가 $x$가 되는 $a[x]$는 어떻게 구할까?

이것 역시 위에서 $b[x]$를 구한 방법과 비슷하게 구할 수 있다.

즉, $c[x의\ ith{-}bit가\ 켜진\ 경우]$에서 $c[x의\ ith{-}bit가\ 꺼진\ 경우]$를 점점 빼가면 결국은 $a[x]$가 된다는 것을 같은 논리로 설명 할 수 있다.

소스코드

구현에서는 직접 a[x], b[x], c[x]를 사용하지 않고 하나의 ar[x]를 사용해서 그것들을 동시에 표현했는데, 이것에 유의하여 보길 바란다.
```
#ifndef ONLINE_JUDGE
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <bits/stdc++.h>
using namespace std;

// ........................macro.......................... //
// [i, n)
#define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
// [i, n]
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
#define pb push_back
#define emb emplace_back
#define fi first
#define se second
#define ENDL '\n'
#define sz(A) (int)(A).size()
#define ALL(A) A.begin(), A.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
#define next next9876
#define prev prev1234
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<pair<int, int> > vii;
typedef vector<vector<pair<int, int> > > vvii;
typedef pair<int, int> ii;
typedef pair<int, pair<int, int> > iii;
typedef long long i64;
typedef unsigned long long ui64;
// inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
inline i64 GCD(i64 a, i64 b) { i64 n; if(a<b) swap(a, b); while(b!=0) { n = a%b; a = b; b = n; } return a; }
inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); }
inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d)*2 >= d); }
const i64 MOD = 1e9+7;
inline i64 POW(i64 a, i64 n) {
	if(n < 0) return 0;
	i64 ret = 1;
	while(n) { if(n % 2) ret *= a, ret %= MOD; a = a * a, a %= MOD; n /= 2; }
	return ret;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << to_string(H);
	debug_out(T...);
}
#ifndef ONLINE_JUDGE
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

// ....................................................... //

const int MAXN = 1e6, MAXM = 20;
int n, m;
i64 ar[1<<MAXM];
void input() {
	cin >> n >> m;
	FOR(i, 0, n) {
		int nn, k = 0; cin >> nn;
		while(nn--) {
			int x; cin >> x; --x;
			k |= (1 << x);
		}
		++ar[k]; // ar[x]의 초기 값: x인 수들의 개수
	}
}

// 분할 정복은 구간이 정확히 2의 제곱수가 되게 수행한다.
// 이렇게 함으로써, 왼쪽과 오른쪽 구간의 차이는 정확히 2^(len-1) 만큼 난다.
// 즉, 오른쪽 구간의 수들은 왼쪽 구간의 수들에서 (len-1) bit만 켠 것과 같다.
// 또한 재귀 중 ar[x]가 의미하는 바가 달라진다!
// top-down 재귀가 끝나고 난 바로 뒤의 ar[x] = b[x]
// leaf에서 작업이 끝나고 난 바로 뒤의 ar[x] = c[x]
// 모든 과정이 끝나고 난 뒤의 ar[x] = a[x]
void f(int s, int e) {
	// leaf: top-down 재귀의 끝 (c[x] = 2^b[x])
	// 이 시점에 ar[x] = b[x]이다.
	if(s+1 == e) {
		ar[s] = POW(2, ar[s]);
		return;
	}
	// top-down 재귀로 b[x]를 구해나간다.
	int m = (s+e)/2;
	FOR(i, m, e) ar[i] += ar[s+i-m];
	f(s, m), f(m, e);
	// top-down 재귀 끝나고 a[x]를 구하는 과정
	FOR(i, m, e) {
		ar[i] -= ar[s+i-m];
		if(ar[i] < 0) ar[i] += MOD;
	}
}

int solve() {
	f(0, 1 << MAXM);
	cout << ar[(1 << m) - 1] << ENDL;
	return 0;
}

// ................. main .................. //
void execute() {
	input(), solve();
}

int main(void) {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
#endif
	cin.tie(0); ios_base::sync_with_stdio(false);
	execute();
	return 0;
}
// ......................................... //
```
Read All
임시변수 없이 swap 하기

2019-04-24

booknu

알고리즘_Math

Math XOR 역원
임시변수 없이 swap을 하는 신박하지만 실제로 쓸모는 없는 방법을 소개한다.

개요

보통 두 변수를 바꾸는 swap 함수는 다음과 같이 구현한다.
```
void swap(int& a, int& b) {
	int t = a;
	a = b;
	b = t;
}
```
그러면, 임시변수 t를 사용하지 않고 swap을 구현하는 방법이 있을까?

XOR

결론부터 말하자면, xor 연산을 이용하여 다음과 같이 구현 가능하다.
```
void swap(int& a, int& b) {
	a ^= b;
	b ^= a;
	a ^= b;
}
```
이 과정을 수학적으로 써보면 다음과 같이 swap이 됨을 알 수 있다.

초기값: $a = x, b = y$

a ^= b: $a = x \oplus y$

b ^= a: $b = y \oplus (x \oplus y) = x$

a ^= b: $a = (x \oplus y) \oplus x = y$

사칙연산으로 확장

위의 xor을 이용한 방법을 잘 살펴보면, 결국 a에 $x, y$ 값을 쌓아두고, b에서는 $x, y$ 값에서 $y$값을 제외한 것을 가져가고, a에서는 $x, y$ 값에서 $x$값을 제외한 것을 가져감을 알 수 있다.

즉, 쌓아두고 뺄 수 있는 연산이면 모두 이런 식으로 구현 할 수 있다는 것인데, 사칙연산이 이에 해당한다.
덧셈을 이용
void swap(int& a, int& b) { a += b; b = a - b; a = a - b; }
곱셈을 이용($b \neq 0$)
void swap(int& a, int& b) { assert(b != 0); a *= b; b = a / b; a = a / b; }
단, 이 경우 overflow 문제가 발생 할 수 있으니, xor 연산을 사용하는게 더 안전하고 효율적이다.

일반화

위에서 연산의 쌓아두고 뺄 수 있는 특성을 이용했는데, 이 때 빼는 경우를 수학적으로 역원이라고 생각 할 수 있다.

역원이란 임의의 연산 $*$의 항등원 $e$가 존재 할 때, $a$에 대해 $a * b = b * a = e$ 인 $b$가 유일하게 존재할 때, $b$를 $a$의 역원이라고 한다.

즉, $b$의 역원 $rev(b)$가 존재한다는 것은 $a * b$ 상태에서 $a * b * rev(b) = a$, 즉 $b$를 제외 할 수 있다는 것이다.

이것을 이용하면 역원이 항상 존재하는 연산 $*$을 이용해 swap을 구현 할 수 있다는 것을 알 수 있다.
```
int oper(int, int); // 역원이 항상 존재하는 어떤 연산
int rev(int); // 위 연산의 역원을 구한다.
void swap(int& a, int& b) {
	a = oper(a, b);
	b = oper(a, rev(b));
	a = oper(a, rev(b));
}
```
Read All

2/4

Welcome to booknu's Blog!

코드포스 Educational Codeforces #66(Div.2) 리뷰

개요

A번

B번

C번

D번

백준 BOJ 14458 - [USACO Platinum] Cow at Large (Platinum)

문제

Quick Select : 배열에서 k번째 원소를 O(n)에 찾기

Quick Sort 활용

시간복잡도

안정적인 알고리즘

소스코드

백준 BOJ 14458 - [USACO Platinum] Why Did the Cow Cross the Road

문제

문제 분석

초기 상태에서의 간선의 교차 세기

k번의 회전

소스코드

백준 BOJ 2803 - [COCI] KOŠARE

문제

문제 분석

DP 아이디어

분할정복 아이디어

편하게 submask가 되는 방법들을 생각해보자

분할정복으로 $b[x]$ 구하기

$c[x]$, a[x] 구하기

소스코드

임시변수 없이 swap 하기

개요

XOR

사칙연산으로 확장

일반화