Problem - F - Codeforces
問題
$0, 1$ からなる長さ $n$ の数列 $\{ a_i \}$ が与えられる.この数列に対して,以下の操作を $k$ 回まで行う.
- $\{ a_i \}$ から長さ $l$ の連続部分列を選ぶ.
- その部分列を全て $0$ か全て $1$ に変える.
$s = \sum a_i$ としたとき, $\min(s, n - s)$ の最小値を求めよ.
制約
- $1 \leq l \leq n \leq 10^6$
- $1 \leq k \leq 10^6$
考察
$s$ を小さくすることにしてしまえば,極力多くの要素を $0$ にする問題になる.これを数列の $0, 1$ を反転させて 2 回解けばいい.
まずシンプルな解法として, $dp_{i, j} =$ 「 $a[0, i]$ について, $j$ 回操作を行ったときの $s$ の最小値」という DP が考えられる.選ぶ部分列は重複しないようにするのが最善なので, $\{ a_i \}$ を $l$ だけ $0$ でかさ増しすればこれは $O(n^2)$ で計算できる.
これの計算量を落とすために, Alien DP というテクニックを使う.
簡単に説明すると,
- 操作回数を覚える代わりに,操作を 1 回行う毎にペナルティ $p$ を加えることにする.
- 最適解の操作回数は $p$ が大きいほど小さくなる.
- そこで最適解の操作回数が $k$ 回になるようなペナルティを二分探索すればいい.
という感じ.ただし $k$ 回が最適であるような $p$ が存在すること(この性質は凸性と呼ばれる)が必要で,.今回の問題はこれが満たされているらしい.
実装例
以下の実装では,
- ペナルティに対する操作回数は最小のものを求める.
- ペナルティの上界と下界,二分探索のループ回数はかなり適当.
としている.また,ペナルティ 0 で操作回数が $k$ 回以下の場合はそれがそのまま答えになることに注意.
Submission #68388249 - Codeforces
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
|
#include <iostream>
#include <vector>
#include <string>
#include <tuple>
using ldouble = long double;
constexpr int INF = 1 << 30;
int main() {
int n, l, k;
std::cin >> n >> k >> l;
std::vector<int> xs(n);
for (auto& x : xs) {
char c;
std::cin >> c;
x = (std::islower(c) ? 1 : 0);
}
xs.insert(xs.begin(), 0);
// penaltyを固定したときの,最小コストとパス回数の最小値
auto calc = [&](ldouble pena) {
static std::vector<std::pair<ldouble, int>> dp(n + l + 1);
dp[0] = std::make_pair(0, 0);
for (int i = 1; i <= n + l; ++i) {
ldouble pdist;
int cnt;
std::tie(pdist, cnt) = dp[i - 1];
if (i <= n) pdist += xs[i];
dp[i] = std::make_pair(pdist, cnt);
if (i >= l) {
std::tie(pdist, cnt) = dp[i - l];
++cnt;
auto nxt = std::make_pair(pdist + pena, cnt);
dp[i] = std::min(dp[i], nxt);
}
}
return dp.back();
};
int ans = INF;
for (int i = 0; i < 2; ++i) {
ldouble pena = 0;
{
int cnt;
std::tie(std::ignore, cnt) = calc(pena);
// pena=0でk回も使わないならそれが最適
if (cnt > k) {
ldouble ok = 1e9, ng = 0;
// pena >= ok -> used <= k
for (int q = 0; q < 100; ++q) {
ldouble mid = (ok + ng) / 2;
int pcnt;
std::tie(std::ignore, pcnt) = calc(mid);
(pcnt <= k ? ok : ng) = mid;
}
pena = ok;
}
}
ldouble cost;
std::tie(cost, std::ignore) = calc(pena);
cost -= k * pena;
int icost = cost + 1e-10;
ans = std::min(ans, icost);
// 全部反転してもう1回
for (auto& x : xs) x = 1 - x;
}
std::cout << ans << std::endl;
return 0;
}
|