http://apio-olympiad.org/2016/
https://oj.uz/problems/source/184
https://koosaga.com/113
3. Gap
Subtask 1
한번에 양 끝의 값 2개씩 알아간다고 생각하자. 지금 아는 끝값으로 쿼리를 날리면 그 다음 끝값 2개를 알 수 있다. 사용하는 쿼리의 개수는 ceil(N/2) 개로, 30점을 받 수 있다.
Subtask 2
Subtask 2에서는 쿼리의 개수만 중요한 것이 아니라, 한 쿼리가 적은 수들을 덮고 있어야 한다.
만점을 얻기 위해서는 한가지 중요한 관찰이 필요하다.
일단 첫번째 쿼리로 최소값과 최대값 s, e를 구했다고 생각하자.
[s, e] 구간 안에 gap들은 N-1개가 있으니, max gap < (e-s)/(N-1) 의 상황이 가능할까?
max gap < (e-s)/(N-1) 이니, sum gap = e-s < (e-s)/(N-1)*(N-1) = e-s 로 모순이다.
즉, max gap >= (e-s)/(N-1) 이니, (e-s)/(N-1)를 사이즈로 하는 버킷으로 전체 [s, e]구간을 커팅해주면 한 버킷 안에 max gap 은 존재할 수 없다. 이제, 각 버킷에 대해서 쿼리를 날리고, 버킷의 양 끝값을 알고 있으면 된다.
사용하는 쿼리의 개수는 처음에 1개 + 버킷 N-1개 / 쿼리가 덮는 수들의 수는 처음에 N개, 버킷의 합이 N개로, 총합 3N개 만점을 받을 수 있다.
N=2일때는 특히 예외처리를 해 주어야 한다.
코드 접기
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
#include "gap.h"
#include < bits/ stdc+ + .h>
using namespace std ;
typedef long long ll;
typedef pair < int , int > pii;
typedef pair < ll, ll> pll;
const int MAXN = 1e5 ;
int T, N;
ll A[MAXN+ 10 ], ans;
ll findGap(int _T, int _N)
{
int i, j;
T= _T; N= _N;
if (T= = 1 )
{
ll s= 0 , t= 1e18 ;
for (i= 1 , j= N; i< = j; i+ + , j- - )
{
ll a, b;
MinMax(s, t, & a, & b);
A[i]= a; A[j]= b;
s= a+ 1 ; t= b- 1 ;
}
for (i= 2 ; i< = N; i+ + ) ans= max(ans, A[i]- A[i- 1 ]);
return ans;
}
else
{
ll s, e;
MinMax(0 , 1e18 , & s, & e);
if (N= = 2 ) return e- s;
ll g= (e- s+ N- 2 )/ (ll)(N- 1 );
ll a, b, p= s, q= s+ g;
vector < pll> V;
while (1 )
{
if (p> e) break ;
if (p> q) break ;
MinMax(p, q, & a, & b);
if (a! = - 1 ) V.push_back ({a, b});
p= q+ 1 ; q= p+ g;
q= min(q, e);
}
//for(i=0; i<V.size(); i++) printf("%lld %lld\n", V[i].first, V[i].second);
for (i= 1 ; i< V.size (); i+ + ) ans= max(ans, V[i].first- V[i- 1 ].second);
return ans;
}
}
cs
접기
1. Boat
이 문제는 DP로 해결된다. (+조합)
가장 중요한 것은 각 보트마다 어떤 구간에 속하는지를 선택해놓으면 경우의 수가 정해진다.
일단 첫번째로, [Ai, Bi]를 [Ai, Bi+1) 꼴로 바꾼 다음, 모든 값들을 좌표압축하여 구간 2N개로 쪼갠다.
따라서 DP를 다음과 같이 정의하자.
DP[i][a] = i번 보트를 0개 초과 내보내고, 그 개수가 구간 a에 포함될 때의 경우의 수
이제 열심히 상태 전이 식을 세워보자.
지금 (i, a) 를 선택했으니, 전 선택이 a인 경우는 따로 처리하고 (i-1, a-1) 일 때를 생각하자.
i바로 전에 선택한 보트가 j라 하면 dp(i, a) = sum(dp(j, 1~a-1))*C 가 된다.
이때 C는 j+1~i번째의 보트들이 선택이 되지 않거나, 선택되면 a구간의 수들일 때이다.
만약 여기서 k개의 보트들이 선택되는 보트이고, p는 j+1~i 에서 구간 a를 포함하는 보트들의 수라 하자.
x개를 선택하고 싶다면 경우의 수는 p-1Cx-1*aCx (i번째 보트는 무조건 선택해야 하기 때문) 이다.
즉, f[x]=sum(x-1Ci-1*aCi-1) 꼴로 표현될 수 있다.
지금 구해야 하는 값들은 a<=b<=500 의 aCb와 정해진 a<=10^9 , b<=500 의 aCb이다. 첫번째 값들은 N^2 전처리를 통해 구할 수 있고, 뒤의 값은 mod inv 를 모두 구해논 뒤, N/1, N/1 * (N-1)/2, N/1 * (N-1)/2 * (N-2)/3 처럼 식을 통해서 계산할 수 있다. 이를 효율적으로 하기 위해서는 구간의 길이 a가 정해져야 하기 때문에, 2차원 dp배열을 한 세로줄씩 구해가면 된다.
첫번째 줄은 예외 처리를 잘 해주어야 한다.
시간 복잡도 : O(N^3)
코드 접기
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
#include < bits/ stdc+ + .h>
using namespace std ;
typedef long long ll;
typedef pair < int , int > pii;
typedef pair < ll, ll> pll;
const int MAXN = 1000 ;
const ll MOD = 1e9 + 7 ;
int N, S, A[MAXN+ 10 ], B[MAXN+ 10 ];
vector < int > comp;
ll inv[MAXN+ 10 ], bino[MAXN+ 10 ][MAXN+ 10 ], comb[MAXN+ 10 ], f[MAXN+ 10 ];
ll dp[MAXN+ 10 ][MAXN+ 10 ], ans;
int getcomp(int x) { return lower_bound(comp.begin (), comp.end (), x)- comp.begin (); }
ll mypow(ll x, ll y)
{
if (y= = 0 ) return 1 ;
if (y%2 ) return mypow(x, y- 1 )* x%MOD;
ll t= mypow(x, y/ 2 );
return t* t%MOD;
}
int main()
{
int i, j, k;
bino[0 ][0 ]= 1 ;
for (i= 1 ; i< = MAXN; i+ + ) for (j= 0 ; j< = i; j+ + )
{
if (j= = 0 | | j= = i) bino[i][j]= 1 ;
else bino[i][j]= (bino[i- 1 ][j]+ bino[i- 1 ][j- 1 ])%MOD;
}
inv[0 ]= 1 ;
for (i= 1 ; i< = MAXN; i+ + ) inv[i]= mypow(i, MOD- 2 );
scanf ("%d" , & N);
for (i= 1 ; i< = N; i+ + )
{
scanf ("%d%d" , & A[i], & B[i]); B[i]+ + ;
comp.push_back (A[i]);
comp.push_back (B[i]);
}
comp.push_back (0 );
sort(comp.begin (), comp.end ());
comp.erase(unique(comp.begin (), comp.end ()), comp.end ());
S= comp.size ()- 2 ;
ll a= comp[2 ]- comp[1 ];
memset(comb, 0 , sizeof (comb)); memset(f, 0 , sizeof (f));
comb[0 ]= 1 ;
for (j= 1 ; j< = min((ll)N, a); j+ + ) comb[j]= comb[j- 1 ]* (a- j+ 1 )%MOD* inv[j]%MOD;
for (j= 1 ; j< = N; j+ + )
{
for (k= 1 ; k< = j; k+ + )
{
f[j]+ = comb[k]* bino[j- 1 ][k- 1 ]%MOD;
f[j]%= MOD;
}
}
int cnt= 0 ;
for (i= 1 ; i< = N; i+ + )
{
if (! (A[i]< = comp[1 ] & & comp[1 ]< B[i])) continue ;
cnt+ + ;
dp[i][1 ]= f[cnt];
}
dp[0 ][1 ]= 1 ;
for (i= 2 ; i< = S; i+ + )
{
dp[0 ][i]= 1 ;
a= comp[i+ 1 ]- comp[i];
memset(comb, 0 , sizeof (comb)); memset(f, 0 , sizeof (f));
comb[0 ]= 1 ;
for (j= 1 ; j< = min((ll)N, a); j+ + ) comb[j]= comb[j- 1 ]* (a- j+ 1 )%MOD* inv[j]%MOD;
for (j= 1 ; j< = N; j+ + )
{
for (k= 1 ; k< = j; k+ + )
{
f[j]+ = comb[k]* bino[j- 1 ][k- 1 ]%MOD;
f[j]%= MOD;
}
}
for (j= 1 ; j< = N; j+ + )
{
if (! (A[j]< = comp[i] & & comp[i]< B[j])) { dp[j][i]= dp[j][i- 1 ]; continue ; }
int cnt= 1 ;
for (k= j- 1 ; k> = 0 ; k- - )
{
dp[j][i]+ = f[cnt]* dp[k][i- 1 ]%MOD;
dp[j][i]%= MOD;
if (A[k]< = comp[i] & & comp[i]< B[k]) cnt+ + ;
}
dp[j][i]+ = dp[j][i- 1 ]; dp[j][i]%= MOD;
}
}
//for(i=1; i<=N; i++) { for(j=1; j<=S; j++) printf("%lld ", dp[i][j]-dp[i][j-1]); printf("\n"); }
for (i= 1 ; i< = N; i+ + ) ans+ = dp[i][S], ans%= MOD;
printf ("%lld" , ans);
}
cs
접기
2. Fireworks
일단 Subtask 2를 tree dp를 이용하여 해결할 수 있다.
