아침에 일어나서 1, 2, 3번 풀고 밥 먹고 씻고 4, 5번 풀었다. 4번에서 뇌절한 거 빼고 괜찮았다.
대회가 대회인만큼 풀이는 최대한 자세하게, 코드까지 포함해서 작성한다.
1번. 다이어트
당연하게도 각 식당의 메뉴 중 가장 작은 $K$개를 먹어야 하는데, 짝을 잘 지어주는 것이 중요하다.
직관적으로 A 식당에서 칼로리가 많은 것을 B 식당에서 칼로리가 적은 것과 함께 먹어야 하고, 이는 실제로 정당한 풀이다.
증명하는 방법에는 여러 가지가 있을 수 있는데, 가장 쉬운 것은 exchange argument인 것 같다.
만약 $a_i < a_j$, $b_k < b_l$이 있어 $(a_i, b_k)$, $(a_j, b_l)$이 서로 짝을 이루고 있다면, 이를 $(a_i, b_l)$, $(a_j, b_k)$로 쌍을 바꾸는 것이 합의 최댓값을 감소시키는 방법이 된다. 이를 계속 반복하면 결국 원하는 결론을 얻고, 증명 끝. 다른 증명으로는 수학적 귀납법이 가능할 것으로 보인다. 코드는 매우 간단하다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | #include <bits/stdc++.h> #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); using namespace std; typedef long long int ll; typedef long double ldb; typedef complex<double> base; // mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const bool debug=false; const int mod=998244353; ll a[222222], b[222222], n, k, ans; void solve(void) { int i; cin>>n>>k; ans=0; for(i=1 ; i<=n ; i++) cin>>a[i]; sort(a+1, a+n+1); for(i=1 ; i<=n ; i++) cin>>b[i]; sort(b+1, b+n+1); for(i=1 ; i<=k ; i++) ans=max(ans, a[i]+b[k+1-i]); cout<<ans; } int main(void) { fio; int tc; cin>>tc; for(int i=1 ; i<=tc ; i++) { cout<<"Case #"<<i<<"\n"; solve(); cout<<"\n"; } return 0; } | cs |
2번. 카드 게임
(초고난이도 문제를 제외한) 게임 문제는 대부분 전형적인 풀이를 갖는다. 가장 대표적인 풀이는 특정 상태를 "선공승", "후공승"으로 분류하고, 이 상태를 동적 계획법으로 계산하는 것이다. 특정 상태가 선공승이 되려면, 선공이 도달할 수 있는 상태 중 하나라도 후공승이면 된다. 반대로, 특정 상태가 후공승이 되려면, 선공이 도달할 수 있는 상태가 모두 선공승이면 된다. 이를 기반으로 동적계획법 풀이를 생각해보자. $dp[i][j]$란 더미 $X$에서 아래 $i$개의 카드, 더미 $Y$에서 아래 $j$개의 카드가 남았을 때 선공승인지, 후공승인지 여부라고 하자. 선공승이면 1, 아니면 0이다. 이제 각 상태에서 선공이 할 수 있는 움직임을 따져보자.
$(i, j)$라는 상태에 있다면, $X[t+1] + \cdots + X[i] \le k$을 만족하는 $t$에 대하여 $(t, j)$로 이동할 수 있다.
또한, $Y[t+1] + \cdots + Y[j] \le k$를 만족하는 $t$에 대하여 $(i, t)$로 이동할 수 있다.
이러한 조건을 만족하는 $t$는 하나의 구간을 이루므로, 부분합 배열을 추가하여 각 DP 값을 $\mathcal{O}(1)$에 해결할 수 있다.
예를 들어, $X[t+1] + \cdots + X[i] \le k$를 만족하는 $t$가 $[u, i-1]$이라고 하자.
그러면 우리가 확인할 것은 $dp[u][j], dp[u+1][j], \cdots, dp[i-1][j]$ 중 $0$인 것이 존재하냐는 것이다.
이는 $dp[u][j]$부터 $dp[i-1][j]$까지의 합이 $i-u$와 같은지 파악하는 것과 같으며, 이는 부분합으로 가능하다.
$Y$의 경우도 마찬가지다. 또한, 이때 조건을 만족하는 $t$의 범위는 $X, Y$에 대한 부분합과 lower_bound 등으로 쉽게 구할 수 있다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 | #include <bits/stdc++.h> #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); using namespace std; typedef long long int ll; typedef long double ldb; typedef complex<double> base; // mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const bool debug=false; const int mod=998244353; int n, k, ans_1, ans_2; int a[3333], b[3333]; int psa[3333], psb[3333]; int cuta[3333], cutb[3333]; int dp[3005][3005]; // first start, who wins? int psx[3005][3005]; int psy[3005][3005]; void solve(void) { int i, j, c; cin>>n>>k; ans_1=0, ans_2=0; for(i=1 ; i<=n ; i++) cin>>a[i]; for(i=1 ; i<=n ; i++) cin>>b[i]; for(i=1 ; i<=n ; i++) psa[i]=psa[i-1]+a[i]; for(i=1 ; i<=n ; i++) psb[i]=psb[i-1]+b[i]; for(i=0 ; i<=n ; i++) { cuta[i]=lower_bound(psa, psa+n+1, psa[i]-k)-psa; cutb[i]=lower_bound(psb, psb+n+1, psb[i]-k)-psb; } dp[0][0]=1; psx[0][0]=1; psy[0][0]=1; for(i=0 ; i<=n ; i++) { for(j=0 ; j<=n ; j++) { if(i==0 && j==0) continue; bool canfin=false; if(i>=1) { int totlose=psx[i-1][j]; if(cuta[i]>=1) totlose-=psx[cuta[i]-1][j]; int totpos=i-cuta[i]; if(totlose<totpos) canfin=true; } if(j>=1) { int totlose=psy[i][j-1]; if(cutb[j]>=1) totlose-=psy[i][cutb[j]-1]; int totpos=j-cutb[j]; if(totlose<totpos) canfin=true; } if(canfin) dp[i][j]=1; else dp[i][j]=0; psx[i][j]=(i>=1?psx[i-1][j]:0)+dp[i][j]; psy[i][j]=(j>=1?psy[i][j-1]:0)+dp[i][j]; } } for(i=0 ; i<=n ; i++) { for(j=0 ; j<=n ; j++) { if(dp[i][j]) ans_1++; else ans_2++; } } cout<<ans_1<<" "<<ans_2; } int main(void) { fio; int i, tc; cin>>tc; for(i=1 ; i<=tc ; i++) { cout<<"Case #"<<i<<"\n"; solve(); cout<<"\n"; } return 0; } | cs |
3번. 사다리 게임
$N$의 범위가 작으므로, 아예 $i$에서 $j$로 가기 위한 최소 간선 삭제 횟수를 $dp[i][j]$라고 정의하자. 이를 전부 구하는 것을 목표로 한다.
초깃값을 설정해야 하는데, $dp[i][i]=0$, $dp[i][j] = \infty$ ($j \neq i$) 가 된다. 이제 DP 업데이트를 어떻게 하는지 생각하자.
만약 $u, v$를 연결하는 간선이 있다면, $u$로 도착한 경로는 강제로 $v$로 가게 된다. 반대 역시 마찬가지.
그러니 $dp[i][u] = \text{min}(dp[i][u]+1, dp[i][v])$, $dp[i][v]=\text{min}(dp[i][v]+1, dp[i][u])$가 성립하게 된다.
물론, 이 업데이트를 순서대로 하면 안되고, 동시에 적용해야 한다. 그러니 업데이트가 간선 하나 당 $\mathcal{O}(N)$이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | #include <bits/stdc++.h> #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); using namespace std; typedef long long int ll; typedef long double ldb; typedef complex<double> base; // mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const bool debug=false; const int mod=998244353; ll ans=0; int n, k, m, inf=1e9; int dp[1511][1511]; void solve(void) { int i, j, u, v, a, b; ans=0; cin>>n>>k>>m; for(i=1 ; i<=n ; i++) for(j=1 ; j<=n ; j++) dp[i][j]=inf; for(i=1 ; i<=n ; i++) dp[i][i]=0; while(k--) { cin>>u>>v; for(i=1 ; i<=n ; i++) { a=dp[i][u]; b=dp[i][v]; dp[i][u]=min(a+1, b); dp[i][v]=min(b+1, a); } } while(m--) { cin>>u>>v; if(dp[u][v]==inf) ans--; else ans+=dp[u][v]; } cout<<ans; } int main(void) { fio; int i, tc; cin>>tc; for(i=1 ; i<=tc ; i++) { cout<<"Case #"<<i<<"\n"; solve(); cout<<"\n"; } return 0; } | cs |
4번. 범위 안의 숫자
뭔가 지나치게 어렵게 푼 것 같다. 고생도 많이했다. 이상한 실수해서 제출횟수도 날리고 ㅋㅋ
우리가 해야 할 일은, 어떤 정수를 추가하고, 삭제하고, 길이 $m$ 구간에 속하는 정수의 최대 개수를 구하는 것이다.
여기서 첫 관찰은, 집합에 존재하는 정수로 시작하는 구간만을 생각해도 충분하다는 것이다. 이는 자명한 사실이므로 설명 생략.
먼저 집합에 등장할 수 있는 정수들을 전부 구하고, 이들을 정렬한 상태로 보관하자. 총 $\mathcal{O}(nk)$개가 있다.
이제 각 정수에 대하여 "그 정수로 시작하는 길이 $m$ 구간에 속한 정수의 개수"를 세그먼트 트리로 관리해보자.
특정 정수를 추가/삭제하면, 그에 따라 영향을 받는 값의 index는 하나의 구간을 이룬다. 이제 해결의 실마리가 나온다.
필요한 것은 구간에 1을 더하는 것, 1을 빼는 것, 그리고 전체의 최댓값을 구하는 연산이다. 모두 lazy propagation으로 가능하다.
하지만 이 풀이는 시간 초과가 난다. (아니라는 말도 있다) $nk$가 생각보다 크고, lazy propagation은 상수가 꽤 크기 때문이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 | #include <bits/stdc++.h> #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); using namespace std; typedef long long int ll; typedef long double ldb; typedef complex<double> base; // mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const bool debug=false; const int mod=998244353; struct SegmentTree { int tree[2288888]; int lazy[2288888]; void build(void) { memset(tree, 0, sizeof(tree)); memset(lazy, 0, sizeof(lazy)); } void workdown(int index, int s, int e) { if(s!=e) { lazy[index<<1]+=lazy[index]; tree[index<<1]+=lazy[index]; lazy[index<<1|1]+=lazy[index]; tree[index<<1|1]+=lazy[index]; } lazy[index]=0; } void update(int index, int s, int e, int l, int r, int v) { if(l>e || r<s) return; workdown(index,s,e); if(l<=s && e<=r) { lazy[index]+=v; tree[index]+=v; return; } int m=(s+e)>>1; update(index<<1,s,m,l,r,v); update(index<<1|1,m+1,e,l,r,v); tree[index]=max(tree[index<<1], tree[index<<1|1]); } int eval(int index, int s, int e, int l, int r) { if(l>e || r<s) return -1e9; workdown(index, s, e); if(l<=s && e<=r) return tree[index]; int m=(s+e)>>1; int ret=max(eval(index<<1,s,m,l,r), eval(index<<1|1,m+1,e,l,r)); tree[index]=max(tree[index<<1], tree[index<<1|1]); return ret; } } ST; string s; int c[51111]; int ans, n, m, k, pt[10]; vector<int> POS; vector<int> RNG; void ins(int x) { POS.push_back(x); for(int i=0 ; i<k ; i++) POS.push_back(x-x%pt[i+1]+x%pt[i]+pt[i]); } void upd(int x, int v) { int tt=lower_bound(POS.begin(), POS.end(), x)-POS.begin(); ST.update(1, 1, POS.size(), RNG[tt]+1, tt+1, v); } void rv(int loc, int v) { int i, ini=0; for(i=max(1, loc-k+1) ; i<=max(1, loc-k+1)+k-1 ; i++) ini=10*ini+c[i]; upd(ini, v); for(i=max(1, loc-k+1)+k ; i<=min(loc+k-1, n) ; i++) { ini=10*(ini-((c[i-k]*pt[k-1])))+c[i]; upd(ini, v); } } void solve(void) { int i, j, ini=0, et; ans=0; cin>>n>>k>>m>>s; POS.clear(); RNG.clear(); ST.build(); pt[0]=1; for(i=1 ; i<=k ; i++) pt[i]=10*pt[i-1]; for(i=1 ; i<=n ; i++) c[i]=s[i-1]-'0'; for(i=1 ; i<=k ; i++) ini=10*ini+c[i]; ins(ini); for(i=k+1 ; i<=n ; i++) { ini=10*(ini-((c[i-k]*pt[k-1])))+c[i]; ins(ini); } sort(POS.begin(), POS.end()); POS.erase(unique(POS.begin(), POS.end()), POS.end()); RNG.resize(POS.size()); for(i=0 ; i<POS.size() ; i++) RNG[i]=lower_bound(POS.begin(), POS.end(), POS[i]-m)-POS.begin(); ini=0; for(i=1 ; i<=k ; i++) ini=10*ini+c[i]; upd(ini, 1); for(i=k+1 ; i<=n ; i++) { ini=10*(ini-((c[i-k]*pt[k-1])))+c[i]; upd(ini, 1); } ans=max(ans, ST.eval(1, 1, POS.size(), 1, POS.size())); for(i=1 ; i<=n ; i++) { rv(i, -1); et=c[i]; c[i]=1; rv(i, 1); ans=max(ans, ST.eval(1, 1, POS.size(), 1, POS.size())); rv(i, -1); c[i]=et; rv(i, 1); } cout<<ans; return; } int main(void) { fio; int i, tc; cin>>tc; for(i=1 ; i<=tc ; i++) { cout<<"Case #"<<i<<"\n"; solve(); cout<<"\n"; } return 0; } | cs |
그래서 최적화를 할 방법을 생각했다. 사실 가장 중요한 부분은, 각 업데이트 이후 확인해야 하는 구간이 많이 겹친다는 것이다.
숫자를 1로 바꾸기 전, 초기 $n-k+1$개의 정수 중 실제로 변화하는 것은 많아야 $k$개다. 이 점을 위 코드는 활용하지 않는다.
그러니, 위 레이지 세그먼트 트리를 초기 $n-k+1$개의 정수 중 하나로 시작하는 구간에 대해서만 만들어주자. 이러면 크기가 $\mathcal{O}(nk)$에서 $\mathcal{O}(n)$으로 줄어든다. 이제 우리가 걱정해야 하는 것은 "새로 추가되는 정수로 시작되는 길이 $m$ 구간"에 속하는 정수의 개수를 구하는 것이다. 이 구간에 속하는 정수 역시 "기존 $n-k+1$개의 정수"와 "새로 추가되는 정수"로 구분될 수 있는데, 후자는 단순하게 $\mathcal{O}(k^2)$으로 계산해도 간단한 계산이므로 충분히 빠르다. 전자의 경우, 기존 $n-k+1$개 정수의 등장 횟수를 Fenwick Tree로 관리하면 간단하게 계산할 수 있다. 특정 구간 내에 존재하는 정수의 개수를 구하면 되므로, lower_bound와 Fenwick Tree의 구간 쿼리를 통해서 계산할 수 있다. 시간복잡도는 크게 다르지 않으나, 최적화가 꽤 많이 된 코드이므로 훨씬 빠르다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 | #include <bits/stdc++.h> #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); using namespace std; typedef long long int ll; typedef long double ldb; typedef complex<double> base; // mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const bool debug=false; const int mod=998244353; struct SegmentTree { int tree[288888]; int lazy[288888]; void build(void) { memset(tree, 0, sizeof(tree)); memset(lazy, 0, sizeof(lazy)); } void workdown(int index, int s, int e) { if(s!=e) { lazy[index<<1]+=lazy[index]; tree[index<<1]+=lazy[index]; lazy[index<<1|1]+=lazy[index]; tree[index<<1|1]+=lazy[index]; } lazy[index]=0; } void update(int index, int s, int e, int l, int r, int v) { if(l>e || r<s) return; workdown(index,s,e); if(l<=s && e<=r) { lazy[index]+=v; tree[index]+=v; return; } int m=(s+e)>>1; update(index<<1,s,m,l,r,v); update(index<<1|1,m+1,e,l,r,v); tree[index]=max(tree[index<<1], tree[index<<1|1]); } int eval(int index, int s, int e, int l, int r) { if(l>e || r<s) return -1e9; workdown(index, s, e); if(l<=s && e<=r) return tree[index]; int m=(s+e)>>1; int ret=max(eval(index<<1,s,m,l,r), eval(index<<1|1,m+1,e,l,r)); tree[index]=max(tree[index<<1], tree[index<<1|1]); return ret; } } ST; struct Fenwick { int tree[111111], C=50000; void rset(void) { memset(tree, 0, sizeof(tree)); } void update(int x, int v) { while(x<=C) { tree[x]+=v; x+=(x&-x); } } int query(int x) { int ret=0; while(x) { ret+=tree[x]; x-=(x&-x); } return ret; } int rquery(int l, int r) { return query(r)-query(l-1); } } T; string s; int c[51111]; int ans, n, m, k, pt[10]; vector<int> POS; vector<int> AT; void ins(int x) { POS.push_back(x); } void upd(int x, int v, int ex) { int t_1=lower_bound(POS.begin(), POS.end(), x-m)-POS.begin()+1; int t_2=upper_bound(POS.begin(), POS.end(), x)-POS.begin(); ST.update(1, 1, POS.size(), t_1, t_2, v); if(ex) { T.update(t_2, v); } } void rv(int loc, int v, int ex) { int i, ini=0; AT.clear(); for(i=max(1, loc-k+1) ; i<=max(1, loc-k+1)+k-1 ; i++) ini=10*ini+c[i]; upd(ini, v, ex); if(v==1 && ex==0) AT.push_back(ini); for(i=max(1, loc-k+1)+k ; i<=min(loc+k-1, n) ; i++) { ini=10*(ini-((c[i-k]*pt[k-1])))+c[i]; upd(ini, v, ex); if(v==1 && ex==0) AT.push_back(ini); } } void do_fun_work(void) { int i, j, ac; for(i=0 ; i<AT.size() ; i++) { int t_1=lower_bound(POS.begin(), POS.end(), AT[i])-POS.begin()+1; int t_2=upper_bound(POS.begin(), POS.end(), AT[i]+m)-POS.begin(); ac=T.rquery(t_1, t_2); for(j=0 ; j<AT.size() ; j++) if(AT[i]<=AT[j] && AT[j]<=AT[i]+m) ac++; ans=max(ans, ac); } } void solve(void) { int i, j, ini=0, et; ans=0; cin>>n>>k>>m>>s; POS.clear(); ST.build(); T.rset(); pt[0]=1; for(i=1 ; i<=k ; i++) pt[i]=10*pt[i-1]; for(i=1 ; i<=n ; i++) c[i]=s[i-1]-'0'; for(i=1 ; i<=k ; i++) ini=10*ini+c[i]; ins(ini); for(i=k+1 ; i<=n ; i++) { ini=10*(ini-((c[i-k]*pt[k-1])))+c[i]; ins(ini); } sort(POS.begin(), POS.end()); POS.erase(unique(POS.begin(), POS.end()), POS.end()); ini=0; for(i=1 ; i<=k ; i++) ini=10*ini+c[i]; upd(ini, 1, 1); for(i=k+1 ; i<=n ; i++) { ini=10*(ini-((c[i-k]*pt[k-1])))+c[i]; upd(ini, 1, 1); } ans=max(ans, ST.eval(1, 1, POS.size(), 1, POS.size())); for(i=1 ; i<=n ; i++) { rv(i, -1, 1); et=c[i]; c[i]=1; rv(i, 1, 0); ans=max(ans, ST.eval(1, 1, POS.size(), 1, POS.size())); do_fun_work(); rv(i, -1, 0); c[i]=et; rv(i, 1, 1); } cout<<ans; } int main(void) { fio; int i, tc; cin>>tc; for(i=1 ; i<=tc ; i++) { cout<<"Case #"<<i<<"\n"; solve(); cout<<"\n"; } return 0; } | cs |
5번. 우범 지역
평행이동을 통해서 점 $Q$를 원점으로 옮기고 시작하자. 원점을 기준으로 나머지 점들을 각도정렬하자.
컨벡스 헐 안에 $Q$가 있을 확률은 구하기 어렵지만, $Q$가 없을 확률은 구하기 상대적으로 쉽다.
$Q$가 없을 필요충분조건은, 결국 선택한 점들이 이루는 각도 범위가 180도 미만인 것이기 때문이다.
우선 이를 기반으로 답이 $0$인지 아닌지는 쉽게 판단할 수 있다. 이를 먼저 처리해주자.
이제 점들을 각도순으로 $P_1, P_2, \cdots, P_n$이라 하고, 그 선택 확률을 $p_1, p_2, \cdots , p_n$이라 하자.
각도 범위가 180도 미만인 경우, "시계 방향으로 처음 선택된 정점"을 직관적으로 정의할 수 있다.
위 그림에서는 오른쪽 아래에 있는 정점이 "처음 선택된 정점"이다. 이제 $P_i$가 처음 선택된 정점이라고 하자.
그 후, $P_i$부터 $P_j$까지의 각도 범위가 180도 미만인 최대의 $j$를 선택하자. 여기서 index가 한 바퀴 돌 수 있음에 주의하자.
이를 쉽게 짜기 위해서는, $P_1, P_2, \cdots , P_n$의 정보를 $P_{n+1} , P_{n+2}, \cdots, P_{2n}$에 복사해서 사용하면 된다.
이제 이렇게 되면 $P_{j+1}, P_{j+2}, \cdots , P_{i+n-1}$은 사용될 수 없다. 즉, 우리가 만족해야 하는 조건은 다음과 같다.
우선 $P_i$를 선택해야 한다. 그 확률은 $p_i$이다.
$P_{j+1}$부터 $P_{i+n-1}$은 사용되지 않는다. 그 확률은 $(1-p_{j+1}) \cdots (1-p_{i+n-1})$이다.
그러니 두 확률의 곱을 "Q가 컨벡스 헐에 포함되지 않을 확률"에 추가하면 된다.
또한, 모든 점이 선택되지 않을 확률 역시 추가되어야 한다. 이러면 모든 확률을 중복없이 다루게 된다.
이 풀이의 매우 많은 부분은 $Q$와 $P_i, P_j$가 한 직선 위에 있지 않다는 사실에 기반한다.
위 계산을 효율적으로 할 방법을 생각해보자. 우선 $j$를 계산하는 것은 inchworm의 방식으로 쉽게 할 수 있다.
또한, $1-p$의 연속된 곱을 효율적으로 계산하는 것은 간단한 세그먼트 트리로 할 수 있다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 | #include <bits/stdc++.h> #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); using namespace std; typedef long long int ll; typedef long double ldb; typedef complex<double> base; // mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const bool debug=false; const int mod=998244353; ll n, qx, qy, C=210000; ldb tree[444444]; ldb ans, p[222222]; pair< pair<ll, ll>, ldb> PT[222222]; ll cross(const pair<ll, ll> &a, const pair<ll, ll> &b) { return a.first*b.second-a.second*b.first; } bool cmp(const pair< pair<ll, ll>, ldb> &X, const pair< pair<ll, ll>, ldb> &Y) { if((X.first>make_pair(0LL, 0LL)) ^ (Y.first>make_pair(0LL, 0LL))) return X.first > Y.first; return cross(X.first, Y.first) > 0; } void update(int loc, ldb t) { loc+=C; tree[loc]=t; for( ; loc>1 ; loc>>=1) tree[loc>>1]=tree[loc]*tree[loc^1]; } ldb query(int l, int r) { ldb ret=1.0; for(l+=C, r+=C ; l<r ; l>>=1, r>>=1) { if(l&1) ret=ret*tree[l++]; if(r&1) ret=ret*tree[--r]; } return ret; } ldb getR(int L, int R) { if(R<=n) return query(1, L)*query(R+1, n+1); if(R>n) return query(R-n+1, L); } void solve(void) { fio; ll i, j; cin>>n; ans=0.0; memset(tree, 0, sizeof(tree)); for(i=1 ; i<=n ; i++) cin>>PT[i].first.first; for(i=1 ; i<=n ; i++) cin>>PT[i].first.second; for(i=1 ; i<=n ; i++) cin>>PT[i].second; cin>>qx>>qy; for(i=1 ; i<=n ; i++) PT[i].first.first-=qx; for(i=1 ; i<=n ; i++) PT[i].first.second-=qy; sort(PT+1, PT+n+1, cmp); if(cross(PT[1].first, PT[n].first) > 0) { cout<<0.0; return; } for(i=1 ; i<=n ; i++) PT[i+n]=PT[i]; for(i=1 ; i<=2*n ; i++) update(i, 1.0-PT[i].second); for(i=1, j=1 ; i<=n ; i++) { while(j<=2*n && cross(PT[i].first, PT[j].first)>=0) j++; j--; ans+=PT[i].second*getR(i, j); } ldb tt=1.0; for(i=1 ; i<=n ; i++) tt=(tt*(1.0-PT[i].second)); ans=1.0-ans-tt; cout<<fixed<<setprecision(15)<<ans; } int main(void) { fio; int i, tc; cin>>tc; for(i=1 ; i<=tc ; i++) { cout<<"Case #"<<i<<"\n"; solve(); cout<<"\n"; } return 0; } | cs |
'PS > 대회 후기' 카테고리의 다른 글
| ACM-ICPC Seoul Regional Preliminary 2020 (0) | 2020.10.19 |
|---|---|
| SCPC 2020 2차 예선 풀이 (1) | 2020.09.05 |
| APIO 2020 Open Contest (0) | 2020.08.22 |
| ACM-ICPC Seoul Regional 2019 (0) | 2019.11.11 |
| 나는 코더다 2018 송년대회 (5) | 2018.12.22 |