무한한 1차원 길 위 초기 크기 $0$인 $N(1\leq N\leq 2\times10^5)$개의 눈덩이가 각각 위치 $L_1, L_2\dots,L_N$에 있습니다. 초기의 길 위에는 눈이 쌓여있고, 눈덩이가 거리 1을 눈 위에서 구르면 크기가 1 증가하고, 눈덩이가 지나간 길 위의 눈은 사라집니다. 모든 눈덩이가 동시에 $Q(1\leq Q\leq 2\times10^5)$개의 명령을 받아 좌/우로 움직일 때, 최종적인 눈덩이들의 크기를 구하는 것이 문제입니다.
다음과 같은 관찰을 할 수 있습니다.
관찰 1. $i$번째 눈덩이 가 밟을 수 있는 눈은 $i-1$번째와 $i+1$번째 눈덩이의 초기 위치 사이 뿐입니다. 그 밖의 눈은 다른 눈덩이가 밟게 됩니다.
관찰 2. $i$번째 눈덩이와 $i+1$번째 눈덩이의 상호작용을 관찰해 봅시다. $k$번째 쿼리를 처리한 뒤 눈덩이가 초기 기준 왼쪽으로 최대한 간 거리를 $left_k$, 오른쪽으로 최대한 간 거리를 $right_k$이라 했을 때 $left_k+right_k$가 $L_{i+1}-L_i$보다 작다면 두 눈덩이는 만나지 않고, 각각 $right_k$, $left_k$만큼의 눈을 확보할 수 있습니다. 그러다 $left_k+right_k$가 $L_{i+1}-L_i$를 넘어가는 순간 두 눈덩이의 경로가 겹치게 되고, 더 이상 두 눈덩이 사이에 눈은 남지 않습니다. 이 때 마지막 눈을 가져가는 눈덩이는 넘어가는 순간의 명령 방향으로 결정되게 됩니다.
쿼리마다 구간의 크기가 어떻게 변하는지 배열에 저장해 놓고, 원소의 크기가 $L_{i+1} - L_i$보다 커지는 시점을 이분탐색으로 찾아줄 수 있습니다. 이렇게 각 눈덩이마다 왼쪽/오른쪽으로 얼마나 많은 눈을 획득하는지 총 $O(N\log N)$에 계산할 수 있습니다.
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, q; cin >> n >> q;
vector<ll> a;
a.push_back(-LLINF);
for(int i=1; i<=n; i++) {
ll x; cin >> x; a.push_back(x);
}
a.push_back(LLINF);
vector<pair<ll, ll>> b;
vector<ll> c;
vector<ll> d;
ll cur = 0;
ll mx = 0, mn = 0;
b.push_back({0, 0});
c.push_back(0);
d.push_back(0);
for(int i=0; i<q; i++) {
ll x; cin >> x;
cur += x;
mx = max(mx, cur);
mn = min(mn, cur);
b.push_back({mn, mx});
c.push_back(abs(mn) + abs(mx));
d.push_back(x);
}
for(int i=1; i<=n; i++) {
ll Ldis = a[i] - a[i-1];
ll Lans = 0;
int id = upper_bound(all(c), Ldis) - c.begin();
if(id == sz(c)) {
Lans = -b.back().ff;
} else {
Lans += -b[id-1].ff;
if(d[id] < 0) {
Lans += Ldis - c[id-1];
}
}
ll Rdis = a[i+1] - a[i];
ll Rans = 0;
id = upper_bound(all(c), Rdis) - c.begin();
if(id == sz(c)) {
Rans = b.back().ss;
} else {
Rans += b[id-1].ss;
if(d[id] > 0) {
Rans += Rdis - c[id-1];
}
}
cout << Lans + Rans << '\n';
}
}
R, G, B로 이루어진 문자열 $S$가 있습니다. 길이 $K(1\leq N\leq2\times 10^5)$ 이하의 부분 문자열을 삭제하는 작업을 최소한으로 수행하여 문자열을 RGB...RGB꼴로 만드는 것이 목표입니다.
$dp[i][c]$을 $i$번째 문자열까지 보았을 때, 마지막을 문자 $c$로 끝내는데 필요한 최소 비용이라고 정의합니다.
그리고 $c’$를 $c$ 직전에 사용되었던 문자라고 정의합니다. ($c$가 B라면 $c’$는 G)
그렇다면 다음과 같이 dp table을 채울 수 있습니다.
Base case로 $dp[0][2] = 0$, 나머지는 $\text{INF}$으로 미리 채워 둘 수 있습니다. (첫 R을 이전 B의 끝에서부터 시작한다고 생각하면 됩니다.)
위 dp table을 나이브하게 채우면 $O(N^2)$의 시간이 들지만, segment tree나 BIT같은 range minimum query point update를 지원하는 자료구조를 사용하면 $O(N\log N)$의 시간복잡도로 해결할 수 있습니다.
class SegmentTree {
public:
vector<ll> seg;
int n;
SegmentTree(int n) {
seg.resize(4 * n + 5, LLINF);
this->n = n;
}
ll upd_(int idx, int l, int r, int pos, ll val) {
if (pos < l || pos > r) return seg[idx];
if (pos == l && pos == r) return seg[idx] = val;
int mid = (l + r) / 2;
return seg[idx] = min(
upd_(idx * 2, l, mid, pos, val),
upd_(idx * 2 + 1, mid + 1, r, pos, val)
);
}
ll calc_(int idx, int l, int r, int tl, int tr) {
if (tl > tr) return LLINF;
if (tl == l && tr == r) return seg[idx];
int mid = (l + r) / 2;
return min(
calc_(idx * 2, l, mid, tl, min(tr, mid)),
calc_(idx * 2 + 1, mid + 1, r, max(mid + 1, tl), tr)
);
}
void upd(int pos, ll val) {
upd_(1, 0, n - 1, pos, val);
}
ll calc(int l, int r) {
if(l < 0) l = 0;
if(r < 0) r = 0;
return calc_(1, 0, n - 1, l, r);
}
};
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, k; cin >> n >> k;
string s; cin >> s;
SegmentTree r(n+1), g(n+1), b(n+1);
b.upd(0, 0);
for(int i=1; i<=n; i++) {
r.upd(i, r.calc(i-k,i-1) + 1);
g.upd(i, g.calc(i-k,i-1) + 1);
b.upd(i, b.calc(i-k,i-1) + 1);
if(s[i-1] == 'R') {
ll v = r.calc(i, i);
ll v2 = b.calc(i-1, i-1);
ll v3 = b.calc(i-k-1, i-2) + 1;
r.upd(i, min({v, v2, v3}));
} else if(s[i-1] == 'G') {
ll v = g.calc(i, i);
ll v2 = r.calc(i-1, i-1);
ll v3 = r.calc(i-k-1, i-2) + 1;
g.upd(i, min({v, v2, v3}));
} else if(s[i-1] == 'B') {
ll v = b.calc(i, i);
ll v2 = g.calc(i-1, i-1);
ll v3 = g.calc(i-k-1, i-2) + 1;
b.upd(i, min({v, v2, v3}));
}
}
cout << b.calc(n, n) << '\n';
}
$N$명의 학생이 각각 주량 $A_i$를 가지고 있습니다. 다음과 같은 쿼리를 처리하면 됩니다.
1 i x: $i$번 학생부터 용량 $x$만큼 의리주를 시킵니다. 학생은 자기 주량만큼 마시면 술을 다음 사람에게 넘깁니다.
2 i: $i$번 학생이 지금까지 마신 술의 양을 출력합니다.
현재까지 주량에 도달하지 않은 학생 번호를 set으로 관리하고, 주량에 도달하게 되면 set에서 원소를 제거합니다. 주량에 도달하지 않은 다음 학생을 효율적으로 찾기 위해 set의 lower_bound 기능을 사용할 수 있습니다. 원소 제거는 최대 $N$번 일어나므로 효율적으로 문제를 풀 수 있습니다.
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, q; cin >> n >> q;
vector<int> a(n), ans(n);
for(int i=0; i<n; i++) {
cin >> a[i];
}
set<int> st;
for(int i=0; i<n; i++) {
st.insert(i);
}
while(q--) {
int op; cin >> op;
if(op == 1) {
int i, x; cin >> i >> x; i--;
if(st.lower_bound(i) == st.end()) {
continue;
}
int id = *st.lower_bound(i);
while(1) {
if(ans[id] + x < a[id]) {
ans[id] += x;
break;
} else {
x -= a[id] - ans[id];
ans[id] = a[id];
st.erase(st.find(id));
}
if(st.lower_bound(id + 1) == st.end()) break;
id = *st.lower_bound(id + 1);
}
} else {
int id; cin >> id; id--;
cout << ans[id] << '\n';
}
}
}
3964 - 팩토리얼과 거듭제곱(G2)
$N!(1 \leq N \leq 10^{18})$이 $K(1\leq K\leq 10^{12})$로 최대 몇번 나누어 떨어지는지 구하는 문제입니다.
$K$를 소인수분해 한 후, 각 소수 성분이 $N!$에 몇 번 들어가는지 계산 후 $K$에서의 지수로 나누어 준 값 중 최소값이 답이 됩니다. $O(T\sqrt k)$에 문제를 해결할 수 있습니다.
void solve() {
ll n, k; cin >> n >> k;
vector<pair<ll, int>> a;
for(ll i=2; i*i<=k; i++) if(k%i==0) {
int cnt = 0;
while(k % i == 0) {
k /= i;
cnt++;
}
a.push_back({i, cnt});
}
if(k != 1) a.push_back({k, 1});
ll ans = LLINF;
for(auto [x, t] : a) {
ll v = n;
ll tot = 0;
while(v) {
tot += v / x;
v /= x;
}
ans = min(ans, tot / t);
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int t; cin >> t;
while(t--) {
solve();
}
}
길이 $N(1\leq N\leq50)$의 문자열 $S$이 주어지고, 주어진 부분 문자열 $M(1\leq M\leq 50)$개를 적절히 이어붙여 $S$를 만들어야 합니다. 한 부분 문자열 $T$에서는 문자의 순서를 임의로 바꿀 수 있으며, 그 비용은 원래 $T$와 일치하지 않는 문자의 갯수만큼 듭니다. 이 비용을 최소화 하는 것이 문제입니다.
$dp[i]$를 $i$번째 문자부터 끝까지 완성시키는데 최소 비용이라고 정의한 뒤 모든 부분문자열 $T$를 시도해보면 됩니다.
string s;
int n, dp[51];
vector<string> a;
int dfs(int id) {
int& ret = dp[id];
if(ret != -1) return ret;
if(id == sz(s)) return ret = 0;
ret = INF;
for(int i=0; i<n; i++) if(id + sz(a[i]) <= sz(s)) {
vector<int> cnt(26);
for(int j=id,k=0; j<id + sz(a[i]); j++,k++) {
cnt[s[j]-'a']++;
cnt[a[i][k]-'a']--;
}
int suc = 1;
for(int j=0; j<26; j++) if(cnt[j]) suc = 0;
if(!suc) continue;
int score = 0;
for(int j=id,k=0; j<id + sz(a[i]); j++,k++) {
if(s[j] != a[i][k]) {
score++;
}
}
ret = min(ret, score + dfs(id + sz(a[i])));
}
return ret;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
memset(dp, -1, sizeof dp);
cin >> s >> n;
a = vector<string>(n);
for(int i=0; i<n; i++) cin >> a[i];
cout << (dfs(0)==INF?-1:dfs(0)) << '\n';
}
17234 - Scoring Hack(G2)
0점에서 시작해서 매 턴마다 다음과 같이 행동할 수 있습니다 : $a$점을 얻거나, $b$점을 얻거나, 현재까지 턴의 수의 10% 이하로 점수를 2배 뻥튀기 할 수 있습니다. $n$점 이상 $n+a$점 이하 점수를 얻을 수 있는 최소 턴을 구하면 됩니다. 단순한 BFS로 [현재 점수, 현재 턴수, 2배 뻥튀기 횟수] 상태를 관리하면서 최솟값을 구할 수 있습니다.
int vis[601][501][11];
struct state {
int score, turn, sp;
};
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, a, b; cin >> n >> a >> b;
memset(vis, 0x3f, sizeof vis);
queue<state> q;
q.push({0, 0, 0});
vis[0][0][0] = 0;
while(sz(q)) {
int sc = q.front().score;
int tu = q.front().turn;
int sp = q.front().sp; q.pop();
if(sc >= n + a) continue;
if(sc >= n) {
cout << vis[sc][tu][sp] << '\n';
return 0;
}
// win
if(sc+a <= n+a && vis[sc+a][tu+1][sp] == INF) {
vis[sc+a][tu+1][sp] = vis[sc][tu][sp] + 1;
q.push({sc+a, tu+1, sp});
}
// lose
if(sc+b <= n+a && vis[sc+b][tu+1][sp] == INF) {
vis[sc+b][tu+1][sp] = vis[sc][tu][sp] + 1;
q.push({sc+b, tu+1, sp});
}
// double
if(sc*2 <= n+a && tu+1 >= 10 * (sp+1) && vis[sc*2][tu+1][sp+1] == INF) {
vis[sc*2][tu+1][sp+1] = vis[sc][tu][sp] + 1;
q.push({sc*2, tu+1, sp+1});
}
}
}
16399 - 드라이브(P5)
길이 $D$ 도로 위 주유소가 위치 $L_1, L_2, \cdots, L_N$에 있고, 각 주유소마다 기름 가격은 $P_1, P_2, \cdots, P_N$입니다. 기름 용량이 $C$, 연비가 $E\ell/km$인 차가 $0$에서 출발하여 $D$ 지점까지 갈 때 최소한의 주유 비용으로 $D$에 도달하는 비용을 구하면 됩니다. (처음에는 기름이 가득 있습니다.) 찾아보니 문제 태그가 dp 이외엔 없을 정도로 dp 풀이가 많던데, greedy한 방법으로 문제를 풀 수 있어서 소개합니다.
다음과 같은 greedy한 방법으로 기름을 채우면 됩니다. 자신의 위치보다 기름값이 적은 첫 오른쪽 위치를 $X$라고 합시다. 만약 현재 가지고 있는 기름으로 $X$까지 도달 가능하다면, 이동합니다. 그렇지 않다면, $X$까지 겨우 도달할 수 있을 정도의 최소 기름을 넣고 갑니다. $X$를 넘어갈 정도로 기름을 채우게 된다면, $X$에서 기름을 사는 것이 더 이득이기 때문에 정당성을 부여할 수 있습니다. 모든 주유소 위치에서의 $X$는 뒤에서부터 monotone stack을 유지하면서 구해내면 $O(N)$에 구할 수 있습니다.
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int c, e, d; cin >> c >> e >> d;
int n; cin >> n;
vector<pii> a(n+2);
int cur = 0;
for(int i=1; i<=n; i++) {
int s; cin >> s;
cur += s;
if(s * e > c) {
cout << -1 << '\n';
return 0;
}
a[i].ff = cur;
}
if((d - cur) * e > c) {
cout << -1 << '\n';
return 0;
}
a[n+1].ff = d;
for(int i=1; i<=n; i++) {
cin >> a[i].ss;
}
stack<pii> st;
vector<int> rht(n+2);
st.push({d, 0});
for(int i=n; i>=1; i--) {
while(st.top().ss > a[i].ss) st.pop();
rht[i] = st.top().ff;
st.push({a[i].ff, a[i].ss});
}
int curOil = c - a[1].ff * e;
int ans = 0;
for(int i=1; i<=n; i++) {
int curDis = a[i].ff;
int nxtDis = rht[i];
int needOil = min(c, (nxtDis - curDis) * e);
ans += max(0, (needOil - curOil) * a[i].ss);
curOil = max(curOil, needOil);
curOil -= e * (a[i+1].ff - a[i].ff);
}
cout << ans << '\n';
}
$0$과 $9$ 사이 양의 정수 $A$와 $B$가 주어지고, $A+B$가 아닌 수를 $0$에서 $9$사이 아무 수나 출력하면 됩니다. $(A+B+1)\%10$을 출력하면 언제나 $A+B$가 아닌 수를 출력할 수 있습니다. 2초만 더 빨리 풀었으면 세계 1등인데 까비..
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int a, b; cin >> a >> b;
cout << ((a+b)+1)%10 <<'\n';
}
B - Adjacency Matrix
제목 그대로 Adjacency matrix를 만들고 출력하면 됩니다.
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n; cin >> n;
vector<vector<int>> g(n, vector<int>(n));
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
cin >> g[i][j];
if(g[i][j]) {
cout << j+1 << ' ';
}
}
cout << '\n';
}
}
C - 343
$N(1 \leq N \leq 10^{18})$이하인 palindrome인 세제곱수를 출력하면 되는 문제입니다. 가능한 세제곱수의 base가 $10^6$개라 전부 해보면 됩니다.
bool pal(ll v) {
vector<ll> a;
while(v) {
a.pb(v % 10); v /= 10;
}
for(int i=0; i<sz(a); i++) {
if(a[i] != a[sz(a)-1-i]) return false;
}
return true;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
ll n; cin >> n;
ll ans = -1;
for(ll i=1; i*i*i<=n; i++) {
ll v = i*i*i;
if(pal(v)) {
ans = v;
}
}
cout << ans << '\n';
}
D - Diversity of Scores
사람 $N$명이 있고, 모두 0점에서 시작합니다. $T(1\leq T\leq2\times10^5)$개의 쿼리가 $a$ $b$꼴로 주어집니다. 이는 사람 $a$에게 $b$점을 추가해주는 쿼리입니다. 각 쿼리 이후 unique한 점수의 갯수를 출력하면 됩니다.
map<long long,int> 꼴로 특정 점수가 몇개가 있는지 관리를 하고, map key의 갯수를 세어주면 됩니다. map의 value가 0이 될 때 원소를 삭제해 주면 됩니다.
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, t; cin >> n >> t;
vector<ll> a(n);
map<ll, int> mp;
mp[0] = n;
for(int i=0; i<t; i++) {
int u; cin >> u; u--;
ll x; cin >> x;
mp[a[u]]--;
if(mp[a[u]] == 0) mp.erase(mp.find(a[u]));
a[u] += x;
mp[a[u]]++;
cout << sz(mp) << '\n';
}
}
E - 7x7x7
7x7x7 큐브 세개 중 세 큐브가 겹치는 공간, 두 큐브만 겹치는 공간, 한 큐브에만 속한 공간이 $V_3,V_2, V_1$를 만족하는 큐브의 좌표를 찾는 문제입니다. 우선 한 큐브를 $(0,0,0)$에 고정하고, 다른 두개의 큐브만 위치를 생각하면 됩니다. 다른 큐브들이 유의미하게 있을 수 있는 좌표는 각각 $(-7\sim7, -7\sim7,-7\sim7)$입니다. 그 밖을 벗어나게 되면 어차피 안 겹치므로 $(7,7,7)$에 있는 것과 동일한 효과를 가지기 때문입니다. 3개의 좌표를 정하고 각각 $V_1, V_2, V_3$를 $O(1)$에 구할 수 있으면 $O(14^6)$만에 문제를 풀 수 있습니다.
int v1, v2, v3;
bool vol2(int x1, int y1, int z1, int x2, int y2, int z2) {
int mx1 = max(x1, x2);
int mx2 = min(x1+7, x2+7);
int my1 = max(y1, y2);
int my2 = min(y1+7, y2+7);
int mz1 = max(z1, z2);
int mz2 = min(z1+7, z2+7);
if(mx1<mx2&&my1<my2&&mz1<mz2) {
return (mx2-mx1) * (my2-my1) * (mz2-mz1);
} else return 0;
}
int vol(int x1, int y1, int z1, int x2, int y2, int z2, int x3, int y3, int z3) {
int ans = 7 * 7 * 7 * 3;
int mx1 = max({x1, x2, x3});
int mx2 = min({x1+7, x2+7, x3+7});
int my1 = max({y1, y2, y3});
int my2 = min({y1+7, y2+7, y3+7});
int mz1 = max({z1, z2, z3});
int mz2 = min({z1+7, z2+7, z3+7});
int rv3 = 0;
if(mx1<mx2&&my1<my2&&mz1<mz2) {
rv3 = (mx2-mx1) * (my2-my1) * (mz2-mz1);
}
int rv2 = 0;
rv2 += vol2(x1, y1, z1, x2, y2, z2);
rv2 += vol2(x2, y2, z2, x3, y3, z3);
rv2 += vol2(x3, y3, z3, x1, y1, z1);
rv2 -= rv3 * 3;
int rv1 = 7 * 7 * 7 * 3 - rv2 * 2 - rv3 * 3;
if(rv1 == v1 && rv2 == v2 && rv3 == v3) return 1;
return 0;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> v1 >> v2 >> v3;
for(int x1=-7; x1<=7; x1++) for(int y1=-7; y1<=7; y1++) for(int z1=-7; z1<=7; z1++) {
for(int x2=-7; x2<=7; x2++) for(int y2=-7; y2<=7; y2++) for(int z2=-7; z2<=7; z2++) {
if(vol(0,0,0,x1,y1,z1,x2,y2,z2)) {
cout << "Yes\n";
cout << 0 << ' ' << 0 << ' ' << 0 << ' ';
cout << x1 << ' ' << y1 << ' ' << z1 << ' ';
cout << x2 << ' ' << y2 << ' ' << z2 << '\n';
return 0;
}
}
}
cout << "No\n";
}
F - Second Largest Query
$N(1\leq N \leq 2\times 10^5)$개의 원소가 있는 배열이 주어집니다. 다음과 같은 쿼리를 처리하면 됩니다.
1 p x : $A_p$를 $x$로 바꿉니다.
2 l r : $A_l, A_{l+1},\cdots ,A_r$ 중 두번째로 큰 원소의 등장 횟수를 출력합니다. 만약 두번째로 큰 원소가 없다면 0을 출력합니다.
최댓값, 최댓값의 등장횟수, 2번째로 큰 값, 2번째로 큰 값의 등장 횟수를 관리하는 세그먼트 트리를 이용해서 문제를 풀 수 있습니다.
struct Node {
ll mx, mx2, mxocc, mx2occ;
};
class SegmentTree {
public:
vector<Node> seg;
int n;
SegmentTree(int n) {
seg.resize(4 * n + 5);
this->n = n;
}
Node op(Node a, Node b) {
Node ret;
map<ll, int> mp;
mp[a.mx] += a.mxocc;
mp[a.mx2] += a.mx2occ;
mp[b.mx] += b.mxocc;
mp[b.mx2] += b.mx2occ;
vector<pair<ll, int>> c;
for(auto x : mp) c.pb(x);
sort(all(c), [](pair<ll, int> x, pair<ll, int> y){
return x.ff > y.ff;
});
ret.mx = c[0].ff; ret.mxocc = c[0].ss;
if(sz(c) >= 2) ret.mx2 = c[1].ff, ret.mx2occ = c[1].ss;
else ret.mx2 = 0, ret.mx2occ = 0;
return ret;
}
Node upd_(int idx, int l, int r, int pos, ll val) {
if (pos < l || pos > r) return seg[idx];
if (pos == l && pos == r) {
seg[idx].mx = val;
seg[idx].mxocc = 1;
seg[idx].mx2 = 0;
seg[idx].mx2occ = 0;
return seg[idx];
}
int mid = (l + r) / 2;
return seg[idx] = op(upd_(idx * 2, l, mid, pos, val),
upd_(idx * 2 + 1, mid + 1, r, pos, val));
}
Node calc_(int idx, int l, int r, int tl, int tr) {
if (tl > tr) return {0, 0, 0, 0};
if (tl == l && tr == r) return seg[idx];
int mid = (l + r) / 2;
return op(calc_(idx * 2, l, mid, tl, min(tr, mid)),
calc_(idx * 2 + 1, mid + 1, r, max(mid + 1, tl), tr));
}
void upd(int pos, ll val) {
upd_(1, 0, n - 1, pos, val);
}
Node calc(int l, int r) {
return calc_(1, 0, n - 1, l, r);
}
};
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, q; cin >> n >> q;
vector<ll> a(n);
SegmentTree st(n);
for(int i=0; i<n; i++) {
cin >> a[i];
st.upd(i, a[i]);
}
for(int i=0; i<q; i++) {
int op; cin >> op;
if(op == 1) {
int p, x; cin >> p >> x; p--;
st.upd(p, x);
} else {
int l, r; cin >> l >> r; l--, r--;
cout << st.calc(l, r).mx2occ << '\n';
}
}
}
G - Compress Strings
$N(1\leq N\leq20)$개의 문자열 $S_1, \cdots, S_N(\sum len(S_i)\leq2\times10^5)$이 주어집니다. $N$개의 문자열을 모두 substring으로 포함하는 하나의 문자열 $T$의 최소 길이를 구하는 문제입니다.
우선 한 문자열이 다른 문자열의 substring이 되는 문자열은 제거를 해줍니다. 이 작업은 후술할 dp가 작동하기 위해 꼭 필요한 과정입니다. 모든 $i$와 $j$ 쌍에 대하여 $f(i,j) = i$번째 문자열의 suffix와 $j$번째 문자열의 prefix가 최대로 얼마나 겹치는지 구해놓았다면 TSP 문제의 dp를 푸는 것처럼 문제를 풀 수 있습니다. 만약 문자열 제거 과정이 없었다면 마지막으로 사용한 문자열의 끝이 다음 문자열의 끝보다 전에 끝난다는 보장을 할 수 없기 때문에 제거 과정이 필요합니다.
$f(i,j)$는 KMP나 Suffix Array와 같은 문자열 알고리즘으로 효율적으로 구할 수 있습니다. 저는 KMP를 까먹어서 SA를 사용하였습니다.
string s = "";
string t = "!@#$%^&*()_+{}:<>,.1234567";
vector<int> pos;
vector<int> start;
vector<vector<int>> pref;
int nn;
vector<int> craig;
vector<int> szzz;
int baeje = 0;
void make_sa(string &s) {
int n = sz(s), m = max(256, n)+1;
vector<int> r(n*2), nr(n*2);
vector<int> sa(n), isa(n), cnt(m), idx(n), lcp(n), poss(n);
for(int i=0 ; i<n ; i++) sa[i] = i, r[i] = s[i];
for(int d=1 ; d<n ; d *= 2){
auto cmp = [&](int i,int j){
return r[i] < r[j] || (r[i] == r[j] && r[i+d] < r[j+d]); };
for(int i=0 ; i<m ; i++) cnt[i] = 0;
for(int i=0 ; i<n ; i++) cnt[r[i+d]]++;
for(int i=1 ; i<m ; i++) cnt[i] += cnt[i-1];
for(int i=n-1 ; ~i ; i--) idx[--cnt[r[i+d]]] = i;
for(int i=0 ; i<m ; ++i) cnt[i] = 0;
for(int i=0 ; i<n ; ++i) cnt[r[i]]++;
for(int i=1 ; i<m ; ++i) cnt[i] += cnt[i-1];
for(int i=n-1 ; ~i ; --i) sa[--cnt[r[idx[i]]]] = idx[i];
nr[sa[0]] = 1;
for(int i=1 ; i<n ; ++i) nr[sa[i]] = nr[sa[i-1]] + cmp(sa[i-1], sa[i]);
for(int i=0 ; i<n ; ++i) r[i] = nr[i];
if(r[sa[n-1]]==n) break;
}
for(int i=0 ; i<n ; i++) {
isa[sa[i]] = i;
}
for(int k=0, i=0 ; i<n ; i++) if(isa[i]) {
for(int j=sa[isa[i]-1]; s[i+k]==s[j+k]; ++k);
lcp[isa[i]] = (k ? k-- : 0);
}
for(int i=0; i<n; i++) {
poss[sa[i]] = i;
}
// lcp[i] = s[i], s[i-1]의 lcp 길이
for(int i=0; i<nn; i++) {
int mx = INF;
for(int j=poss[start[i]]; j>0; j--) {
mx = min(mx, lcp[j]);
if(mx >= craig[start[i]]) {
baeje |= (1<<i);
}
// j-1번째 lcp
if(mx == 0) break;
if(craig[sa[j-1]] == mx) {
pref[i][pos[sa[j-1]]] = max(pref[i][pos[sa[j-1]]], mx);
}
}
mx = INF;
for(int j=poss[start[i]]+1; j<sz(sa); j++) {
mx = min(mx, lcp[j]);
if(mx >= craig[start[i]]) {
baeje |= (1<<i);
}
if(mx == 0) break;
if(craig[sa[j]] == mx) {
pref[i][pos[sa[j]]] = max(pref[i][pos[sa[j]]], mx);
}
}
}
}
vector<vector<int>> dp;
int dfs(int mask, int id) {
int& ret = dp[mask][id];
if(ret != -1) return ret;
if(mask == (1<<nn)-1) return 0;
ret = INF;
for(int i=0; i<nn; i++) if(!(mask & (1<<i))) {
ret = min(ret, szzz[i] - pref[i][id] + dfs(mask | (1<<i), i));
}
return ret;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n; cin >> n;
int shit = 0;
set<string> st;
for(int i=0; i<n; i++) {
string v; cin >> v;
if(st.count(v)) {
shit++;
continue;
}
st.insert(v);
szzz.pb(sz(v));
s += v; s += t[i];
start.pb(sz(pos));
int x = sz(v);
for(int j=0; j<sz(v)+1; j++) {
craig.pb(x--);
pos.push_back(i-shit);
}
}
n -= shit;
nn = n;
pref = vector<vector<int>>(n, vector<int>(n));
int id = 0;
make_sa(s);
dp = vector<vector<int>>(1<<n, vector<int>(n, -1));
ll ans = INF;
for(int i=0; i<n; i++) {
ans = min(ans, szzz[i] + (ll)dfs(baeje|(1<<i), i));
}
cout << ans << '\n';
}
문제 설명
R,G,B 세 문자로 이루어진 문자열 $s$가 주어집니다. $A$원을 지불하면 앞 문자 하나를 삭제, $B$원을 지불하면 뒷 문자 하나를 삭제, $C$원을 사용하면 원하는 문자를 다른 문자로 변경 가능할 때 RGBRGB...RGB 꼴의 문자열을 만드는데 드는 최소 비용을 구하는 문제입니다.
해설
$dp[i][j]$를 $i$번째 문자를 $j$로 칠하려 할 때 드는 최소 비용이라고 정의합시다.
우선 현재 칠해야 하는 색이 R, 즉 $j$가 $0$일 때, $b \times (n-i)$의 비용을 지불하고 그 부분부터 뒷 문자를 모두 삭제할 수 있습니다. 또 만약 $s[i] \neq j$라면 $dp[i][j] = min(dp[i][j], c + dp[i+1][(j+1)\% 3])$으로 전이할 수 있습니다.
이후 모든 $0 \leq i \leq n$인 모든 $i$에 대해 $a\times i+dp[i][0]$의 최솟값을 구하면 답을 얻을 수 있습니다.
코드
ll n, a, b, c, s[200003];
ll dp[200003][3];
ll dfs(int id, int col) {
ll& ret = dp[id][col];
if(ret != -1) return ret;
if(id == n) {
if(col == 0) return ret = 0;
else return ret = LLINF;
}
ret = LLINF;
if(col == 0) ret = (n-id) * b;
if(col == s[id]) {
ret = min(ret, dfs(id+1, (col+1) % 3));
} else {
ret = min(ret, c + dfs(id+1, (col+1) % 3));
}
return ret;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
memset(dp, -1, sizeof dp);
cin >> n;
string t; cin >> t;
for(int i=0; i<n; i++) {
if(t[i] == 'R') s[i] = 0;
else if(t[i] == 'G') s[i] = 1;
else s[i] = 2;
}
cin >> a >> b >> c;
ll ans = LLINF;
for(int i=0; i<=n; i++) {
ans = min(ans, i*a + dfs(i, 0));
}
cout << ans << '\n';
}
문제 설명
일렬로 키가 각각 $L_1,L_2,\cdots,L_N$인 식물이 놓여있고, $[l,r]$구간에 물을 주면 $L_l,L_l+1,\cdots,L_r$이 1씩 증가하게 됩니다. 이런 상황에서 최소 횟수 $d$로 피라미드 모양을 만들려 할 때 $d$를 구하는 것이 문제입니다.
해설
우선 가장 길게 될 식물(피라미드의 정점)을 정합니다. 이후, 그 식물 앞으로는 증가수열, 뒤로는 감소수열이 되게끔 하는 최소 횟수를 $pref$, $suf$배열에 저장합니다. $x$를 가장 높은 식물로 키우는 최소 횟수는 $max(pref[x], suf[x]) +$식물 $x$를 $max(L_{x-1}, L_{x+1})+1$으로 키우는 횟수입니다. 이 중 최소를 구하면 됩니다. 시간복잡도는 $O(N)$입니다.
코드
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n; cin >> n;
vector<ll> a(n);
for(int i=0; i<n; i++) {
cin >> a[i];
}
vector<ll> pref(n), suf(n);
for(int i=1; i<n; i++) {
pref[i] = pref[i-1];
if(a[i] > a[i-1]) continue;
else {
pref[i] += a[i-1] - a[i] + 1;
}
}
for(int i=n-2; i>=0; i--) {
suf[i] = suf[i+1];
if(a[i] > a[i+1]) continue;
else suf[i] += a[i+1] - a[i] + 1;
}
ll ans = LLINF;
for(int i=0; i<n; i++) {
ll v1 = 0; if(i) v1 = pref[i-1];
ll v2 = 0; if(i+1<n) v2 = suf[i+1];
ll m1 = 0; if(i) m1 = a[i-1];
ll m2 = 0; if(i+1<n) m2 = a[i+1];
ans = min(ans, max(v1, v2) + max(0LL, max(m1, m2) - a[i] + 1));
}
cout << ans << '\n';
}
문제 설명
일자로 된 길 위 $N(4\leq N \leq100000)$개의 지점이 있습니다. $i$번째 지점의 위치는 $L_i(1 \leq L_i\leq10^{15})$, 그리고 그 지점 위 JOIG 중 하나의 글자가 써 있습니다. $Q(1\leq Q\leq10^5)$개의 쿼리가 주어집니다.
$(s, e)$ : $s$에서 여행을 시작, JOIG를 순서대로 보고 $e$에서 여행을 마무리 할 때 최단거리 $D$를 구하시오.
해설
목표 글자가 $c$라면, 지금 현재 위치에서 왼쪽으로 가장 가까운 글자/오른쪽으로 가장 가까운 글자 2개만 고려하면 됩니다. 한 쿼리당 $2^4$번의 시뮬레이션을 사용해서 풀 수 있습니다. 현위치에서 가장 가까운 글자 위치는 이분탐색으로 찾을 수 있습니다.
코드
int n;
vector<vector<ll>> g(4);
ll s, e;
ll cur = 0;
ll dfs(int id) {
if(id == 4) {
return abs(cur - e);
}
ll t = cur;
int v = lower_bound(all(g[id]), cur) - g[id].begin();
ll ret1 = LLINF, ret2 = LLINF;
if(v != sz(g[id])) {
ret1 = g[id][v] - cur;
cur = g[id][v];
ret1 += dfs(id + 1);
cur = t;
}
if(v > 0) {
ret2 = cur - g[id][v-1];
cur = g[id][v-1];
ret2 += dfs(id + 1);
cur = t;
}
return min(ret1, ret2);
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for(int i=0; i<n; i++) {
ll x; cin >> x;
char c; cin >> c;
for(int j=0; j<4; j++) if(c == "JOIG"[j]) {
g[j].push_back(x);
}
}
int q; cin >> q;
while(q--) {
cin >> s >> e;
cur = s;
cout << dfs(0) << '\n';
}
}
문제 설명
길이 $L_1+L_2+\cdots+L_N\space(N\leq50, 1\leq L_i\leq1000)$인 막대가 있고, 막대 위 $x=L_1, L_2,\cdots,L_{N-1} $에 각각 막대를 절단할 수 있는 표시가 있습니다. 막대를 적절히 절단하여 최소 막대 길이와 최대 막대 길이간의 길이 차이 $d$를 최소화하는 문제입니다.
해설
우선 절단한 막대 길이의 하나의 하한을 $lo$로 설정합시다. 이후 막대의 상한 $hi$으로 가능한 값을 parametric search로 찾아줄 수 있습니다. 가능한 $lo$의 값은 최대 $50000$이므로 $O(\sum L\cdot N\log N)$정도에 문제를 해결할 수 있습니다.
코드
int n, a[51], dp[51];
int f(int l, int r) {
int ret = a[r];
if(l) ret -= a[l-1];
return ret;
}
int dfs(int x, int l, int r) {
int& ret = dp[x];
if(x == n) return ret = 1;
if(ret != -1) return ret;
int sum = 0;
ret = 0;
for(int i=x; i<n; i++) {
if(x == 0 && i == n-1) break;
sum += a[i];
if(l<=sum && sum<=r) {
ret |= dfs(i+1, l, r);
}
}
return ret;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for(int i=0; i<n; i++) cin >> a[i];
int mn = *min_element(a, a+n);
int fans = INF;
for(int i=mn; i<=50000; i++) {
int id = 0;
int l=i, r=50000, ans=INF;
while(l <= r) {
int mid = (l+r) / 2;
memset(dp, -1, sizeof dp);
if(dfs(0, i, mid)) {
r = mid - 1;
ans = mid;
} else {
l = mid + 1;
}
}
fans = min(fans, ans - i);
}
cout << fans << '\n';
}
문제 설명
정점 $N(1\leq N \leq 1000)$개, 가중치가 있는 단방향 간선 $M(1 \leq M \leq 1000)$개 로 이루어진 그래프에서 정점 $1$에서 $N$까지 최단 경로가 $L(1 \leq L \leq 10^9)$ 이하가 되도록 간선 방향을 뒤집을 때, 뒤집어야 하는 간선의 최소 갯수를 구하는 문제입니다.
해설
$dis[v][x]$를 정점 $v$까지 $x$번의 뒤집음으로 도달 가능한 최단거리라고 정의하고 dijkstra알고리즘을 사용하여 최단거리를 구해주면 됩니다. 시간복잡도는 $O(M +N^2\log N^2)$입니다.
코드
#include "bits/stdc++.h"
#ifndef ONLINE_JUDGE
#include "headers/debug.h"
#else
#define debug(...) 42
#endif
using namespace std;
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
#define LLINF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
#define uniq(x) sort(all(x)); x.resize(unique(all(x))-x.begin());
#define sz(x) (int)x.size()
#define pw(x) (1LL<<x)
#define pb push_back
using pii = pair<int, int>;
using ll = long long;
using ld = long double;
const ll MOD = 1e9 + 7;
const long double PI = acos(-1.0);
struct cmp {
bool operator() (pair<int, pii> a, pair<int, pii> b) {
return a.ff > b.ff;
}
};
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, m, l; cin >> n >> m >> l;
vector<vector<pii>> g(n), rg(n);
for(int i=0; i<m; i++) {
int u, v, x; cin >> u >> v >> x;
u--, v--;
g[u].push_back({v, x});
rg[v].push_back({u, x});
}
vector<vector<int>> dis(n, vector<int>(m+1, INF));
dis[0][0] = 0;
priority_queue<pair<int, pii>, vector<pair<int, pii>>, cmp> pq;
pq.push({0, {0, 0}});
while(sz(pq)) {
int curdis = pq.top().ff;
int curid = pq.top().ss.ff;
int cursw = pq.top().ss.ss; pq.pop();
if(dis[curid][cursw] ^ curdis) continue;
for(auto [nxtid, nxtdis] : g[curid]) {
if(dis[nxtid][cursw] > curdis + nxtdis) {
dis[nxtid][cursw] = curdis + nxtdis;
pq.push({dis[nxtid][cursw], {nxtid, cursw}});
}
}
for(auto [nxtid, nxtdis] : rg[curid]) {
if(cursw+1<=m && dis[nxtid][cursw+1] > curdis + nxtdis) {
dis[nxtid][cursw+1] = curdis + nxtdis;
pq.push({dis[nxtid][cursw+1], {nxtid, cursw + 1}});
}
}
}
for(int i=0; i<=m; i++) {
if(dis[n-1][i] <= l) {
cout << i << '\n';
return 0;
}
}
cout << -1 << '\n';
}