B
Subtask 1 : $x = 1$
구슬을 흘려보냈을 때 도착하는 위치는 왼쪽으로 이동할 때 1칸만 이동할 수 있으므로, amortized $O(1)$에 업데이트할 수 있습니다.
따라서 현재 도착 위치에서 다음 도착 위치를 naive하게 구해주어도 $O(N+Q)$에 문제가 해결됩니다.
Subtask 2 : $N, Q \le 5000$
쿼리가 주어질 때마다 다음 배열이 어떻게 되는지 $O(N)$에 다양한 방법으로 구할 수 있습니다. 따라서 시간복잡도는 $O(NQ)$입니다.
Subtask 3 : 추가 제약 조건 없음
stack을 이용하여 문제를 해결합니다. 각 $A[i]$에 $i$를 더해준 후, 스택을 활용해 최댓값이 업데이트되는 부분을 저장합니다. 그 후 그 지점을 중심으로 그 지점의 원래 높이와 주변 높이가 같아질 때까지 흘려야 하는 구슬의 수, 다음 지점을 넘어가지 않고 흘릴 수 있는 최대 구슬의 수를 미리 계산해놓으면 스위핑을 통해 문제를 해결할 수 있습니다.
#include <iostream>
#include <stack>
#include <string>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cassert>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
ll V[500002];
ll pf[500002], th[500002];
vector<ll> qry;
int main()
{
ios::sync_with_stdio(false); cin.tie(NULL);
int n, q; cin >> n >> q;
for(int i=1;i<=n;i++) {
cin >> V[i];
V[i] += i-1;
}
V[n+1] = INF;
ll now = 0;
for(int i=1;i<=q;i++) {
int t; cin >> t;
if(t == 1) {
ll x; cin >> x;
now += x;
}
if(t == 2) {
qry.push_back(now);
}
}
pf[0] = 0;
for(int i=1;i<=n;i++) pf[i] = pf[i-1] + V[i];
int st = 1;
vector<int> v;
v.push_back(st);
for(int i=2;i<=n;i++) {
if(V[i] > V[st]) {
st = i;
v.push_back(i);
}
}
vector<ll> v2, v3;
int m = (int)v.size();
v2.resize(m);
v3.resize(m);
v.push_back(n+1);
v2[0] = 0;
v3[0] = 0;
for(int i=0;i<m;i++) {
v2[i] = (v[i+1] - 1) * V[v[i]] - pf[v[i+1]-1];
v3[i] = V[v[i]] * v[i] - pf[v[i]];
}
int k = (int)qry.size();
vector<ll> ans(k);
now = 0;
for(int i=0;i<k;i++) {
while(now < m - 1 && v3[now+1] <= qry[i]) now++;
if(qry[i] >= v2[now]) ans[i] = (qry[i] - v2[now])/(v[now+1] - 1) + V[v[now]];
else ans[i] = V[v[now]];
cout << ans[i] << "\n";
}
}C
Subtask 1,2 : $N \le 8, 9$
각 칸을 돌면서, 위의 두 줄(노란색 칸)이 개발되었는지 여부를 2N개의 bit로 저장하는 bitmask DP를 진행합니다.
$dp[bit][H][i] := $ 노란색 칸의 개발 여부를 $bit$, 현재 칸의 위치를 $H$, 지금까지 추가로 개발한 지역의 개수를 $i$라고 할 때 도시로 확인된 구역들의 관광가치의 최대 합
가능한 비트열의 수는 $2^{2N}=4^N$개이고, 이 dp를 $N^2$ 칸과 $K$개의 상태에 대해 진행합니다.
총 시간복잡도는 $O(KN^24^N)$이 됩니다.
그대로 구현하면 $N \le 8$인 데이터를 맞을 수 있으며, 토글링 기법을 통한 메모리 최적화 및 효율적인 구현을 통해 $N \le 9$까지 풀 수 있습니다.
Subtask 3,4 : $N \le 10, 11$
기본적으로 비슷한 아이디어의 dp를 진행할 수 있습니다. 2가지 상태의 bit 대신 각 칸이 아래와 같은 3가지 상태를 가질 수 있습니다.
- 0 : 개발되지 않음
- 1 : 개발되었으나, 도시가 될 가능성이 없음
- 2 : 개발되었으며 도시가 될 가능성이 있음
상태를 3가지로 늘릴 경우 미리 가능성을 판별할 수 있기 때문에, 위의 두 줄을 기록하는 대신 위의 한 줄을 기록하는 것으로 충분합니다.
총 시간복잡도는 $O(KN^23^N)$이며, 효율적인 구현을 통해 $N \le 11$인 데이터까지 정답을 받을 수 있습니다.
Subtask 5 : $N \le 12$
Subtask 3, 4와 같은 방식으로 각 칸의 상태를 정의합니다. 단, 상태 배열에서 0과 2가 인접할 수 없다는 사실을 이용하여 가능한 상태의 총 가짓수를 줄일 수 있습니다. $N = 12$일 때 이 상태의 총 개수는 대략 5만 개입니다. 이 값을 $S$라고 할 때, $O(KN^2S)$의 시간복잡도로 문제를 풀 수 있습니다.
0, 1, 2로 이루어졌으며 0과 2가 인접한 배열 중, 마지막 원소가 0, 1, 2인 것의 가짓수를 각각 $a_i, b_i, c_i$라고 할 때, 다음 점화식이 성립합니다.
- $a_{k+1} = a_k + b_k$
- $b_{k+1} = a_k + b_k + c_k$
- $c_{k+1} = b_k + c_k$
이때
$a_{k+1} + \sqrt{2}b_{k+1} + c_{k+1} = (1+\sqrt{2})a_k + (2+\sqrt{2})b_k + (1+\sqrt{2})c_k = (1+\sqrt{2})(a_k+\sqrt{2}b_k+c_k)$
따라서 $S = O((1+\sqrt{2})^N)$이 되고, 문제의 총 시간복잡도는 $O(KN^2(1+\sqrt{2})^N)$이 됩니다.
#include <iostream>
#include <stack>
#include <string>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cassert>
using namespace std;
typedef long long ll;
const ll INF = 1e9;
int grid[12][12];
int value[12][12];
int pw3[13];
vector<int> bit[47321];
int nxt[47321][3];
int id[531441];
int dp[47321][51];
int tmp[47321][51];
int main()
{
ios::sync_with_stdio(false); cin.tie(NULL);
pw3[0] = 1;
for(int i=1;i<=12;i++) {
pw3[i] = pw3[i-1] * 3;
}
int n, k; cin >> n >> k;
int cnt = 0;
for(int i=0;i<pw3[n];i++) id[i] = -1;
for(int i=0;i<pw3[n];i++) {
vector<int> v(n);
int now = i;
bool flag = true;
for(int j=0;j<n;j++) {
v[j] = now%3;
if(j > 0) {
if(v[j-1] == 0 && v[j] == 2) {
flag = false;
break;
}
if(v[j-1] == 2 && v[j] == 0) {
flag = false;
break;
}
}
now /= 3;
}
if(flag) {
bit[cnt] = v;
id[i] = cnt;
cnt++;
}
}
for(int i=0;i<cnt;i++) {
nxt[i][0] = nxt[i][1] = nxt[i][2] = -1;
}
for(int i=0;i<pw3[n];i++) {
int j = id[i];
if(j < 0) continue;
if(i%3 == 0) {
nxt[j][0] = id[(i*3)%pw3[n] + 0];
nxt[j][1] = id[(i*3)%pw3[n] + 1];
} else if(i%3 == 1) {
nxt[j][0] = id[(i*3)%pw3[n] + 0];
nxt[j][1] = id[(i*3)%pw3[n] + 1];
if(bit[j][n-1] != 0) nxt[j][2] = id[(i*3)%pw3[n] + 2];
} else {
nxt[j][1] = id[(i*3)%pw3[n] + 1];
if(bit[j][n-1] != 0) nxt[j][2] = id[(i*3)%pw3[n] + 2];
}
}
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
cin >> grid[i][j];
}
}
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
cin >> value[i][j];
}
}
for(int i=0;i<cnt;i++) {
for(int j=0;j<=k;j++) {
dp[i][j] = -INF;
}
}
dp[0][0] = 0;
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
for(int a=0;a<cnt;a++) {
for(int b=0;b<=k;b++) {
tmp[a][b] = -INF;
}
}
for(int a=0;a<cnt;a++) {
for(int b=0;b<=k;b++) {
if(dp[a][b] == -INF) continue;
int u0 = nxt[a][0], u1 = nxt[a][1], u2 = nxt[a][2];
if(u0 >= 0 && grid[i][j] == 0) {
tmp[u0][b] = max(tmp[u0][b], dp[a][b]);
}
if(u1 >= 0) {
int T = dp[a][b];
if(bit[a][n-1] == 2) T += value[i-1][j];
if(grid[i][j] == 0 && b < k) {
tmp[u1][b+1] = max(tmp[u1][b+1], T);
}
else if(grid[i][j] == 1){
tmp[u1][b] = max(tmp[u1][b], T);
}
}
if(u2 >= 0 && j != 0 && j != n-1) {
int T = dp[a][b];
if(bit[a][n-1] == 2) T += value[i-1][j];
if(grid[i][j] == 0 && b < k) {
tmp[u2][b+1] = max(tmp[u2][b+1], T);
}
else if(grid[i][j] == 1){
tmp[u2][b] = max(tmp[u2][b], T);
}
}
}
}
for(int a=0;a<cnt;a++) {
for(int b=0;b<=k;b++) {
dp[a][b] = tmp[a][b];
}
}
}
}
int ans = 0;
for(int a=0;a<cnt;a++) {
ans = max(ans, dp[a][k]);
}
cout << ans;
}