티스토리 뷰
백준 땅따먹기에서 열린 Hanbyeolforces Global Round 2에 참여해 보았다.
BOJ 11712. JAG-channel II
Bitmask DP를 할 것이다. 그런데 무슨 사람을 썼는지 말고 post가 어떤 순서로 있는지도 저장해야 하는 게 까다롭다.
$1 \le N-K \le 3$이라는 특이한 조건 때문에 마지막 사람을 저장하면, 마지막 사람에 포함되지 않은 post의 개수가 최대 $3$개이므로 그 순서들만 따로 저장해도 충분함을 알 수 있다. 이렇게 하고 Bitmask DP를 돌리면 문제를 $O(2^N \times N^2 \times 3!)$ 정도의 시간에 풀 수 있다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct State{
int d, last, rem; string str;
State(){}
State(int d, int last, int rem, string str): d(d), last(last), rem(rem), str(str){}
};
int n, k;
int arr[17][17];
bool able[1<<17][17][6];
int nxtVal[17][6][17];
int findNxt(int last, int remOrder, int nxt){
if(nxtVal[last][remOrder][nxt] != -2) return nxtVal[last][remOrder][nxt];
vector<bool> chk (n, 1);
vector<int> order, rem;
for(int i=0; i<k; i++) chk[arr[last][i]] = 0, order.push_back(arr[last][i]);
reverse(order.begin(), order.end());
for(int i=0; i<n; i++) if(chk[i]) rem.push_back(i);
sort(rem.begin(), rem.end());
for(int cnt=0; cnt < remOrder; cnt++) next_permutation(rem.begin(), rem.end());
for(int x: rem) order.push_back(x);
int result = 0;
vector<bool> good (n, 0);
int pnt = 0;
for(int i=0; i<k; i++){
while(pnt<n && order[pnt] != arr[nxt][i]) pnt++;
if(pnt >= n){
result = -1;
break;
}
good[pnt] = 1;
}
if(result == 0){
rem.clear();
for(int i=0; i<n; i++) if(!good[i]) rem.push_back(order[i]);
int cnt = 0;
while(prev_permutation(rem.begin(), rem.end())) cnt++;
result = cnt;
}
// return result;
return nxtVal[last][remOrder][nxt] = result;
}
inline string toStr(int x){
return string(1, char('A'+x));
}
int main(){
for(int a=0; a<16; a++) for(int b=0; b<6; b++) for(int c=0; c<16; c++) nxtVal[a][b][c] = -2;
scanf("%d %d", &n, &k);
for(int i=0; i<n; i++) for(int j=0; j<k; j++){
char c;
scanf(" %c", &c);
arr[i][j] = c-'A';
}
int p = n-k;
int f = p==1 ? 1 : p==2 ? 2 : 6;
for(int s=0; s<n; s++){
for(int t=0; t<f; t++){
able[1<<s][s][t] = 1;
}
}
for(int b=1; b<(1<<n); b++){
for(int e=0; e<n; e++){
for(int r=0; r<f; r++){
if(!able[b][e][r]) continue;
// printf("%d %d %d\n", b, e, r);
for(int i=0; i<n; i++){
if((b>>i)&1) continue;
int nxt = findNxt(e, r, i);
if(nxt < 0) continue;
able[b+(1<<i)][i][nxt] = 1;
}
}
}
}
for(int b=(1<<n)-2; b>=1; b--){
for(int e=0; e<n; e++){
for(int r=0; r<f; r++){
if(!able[b][e][r]) continue;
bool exist = 0;
for(int i=0; i<n; i++){
if((b>>i)&1) continue;
int nxt = findNxt(e, r, i);
if(nxt >= 0 && able[b+(1<<i)][i][nxt]) {exist = 1; break;}
}
if(!exist) able[b][e][r] = 0;
}
}
}
vector<State> vec;
for(int s=0; s<n; s++){
for(int t=0; t<f; t++){
if(able[1<<s][s][t]) vec.push_back(State(1<<s, s, t, toStr(s)));
}
if(!vec.empty()) break;
}
for(int turn=1; turn<n; turn++){
vector<State> vec2;
for(int i=0; i<n; i++){
for(State &p: vec){
int b = p.d, e = p.last, r = p.rem;
if((b>>i)&1) continue;
int nxt = findNxt(e, r, i);
if(nxt >= 0 && able[b+(1<<i)][i][nxt]){
vec2.push_back(State(b+(1<<i), i, nxt, p.str + toStr(i)));
}
}
if(!vec2.empty()) break;
}
vec = vec2;
}
printf("%s", vec[0].str.c_str());
}BOJ 32413. 카드 뒤집기 2
앞에서부터 답을 결정짓고, 그 다음 카드는 앞 차례의 카드 값들을 이용해 찾는 전략을 사용하자.
앞면이 $a$고 뒷면이 $b$인 카드가 어떤 값이 나왔을지를 알아보자. $a=b$라면 자명하니 넘어가도 된다. $a>b$인 경우를 보자. 이때 앞에 $[a+1, b]$ 범위의 카드가 있다면 어떤 경우에도 뒤집히고, $[b+1, a]$ 범위의 카드가 있다면 $b$인 경우에만 뒤집히고, $[1, b]$ 범위의 카드가 있다면 뒤집히지 않는다. 중간의 $[b+1, a]$ 범위인 경우가 중요하다. 이 경우 어떤 경우에도 카드의 앞면이 $a$가 되기 때문이다. 따라서 가장 최근에 $[b+1, a]$ 범위의 답이 어디서 나왔는지 찾고, 그 뒤로 $[b+1, a]$ 구간의 카드가 몇 번 나왔는지를 세면 답을 구할 수 있다. 이것은 각각 일반적인 segment tree와 Persistent segment tree를 이용해 해결할 수 있다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct segTree{
int tree[1<<19];
void update(int i, int l, int r, int x, int v){
if(l==r){
tree[i] = v;
return;
}
int m = (l+r)>>1;
if(x<=m) update(i*2, l, m, x, v);
else update(i*2+1, m+1, r, x, v);
tree[i] = max(tree[i*2], tree[i*2+1]);
}
int query(int i, int l, int r, int s, int e){
if(r<s || e<l) return 0;
if(s<=l && r<=e) return tree[i];
int m = (l+r)>>1;
return max(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
}
} tree;
struct PST{
struct Node{
Node *lc, *rc;
int val;
Node(){lc = rc = nullptr, val = 0;}
Node(int l, int r){
if(l!=r){
int m = (l+r)/2;
lc = new Node(l, m), rc = new Node(m+1, r);
}
val = 0;
}
~Node(){
if(lc) delete lc;
if(rc) delete rc;
}
Node *update(int l, int r, int x, int v){
Node *tmp = new Node();
if(l==r){
tmp->val = val + v;
return tmp;
}
int m = (l+r)>>1;
if(x<=m) tmp->lc = lc->update(l, m, x, v), tmp->rc = rc;
else tmp->lc = lc, tmp->rc = rc->update(m+1, r, x, v);
tmp->val = tmp->lc->val + tmp->rc->val;
return tmp;
}
int query(int l, int r, int s, int e){
if(r<s || e<l) return 0;
if(s<=l && r<=e) return val;
int m = (l+r)>>1;
return lc->query(l, m, s, e) + rc->query(m+1, r, s, e);
}
} *root;
Node *history[200002];
int cnt = 0, n;
void init(int _n){
n = _n;
history[0] = root = new Node(1, n);
}
void update(int x, int v){
int c = ++cnt;
history[c] = history[c-1]->update(1, n, x, v);
}
int query(int p, int l, int r){
if(l>r) return 0;
return history[cnt]->query(1, n, l, r) - history[p]->query(1, n, l, r);
}
} pst;
int n;
int A[200002], B[200002];
int ans[200002];
void putAns(int x, int v){
ans[x] = v;
tree.update(1, 1, n, v, x);
pst.update(v, 1);
}
int main(){
scanf("%d", &n);
for(int i=1; i<=n; i++) scanf("%d", &A[i]);
for(int i=1; i<=n; i++) scanf("%d", &B[i]);
pst.init(n);
putAns(1, A[1]);
for(int i=2; i<=n; i++){
int a = A[i], b = B[i];
if(a==b){
putAns(i, a);
continue;
}
int p = tree.query(1, 1, n, min(a,b)+1, max(a,b)); /// 첫 위치
int c = pst.query(p, max(a,b)+1, n);
int t = 0;
if(!p) t = (c%2==0 ? a : b);
else t = (c%2==0 ? max(a,b) : min(a,b));
putAns(i, t);
}
for(int i=1; i<=n; i++) printf("%d ", ans[i]);
}BOJ 24866. Birthday
모든 $i$에 대해 $A_i \ge B_i$를 가정한다. 이게 성립하지 않으면 바꿔 주면 된다.
$k$의 배수 조건이 없을 때 답을 먼저 구하자. 답은 각 $A_i$가 몇 번 더해지는지를 더블 카운팅으로 세면 $\sum A_i \times i(n+1-i)$임을 알 수 있다.
이제 여기서 얼마가 빠지는지를 생각해 보자. 합이 줄어드는 이유는 어떤 구간의 $A_i$ 합이 $k$의 배수이다. 이런 후보들을 골라내기 위해 $A$의 누적합 $S_i$를 구하고 $S_i$를 $k$로 나눈 나머지가 같은 것끼리 묶자. 이제 구간의 양끝점이 이 그룹 안에 있는 경우에 한해서 답의 감소량을 구하면 된다.
각각의 끝점 사이에 있는 수들 중 $k$의 배수가 아닌 $A_i - B_i$의 최솟값을 구해 놓자. (그런 것이 없으면 $\infty$로 둔다.) $\infty$로만 이루어진 구간은실제 문제에서 $A_i$나 $B_i$ 어떤 쪽을 고르든 $k$의 배수가 되므로 전체 합을 빼 줘야 한다. 이것은 앞의 더블 카운팅과 비슷하게 하면 된다. 그렇지 않다면, 구간의 최소 $A_i - B_i$만큼 빼주면 되는데, 이것은 segment tree와 dnc로 가능하다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1'000'000'007;
const ll INF = (ll)1e18;
struct segTree{
ll tree[1<<20]; int minIdx[1<<20];
void init(int i, int l, int r, ll *A){
if(l==r){
tree[i] = A[l];
minIdx[i] = l;
return;
}
int m = (l+r)>>1;
init(i*2, l, m, A);
init(i*2+1, m+1, r, A);
if(tree[i*2] < tree[i*2+1]) tree[i] = tree[i*2], minIdx[i] = minIdx[i*2];
else tree[i] = tree[i*2+1], minIdx[i] = minIdx[i*2+1];
}
ll query(int i, int l, int r, int s, int e){
if(r<s || e<l) return INF;
if(s<=l && r<=e) return tree[i];
int m = (l+r)>>1;
return min(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
}
pair<ll, int> queryIdx(int i, int l, int r, int s, int e){
if(r<s || e<l) return make_pair(INF, -1);
if(s<=l && r<=e) return make_pair(tree[i], minIdx[i]);
int m = (l+r)>>1;
return min(queryIdx(i*2, l, m, s, e), queryIdx(i*2+1, m+1, r, s, e));
}
} tree, tree2;
int n; ll k;
ll A[500002], B[500002], S[500002], V[500002];
ll ans;
int m;
ll T[500002];
void dnc(int l, int r){
pair<ll, int> pr = tree2.queryIdx(1, 1, m, l, r);
if(pr.first == INF) return;
int x = pr.second;
ll v = T[x] * (x-l+1) % MOD * (r-x+1) % MOD;
ans = (ans - v + MOD) % MOD;
if(l<x) dnc(l, x-1);
if(x<r) dnc(x+1, r);
}
void solve(vector<ll> &sum, vector<ll> &value){
m = (int)sum.size();
/// 아예 없는 부분 제거
for(int i=0; i<m; i++){
if(value[i] != INF) continue;
int j = i;
while(j+1<m && value[j+1] == INF) j++;
for(int x=i; x<=j; x++){
ll v = sum[x] % MOD * (x-i+1) % MOD * (j-x+1) % MOD;
ans = (ans - v + MOD) % MOD;
}
i=j;
}
for(int i=1; i<=m; i++) T[i] = value[i-1];
tree2.init(1, 1, m, T);
dnc(1, m);
}
int main(){
scanf("%d %lld", &n, &k);
for(int i=1; i<=n; i++){
scanf("%lld %lld", &A[i], &B[i]);
if(A[i] < B[i]) swap(A[i], B[i]);
}
/// calculate all sum
for(int i=1; i<=n; i++){
ans += A[i] * i % MOD * (n+1-i) % MOD;
ans %= MOD;
}
/// now calculate what to subtract
vector<pair<ll, int> > v;
v.push_back(make_pair(0LL, 0));
for(int i=1; i<=n; i++){
S[i] = S[i-1] + A[i];
V[i] = (A[i] - B[i]) % k == 0 ? INF : A[i] - B[i];
v.push_back(make_pair(S[i] % k, i));
}
tree.init(1, 1, n, V);
sort(v.begin(), v.end());
for(int l=0; l<=n; l++){
int r = l;
while(r < n && v[r+1].first == v[l].first) r++;
if(l==r) continue;
vector<ll> sum, value;
for(int i=l; i<r; i++){
sum.push_back(S[v[i+1].second] - S[v[i].second]);
value.push_back(tree.query(1, 1, n, v[i].second+1, v[i+1].second));
}
solve(sum, value);
l=r;
}
printf("%lld", ans);
}BOJ 14634. Get a Clue!
백트래킹 문제이다. 비트마스킹을 잘 활용하고 경우의 수 분석을 잘 해서 시간을 줄이는 것이 핵심이다.
대략적인 흐름은, 각 사람별로 무조건 있어야 할 카드, 무조건 없어야 할 카드를 고를 수 있다. 또한 이 세 장 중에 한 장을 가지고 있어야 한다는 경우가 생긴다. 이 정보들을 모두 모은 뒤, 각 사람별로 가능한 카드 조합을 모두 구해 놓는다. (정확히는, 각 사람별로 이 카드 조합이 가능한지를 저장해 놓는다.) 다음으로, 답 카드 세 장을 정해 놓고, 백트래킹을 통해 가능한 모든 나머지 세 명 카드 조합을 시도해 보며 가능한지 판별하면 된다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline char input(){
char c;
scanf(" %c", &c);
return c;
}
inline int input(int x){
int ret = 0;
for(int i=0; i<x; i++) ret |= (1<<(input()-'A'));
return ret;
}
int n;
int my;
int yes[4], no[4];
vector<int> yescand[4];
bool poss[4][1<<21];
bool ans[21];
const int total[4] = {0, 5, 4, 4};
int cnt[4], value[4];
inline bool dfs(int left, int x){
if(x == 21){
if(poss[1][value[1]] && poss[2][value[2]] && poss[3][value[3]]){
// printf("%d %d %d\n", value[0], value[1], value[2]);
}
return poss[1][value[1]] && poss[2][value[2]] && poss[3][value[3]];
}
if(!((left>>x)&1)) return dfs(left, x+1);
for(int d=1; d<4; d++){
if(cnt[d] < total[d]){
cnt[d]++, value[d] ^= (1<<x);
if(dfs(left^(1<<x), x+1)) return true;
cnt[d]--, value[d] ^= (1<<x);
}
}
return false;
}
bool able(int a, int b, int c){
int V = ((1<<21) - 1) ^ my ^ (1<<a) ^ (1<<b) ^ (1<<c);
cnt[1] = cnt[2] = cnt[3] = 0;
value[1] = value[2] = value[3] = 0;
return dfs(V, 0);
}
void print(int l, int r){
if(count(ans+l, ans+r+1, true) > 1) printf("?");
else printf("%c", 'A' + find(ans+l, ans+r+1, true) - ans);
}
int main(){
scanf("%d", &n);
my = input(5);
for(int turn=0; turn<n; turn++){
int suppose = input(3);
for(int d=(turn+1)%4; d!=turn%4; d=(d+1)%4){
char c = input();
if(c == '-') no[d] |= suppose;
else if(c == '*') {yescand[d].push_back(suppose); break;}
else {yes[d] |= 1<<(c-'A'); break;}
}
}
for(int d=1; d<4; d++){
for(int t=0; t<(1<<21); t++){
if((t&yes[d]) != yes[d] || __builtin_popcount(t) != total[d] || (t&my)) continue;
if(t&no[d]) continue;
poss[d][t] = 1;
for(int x: yescand[d]){
if(!(t&x)){
poss[d][t] = 0;
break;
}
}
}
}
for(int i=0; i<6; i++){
for(int j=6; j<12; j++){
for(int k=12; k<21; k++){
if(my & ((1<<i)+(1<<j)+(1<<k))) continue;
if(able(i, j, k)){
ans[i] = ans[j] = ans[k] = 1;
}
}
}
}
print(0,5);
print(6,11);
print(12,20);
}BOJ 21272. Harsh Comments
다이아4 치고 굉장히 어렵게 느껴졌다.
먼저 문제를 동치인 꼴로 환원해야 한다. 공 $a_i$가 $A_i$개 있고, 공 $b_i$가 $B_i$개가 있을 때, 이들을 적당히 섞는다고 하자. 이때 $a_i$들 중 첫 등장이 가장 나중에 나오는 위치 $x$를 잡고, 그 위치를 포함해 그 앞에 나오는 서로 다른 공의 개수의 기댓값을 구하자. 이렇게 문제를 변형하면 동치라는 것은 직관적인 느낌이 강하고, 증명도 가능한 것 같다.
여기서 $B_i$를 한 번에 생각하면 너무 어려우니, 기댓값의 선형성을 이용해 보자. $m = 1$이라고 가정하고 $B_i$가 $x$ 왼쪽에 한번이라도 등장할 확률을 구할 수 있다면, 이것들을 모든 $B_i$에 대해 다 더해주면 답이 된다. (실제로는 답에 $n$을 더 더해야 하는데 이는 $A_i$도 고려해야 하기 때문이다.)
우리는 공 $a_i$들을 전부 배치한 뒤, 그 사이에 $ b_i$를 끼워 넣는다고 생각할 것이다. $\sum A_i = S_A$라고 하자. 먼저 각각의 $x$에 대한 확률 $p_x$를 구해줄 것이다. $p_x$는 DP를 통해 구할 수 있다. $DP[i][x]$를 $a_1, \cdots, a_i$ 공을 모두 넣었을 때 첫 등장의 최후 위치가 $x$인 경우의 수라고 하자. 이 $DP$를 잘 전이하면 $O(n^4)$에 할 수 있다. $p_x$는 $DP[n][x]$에서 전체 경우의 수를 나누는 것으로 구할 수 있다.
그다음으로 각 $p_x$에 대해, 각 $b_i$가 왼쪽에 들어가는 경우의 수를 구해야 한다. 식정리를 하면 대략 $\frac{S_A! (S_a-x+v)!}{(S_a-x)! (S_A+v)!}$ 같은 형태가 나오고, 이것을 그냥 계산하기는 너무 어렵다. 하지만 $x=1$인 경우 구하기 쉽고, $x$가 하나씩 늘어날 때마다 얼마나 곱해줘야 하는지를 따라가면 각 $(x, i)$ 쌍에 대한 답을 $O(n^3)$에 계산할 수 있다. 이 기댓값을 모두 더하면 문제를 해결할 수 있다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
ll mpow(ll x, ll y){
if(!y) return 1;
if(y&1) return mpow(x, y-1)*x%MOD;
ll tmp = mpow(x, y/2);
return tmp * tmp % MOD;
}
ll modInv(ll x){
return mpow(x, MOD-2);
}
int n, m;
ll A[102], B[102], sA;
ll fact[100002], factInv[100002];
ll P[102][10002];
inline ll comb(ll n, ll k){
return (k<0 || n<k) ? 0 : fact[n] * factInv[k] % MOD * factInv[n-k] % MOD;
}
ll value(ll l, ll r, ll s, ll e){
ll ret = 1, inv = 1;
for(ll i=l; i<=r && i<s; i++) ret = ret * i % MOD;
for(ll i=max(r+1, s); i<=e; i++) inv = inv * i % MOD;
return ret * modInv(inv) % MOD;
}
int main(){
fact[0] = 1;
for(int i=1; i<=100000; i++) fact[i] = fact[i-1] * i % MOD;
factInv[100000] = modInv(fact[100000]);
for(int i=99999; i>=0; i--) factInv[i] = factInv[i+1] * (i+1) % MOD;
scanf("%d %d", &n, &m);
for(int i=1; i<=n; i++) scanf("%lld", &A[i]), sA += A[i];
for(int i=1; i<=m; i++) scanf("%lld", &B[i]);
ll allCase = fact[sA];
for(int i=1; i<=n; i++) allCase = allCase * factInv[A[i]] % MOD;
P[1][1] = 1;
int S = 0;
for(int i=2; i<=n; i++){
S += A[i-1];
for(int x=1; x<=S; x++){
for(int c=1; c<=A[i]; c++){
P[i][x+c] = (P[i][x+c] + P[i-1][x] * comb(x+c-1, c) % MOD * comb(S-x+A[i]-c, A[i]-c)) % MOD;
}
}
ll sum = 0;
for(int y=1; y<=S; y++){
sum = (sum + P[i-1][y]) % MOD;
P[i][y+1] = (P[i][y+1] + sum * comb(S-y+A[i]-1, A[i]-1)) % MOD;
}
}
for(int x=1; x<=sA; x++) P[n][x] = P[n][x] * modInv(allCase) % MOD;
ll ans = n;
for(int i=1; i<=m; i++){
ll coef = sA * modInv(sA + B[i]) % MOD;
for(int x=1; x<=sA; x++){
ll v = (MOD + 1 - coef) % MOD;
ans = (ans + v * P[n][x]) % MOD;
coef = coef * (sA - x) % MOD * modInv(sA - x + B[i]) % MOD;
}
}
printf("%lld", ans);
}BOJ 28046. Gravitational Wave Detector
남은 한 점이 있을 수 있는 공간을 생각해 보면, $\frac{A+B}{2}$, $2A-B$, $2B-A$ 중 하나임을 알 수 있다. 여기서 $A$와 $B$는 두 다각형 내의 임의의 점이다.
따라서 이 세 다각형을 민코프스키 합을 통해 구해 주고, 볼록 껍질을 상하로 나누는 테크닉을 이용해 안에 있는 점들을 모두 구하면 된다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct vector2{
ll x, y; int idx;
vector2(){}
vector2(ll x, ll y): x(x), y(y){}
vector2 operator-(const vector2& r) const {
return vector2(x - r.x, y - r.y);
}
vector2 operator+(const vector2& r) const {
return vector2(x + r.x, y + r.y);
}
ll cross(const vector2& r) const {
return x * r.y - y * r.x;
}
bool operator<(const vector2& r) const {
return x < r.x || (x == r.x && y < r.y);
}
bool operator==(const vector2& r) const {
return x == r.x && y == r.y;
}
bool operator!=(const vector2& r) const {
return x != r.x || y != r.y;
}
};
ll ccw(vector2 a, vector2 b){
return a.cross(b);
}
ll ccw(vector2 a, vector2 b, vector2 c){
return (b-a).cross(c-a);
}
struct Polygon{
int n;
vector<vector2> arr;
void input(){
scanf("%d", &n);
arr.resize(n);
for(int i=0; i<n; i++) scanf("%lld %lld", &arr[i].x, &arr[i].y), arr[i].x *= 2, arr[i].y *= 2;
}
Polygon minkowski_sum(const Polygon& other) {
auto sort_ccw = [](vector<vector2>& points) {
auto pivot = *min_element(points.begin(), points.end());
sort(points.begin(), points.end(), [pivot](const vector2& a, const vector2& b) {
ll cross = (a - pivot).cross(b - pivot);
if (cross == 0) {
return (a.x < b.x || (a.x == b.x && a.y < b.y));
}
return cross > 0;
});
};
vector<vector2> a = arr;
vector<vector2> b = other.arr;
sort_ccw(a);
sort_ccw(b);
vector<vector2> result;
int i = 0, j = 0, m = a.size(), n = b.size();
while (i < m || j < n) {
vector2 va = a[i % m];
vector2 vb = b[j % n];
result.push_back(va + vb);
ll cross_product = (a[(i + 1) % m] - va).cross(b[(j + 1) % n] - vb);
if (cross_product >= 0) i++;
if (cross_product <= 0) j++;
}
vector<vector2> unique_result;
for (size_t k = 0; k < result.size(); ++k) {
if (k == 0 || result[k] != result[k - 1]) {
unique_result.push_back(result[k]);
}
}
Polygon sum_polygon;
sum_polygon.arr = unique_result;
sum_polygon.n = unique_result.size();
return sum_polygon;
}
vector<bool> contains_points(vector<vector2> points) {
rotate(arr.begin(), min_element(arr.begin(), arr.end()), arr.end());
auto it = max_element(arr.begin(), arr.end());
vector<vector2> lower (arr.begin(), it+1), upper (it, arr.end());
upper.push_back(arr[0]);
reverse(upper.begin(), upper.end());
if(upper[0].x == upper[1].x) upper.erase(upper.begin());
if(lower.back().x == lower[(int)lower.size()-2].x) lower.pop_back();
vector<bool> ans ((int)points.size());
sort(points.begin(), points.end());
int pl = 1, pu = 1;
ll L = lower[0].x, R = lower.back().x;
for(int i=0; i<(int)points.size(); i++){
if(points[i].x < L || points[i].x > R) continue;
while(lower[pl].x < points[i].x) pl++;
while(upper[pu].x < points[i].x) pu++;
if(ccw(lower[pl-1], points[i], lower[pl]) <= 0 && ccw(upper[pu-1], points[i], upper[pu]) >= 0){
ans[points[i].idx-1] = 1;
}
}
return ans;
}
void print() {
for (const auto& p : arr) {
printf("(%lld, %lld)\n", p.x, p.y);
}
}
};
int n;
Polygon A, B, C, D, E;
vector2 arr[500002];
int main(){
A.input(), B.input();
scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%lld %lld", &arr[i].x, &arr[i].y);
arr[i].x *= 2, arr[i].y *= 2, arr[i].idx = i;
}
C = A.minkowski_sum(B);
for(auto &p: C.arr) p.x/=2, p.y/=2;
for(auto &p: A.arr) p.x*=2, p.y*=2;
for(auto &p: B.arr) p.x*=-1, p.y*=-1;
reverse(B.arr.begin(), B.arr.end());
D = A.minkowski_sum(B);
for(auto &p: A.arr) p.x/=2, p.y/=2;
for(auto &p: B.arr) p.x/=-1, p.y/=-1;
reverse(B.arr.begin(), B.arr.end());
for(auto &p: B.arr) p.x*=2, p.y*=2;
for(auto &p: A.arr) p.x*=-1, p.y*=-1;
reverse(A.arr.begin(), A.arr.end());
E = A.minkowski_sum(B);
for(auto &p: B.arr) p.x/=2, p.y/=2;
for(auto &p: A.arr) p.x/=-1, p.y/=-1;
reverse(A.arr.begin(), A.arr.end());
// C.print();
// D.print();
// E.print();
vector<bool> Cb = C.contains_points(vector<vector2> (arr+1, arr+n+1));
vector<bool> Db = D.contains_points(vector<vector2> (arr+1, arr+n+1));
vector<bool> Eb = E.contains_points(vector<vector2> (arr+1, arr+n+1));
for(int i=0; i<n; i++){
printf("%c", (Cb[i] || Db[i] || Eb[i]) ? 'Y' : 'N');
}
}BOJ 25667. Kitten's Computer
문제를 요약하면 다음과 같다.
- $64$비트 정수를 담을 수 있는 $400$개의 레지스터 $a_1, a_2, \cdots, a_{400}$이 있다.
- 처음에 $a_1 = x, a_2 = y$가 담겨 있을 때, 일정 횟수의 비트 연산 뒤에 $a_1$에 $x \times y \mod 2^{64}$를 저장해야 한다.
- 비트 연산은 병렬로 시행할 수 있다. 병렬 연산 횟수가 어떻게 측정되는지는 지문을 참고하면 좋다. $70$스텝 안에 $100, 000$번의 연산 이내로 수행해야 한다.
어떻게 해야 할까? 일반적으로 곱셈은 여러 번의 덧셈을 통해 해결한다. 그러나 이 문제의 경우 병렬 연산으로 빠르게 덧셈을 하는 것도 문제고, 덧셈을 $y$번 할 수도 없는 것도 문제다. 이진수의 특성을 살려 생각해볼 수 있는 적당한 절충안은 다음과 같다.
- $y$의 $i$번째 비트가 켜져 있는 모든 $i$에 대해, $x \times 2^i$를 모두 더한다.
이 점에서 착안해 다음과 같이 $A_i$를 정의하자.
- $A_i$는 $y$의 $2^i$의 비트가 켜져 있으면 $x \times 2^i$, 아니라면 $0$이다.
이제 문제를 $A_i$를 구하는 단계와 $A_i$를 더하는 관계로 나눌 수 있을 것 같다. 그러나 $A_i$는 총 $64$개가 존재하고, 두 수를 더하는 것도 이 문제에서는 매우 어렵다. 두 수를 더할 수 있는 방법이 존재한다면, 이진 트리 형태로 병렬로 처리하는 것도 고려해볼 만 하지만, 레지스터의 수가 최대 $400$개라는 것이 또 걸린다.
$A_i$를 구하는 방법
$A_i$를 빠르게 구해 보자. 먼저 $y$의 $i$번째 비트가 켜져 있는지 확인해야 한다. 이걸 하려면 $64$개의 레지스터에 $2^0, \cdots, 2^{63}$을 차례대로 넣은 뒤, and 연산을 취해야 한다. 이렇게 하면 $y$의 $i$번째 비트를 모두 얻을 수 있다.
문제는 이 비트들은 각각 $i$번 비트 자리에만 존재한다는 것이다. 우리가 하고 싶은 것은 $x \times 2^i$, 즉 x << i를 저 비트에 따라 $0$으로 만드는 일이다. 따라서 다음과 같은 방식을 생각해 보자.
x << i를 두 스텝에 모두 계산해 둔다. 복제를 해두고 shift해야 한다.- $y$의 $i$번째 비트를 $i$번째 비트뿐만 아니라 다른 모든 왼쪽 비트에 복사해 둔다. (오른쪽 비트는 어차피
x<<i에서 $0$이기 때문에 안 해도 상관없다.)
여기서 첫 파트는 $2$스텝이 걸린다. 이와 무관하게 두 번째 파트는 영역을 두 배씩 늘려나가면 $2 \log_2 {64} = 12$ 스텝이 필요하다. 이 뒤에는 x << i와 두 번째 파트에서 계산한 결과에 and 연산을 하면 된다.
여기서 드는 총 스텝의 수를 계산해 보자. 과정을 대략 요약하면,
따라서 총 $16$ 스텝이 걸린다.
두 수를 더하는 방법
$64$개의 수를 더하기 위해서는 먼저 두 수를 더해야 한다. 두 수를 더할 수 있는 방법을 찾아보자. (놀랍게도 며칠 전 알고리즘 수업에서 이 내용을 들은 것이 도움이 되었다.) Kogge-Stone adder (Wikipedia) 등을 참고하였다.
두 수를 더하는 것을 이진수로 계산할 때, 보통은 병렬적인 방법보다는 직렬적인 방법을 쓴다. 오른쪽에서부터 시작해 비트를 하나씩 더하고, carry(받아올림)을 왼쪽으로 보내 준다.
이걸 병렬로 바로 처리한다고 생각해 보자. 두 수 $A$와 $B$를 더하고 싶을 때, 우리는 A & B를 carry로, A ^ B를 각 자리에 들어갈 원소로 생각할 수 있다. 이론적으로는 이 뒤에 (A & B) << 1을 더하는 것을 $64$번 더 반복하면 이진수 덧셈이 완성되지만, 그렇게 하면 너무 오래 걸린다.
이 문제를 해결하기 위해 조금 특이한 발상을 해야 한다. 내가 한 발상은 아니지만 대략적인 직관을 유추해보면 다음과 같다. 애초에 덧셈이라는 구조 자체가 워낙 직렬적인 구조라서 병렬로 계산하기가 어렵다. 그런데 우리는 어딘가에서 비슷한 것을 본 적이 있다. 바로 LCA이다. LCA 역시 매우 직렬적인 parent 함수를 functional graph로서 이용하지만, Sparse Table을 통해 병렬로 구조를 구축한다. 비슷한 식으로, 덧셈을 Sparse Table을 이용해 처리할 수 없을까?
스파스 테이블에 뭘 저장하면 좋을 지 떠올려 보기 위해, $sps[i][d]$를 일단 잡아 놓고 생각하자. 여기서 $sps[i][d]$는 $d$번째 step 이후의 정보가 들어가 있을 것이며, $i$번 비트부터 $i-2^d+1$번 비트 사이의 어떤 정보가 들어 있을 것이다. 여기서 자명하게 두 가지 정보가 필요함을 예측할 수 있다.
- 이 구간 내에서 carry가 저절로 생겨 $i$번 비트 직후까지 전파되는가?
- 이 구간 직전 위치에서 carry가 들어왔다면, $i$번 비트 직후까지 전파되는가?
의 두 정보임을 알 수 있다. 이 둘을 각각 $g[i][d]$와 $p[i][d]$라고 하자. (각각 generate bit과 propagate bit의 약자라고 한다.)
우선 초항을 생각해 보자. 이 케이스는 $A$와 $B$가 $1$비트라고 생각하고 진행해도 된다.
- $g$가 $1$이려면 이 구간 내에서 자동으로 carry가 생겨야 한다. 이런 경우는 $A=B=1$밖에 없다. 따라서 $g$는
A&B로 계산할 수 있다. - $p$가 $1$이라면 $A$나 $B$ 둘 중 하나만 $1$이어야 한다. 둘이 같은 경우는 원래 자리에 남는 수가 $0$이기 때문에, carry가 들어와도 $i$번 비트가 $0$에서 $1$로 바뀌고 끝난다. 따라서 $p$는
A^B로 계산할 수 있다.
위 식을 참고하면, 사실 $A$나 $B$가 $1$비트보다 더 커도 병렬적으로 저게 계산됨을 알 수 있다. $64$비트 정수에서 비트 연산을 하면 알맞는 비트끼리 연산이 되기 때문이다.
그런데 이 다음 전파를 어떻게 해야 할까? 모든 $i$에 대해 $g[i][d-1]$과 $p[i][d-1]$을 아는 상황에서, $g[i][d]$와 $p[i][d-1]$을 알 수 있는지 살펴보자.
만약 $g[i][d-1] = 1$이라면 $g[i][d]$도 당연히 $1$이다. 그러지 않고, $g[i-2^{d-1}][d-1] = 1$인 경우, $[i-2^{d-1}+1, i]$ 구간에서 저걸 넘겨 줄 수 있어야 하므로, $p[i][d-1]$도 $1$이면 $1$이 될 수 있다. 따라서, $g[i][d] = g[i][d-1] \or \left(g[i-2^{d-1}][d-1] \and p[i][d-1] \right)$.
$p[i][d]$는 자명히 $p[i][d-1] \and p[i-2^{d-1}][d-1]$이다.
이제 이걸 스파스 테이블 느낌으로 병렬 처리를 할 수 있다. $d$가 증가하는 각 스텝은 $3$번의 연산이 필요할 것이다. ($g$가 $3$스텝이 걸리기 때문이다. $p$는 $2$스텝에 되는데, $g$와 병렬로 계산해주면 되기 때문에 딱히 문제는 없다.) $i$가 너무 작은 경우 $i-2^{d-1}$이 없을 수 있는데, 그러면 그냥 $g$와 $p$ 값을 그대로 전파해 주면 될 것이다. ($3$스텝에는 $i-2^{d-1}$을 계산하기 위한 shift가 필요함을 주목하자.)
저걸 끝까지 구하고 나면 답은 또 어떻게 구하는지 생각해 봐야 한다. 저 과정을 $6$번 진행하면 처음에는 $1$이었던 구간의 길이가 $64$가 되기 때문에, 마지막까지의 정보를 얻을 수 있다. 여기서 정의에 의해 최후의 $g[i-1][d]$들은 뒤에서 carry가 오는지를 나타낼 것이다. 따라서 이걸 단순히 맨 처음에 구했던 $p[i][0]$과 XOR을 하게 되면 $i$번째 비트를 구할 수 있게 된다.
초항을 구하는데 $1$스텝, 그 후 $6$단계 동안 스파스 테이블 전파를 하는데 $18$스텝, 마지막에 $2$스텝으로 덧셈 한 번에 총 $21$번의 스텝이 필요하다.
여러 수 더하기
위 방법을 그대로 적용하면 이진 트리 형태의 병렬 덧셈을 시도할 수 있다. 그러나 이렇게 하는 경우 전체 횟수가 $16 + 6 \times 21 = 140$회가 되기 때문에 너무 많다. 따라서 수가 $64$개일 때부터 위 알고리즘을 적용하면 안 되고, 조금 더 효율적인 방법을 써야 한다. 이 문서를 참고해서 작성했다.
두 수를 더하는 이진 덧셈 알고리즘을 생각해 보면, 받아올림이 있기 때문에 어느 순간부터 세 수를 더하는 것과 동치가 됨을 알 수 있다. 그렇다면 아예 세 수 덧셈을 하면 어떨까? 이게 생각만큼 잘 되지는 않는다. 갑자기 받아올림이 $2$가 넘어가면 골치아프기 때문이다. 그런데 받아올림의 전파를 신경쓰지 않는다면 재미있는 것을 알 수 있다. $A$, $B$, $C$ 세 수를 더하는 경우 받아올림을 제외한 결과는 $A \oplus B \oplus C$가 될 것이다. 그런데 여기서 받아올림은 $A$, $B$, $C$ 셋 중 둘 이상이 $1$인 비트에서 일어난다. 이건 $(A \and B) \or (B \and C) \or (C \and A)$ 꼴로 계산하면 $3$ step에 구할 수 있고, 여기서 왼쪽으로 shift를 하나 하게 되면 $A, B, C$의 합은 이 두 수의 합으로 바뀐다. 따라서 수를 하나 줄이는 효과를 가져올 수 있다.
이렇게 수의 개수를 $4$ step에 대략 $\frac{2}{3}$으로 줄이는 방법이 생긴다. 이걸 적용하면 $64$개의 수를 $10$번의 reduction 끝에 $2$개의 수로 바꿀 수 있다.
지금까지의 총 step 개수는 $16 + 21 + 4 \times 10 = 77$으로, 여기서 $7$비트를 더 줄이면 정답이 된다.
7스텝 줄이기
여기서 7스텝을 줄이는 것도 어렵다. 전체적인 과정을 다시 정리해 보자.
여기서 $40$ 스텝 부분을 더 줄일 수 있다.
생각해 보면, $A, B, C$ 세 수를 두 수 $P, Q$로 바꾸는 과정에서 $P$는 $2$스텝만에, $Q$는 $4$스텝만에 얻을 수 있다. $P$가 나오는 즉시 재활용한다면 어떨까? 시뮬레이션을 해 보면 40 step을 30 step으로 줄일 수 있음을 알 수 있다.
이렇게 하면 문제를 해결할 수 있다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef int Reg;
namespace ControlRegister{
set<Reg> emptyReg;
void init(){
for(Reg i=3; i<=400; i++) emptyReg.insert(i);
}
Reg newReg(){
assert(emptyReg.size());
Reg ret = *emptyReg.begin(); emptyReg.erase(emptyReg.begin());
return ret;
}
void delReg(Reg x){
emptyReg.insert(x);
}
void _set(Reg a, Reg b){
printf("SET %d %d\n", a, b);
}
void _xor(Reg a, Reg b, Reg c){
printf("XOR %d %d %d\n", a, b, c);
}
void _and(Reg a, Reg b, Reg c){
printf("AND %d %d %d\n", a, b, c);
}
void _or(Reg a, Reg b, Reg c){
printf("OR %d %d %d\n", a, b, c);
}
void _not(Reg a, Reg b){
printf("NOT %d %d\n", a, b);
}
void _lsh(Reg a, int x){
printf("LSH %d %d\n", a, x);
}
void _rsh(Reg a, int x){
printf("RSH %d %d\n", a, x);
}
}
using namespace ControlRegister;
vector<Reg> toDelete;
struct Work{
int t;
Reg a, b, c, p, x, y, z;
Work(Reg a, Reg b, Reg c): a(a), b(b), c(c){
t = 0;
p = x = y = z = 0;
}
Reg work(){
t++;
if(t == 1){
p = newReg();
x = newReg();
y = newReg();
z = newReg();
_xor(p, a, b);
_and(x, a, b);
_and(y, b, c);
_and(z, c, a);
toDelete.push_back(a), toDelete.push_back(b);
return 0;
}
if(t == 2){
_xor(p, p, c);
_or(x, x, y);
toDelete.push_back(c), toDelete.push_back(y);
return p;
}
if(t == 3){
_or(x, x, z);
toDelete.push_back(z);
return 0;
}
if(t == 4){
_lsh(x, 1);
return x;
}
exit(1);
}
};
void clear(){
for(Reg x: toDelete) delReg(x);
toDelete.clear();
}
const int n = 64;
const int logn = 6;
int main(){
freopen("sol.txt", "w", stdout);
init();
Reg X = 1, Y = 2;
vector<Reg> toadd;
{ /// Step 1, 16 step
/// 1 만들어놓기
Reg one = newReg();
_not(one, one);
_rsh(one, n-1);
/// x 복제하고 시프트
int xsh[n];
for(int i=0; i<n; i++){
xsh[i] = newReg();
_set(xsh[i], X);
_lsh(xsh[i], i);
}
/// y 복제하고 시프트, 1과 AND
int ysh[n];
for(int i=0; i<n; i++){
ysh[i] = newReg();
_set(ysh[i], Y);
_rsh(ysh[i], i);
_and(ysh[i], ysh[i], one);
}
/// 비트 복제
int ycopy[n];
for(int i=0; i<n; i++){
ycopy[i] = newReg();
for(int j=0; j<logn; j++){
_set(ycopy[i], ysh[i]);
_lsh(ysh[i], 1<<j);
_or(ysh[i], ysh[i], ycopy[i]);
}
}
for(int i=0; i<n; i++) delReg(ycopy[i]);
/// AND
for(int i=0; i<n; i++){
_and(xsh[i], xsh[i], ysh[i]);
toadd.push_back(xsh[i]);
}
for(int i=0; i<n; i++) delReg(ysh[i]);
}
{ /// Step 2
vector<Work> works;
while(!works.empty() || (int)toadd.size() > 2){
while((int)toadd.size() >= 3){
int a = toadd.back(); toadd.pop_back();
int b = toadd.back(); toadd.pop_back();
int c = toadd.back(); toadd.pop_back();
works.push_back(Work(a, b, c));
}
for(int i=0; i<(int)works.size(); i++){
if(works[i].t == 4){
works.erase(works.begin() + i);
i--;
continue;
}
int tmp = works[i].work();
if(tmp) toadd.push_back(tmp);
}
clear();
}
}
{ /// Step 3
int A = toadd[0], B = toadd[1];
int p[logn+1], g[logn+1];
for(int i=0; i<=logn; i++) p[i] = newReg(), g[i] = newReg();
_and(g[0], A, B);
_xor(p[0], A, B);
for(int d=1; d<=logn; d++){
int x = newReg();
_set(x, g[d-1]);
_lsh(g[d-1], 1<<(d-1));
swap(x, g[d-1]);
_and(x, x, p[d-1]);
_or(g[d], g[d-1], x);
int y = newReg();
_set(y, p[d-1]);
_lsh(p[d-1], 1<<(d-1));
swap(y, p[d-1]);
_and(p[d], p[d-1], y);
delReg(x), delReg(y);
}
_lsh(g[logn], 1);
_xor(1, p[0], g[logn]);
}
}'문제풀이 > Problem Solving Diary' 카테고리의 다른 글
| Problem Solving Diary #29 (0) | 2024.12.29 |
|---|---|
| Problem Solving Diary #27 (0) | 2024.11.26 |
| Problem Solving Diary #26 (0) | 2024.11.15 |
| Problem Solving Diary #25 (0) | 2024.10.13 |
| Problem Solving Diary #24 (0) | 2024.07.08 |