1635 < ICPC Prelim < Challenges | Aizu Online Judge
問題
長さ $n$ の整数列 $\{ a_i \}, \{ b_i \}$ が与えられる。
以下の操作を繰り返して $\{ a_i \}$ を $\{ b_i \}$ に一致させるとき、最小の操作回数を求めよ。
- $1 \leq l \leq r \leq n$ なる整数 $l, r$ を選ぶ。
- $a_l, a_{l + 1}, \cdots, a_r$ を 1 増やす。ただし値が $m$ を上回る場合は $1$ に戻る。
制約
- $1 \leq n \leq 10^3$
- $1 \leq m \leq 10^4$
- $1 \leq a_i, b_i \leq m$
考察
まず $c_i = (b_i - a_i) \bmod m$ とすると、「全て $0$ の数列を区間 1 加算によって $\{ c_i \}$ と $\bmod{m}$ で一致させる」という問題になる。
「作った区間をどこで閉じるかは保留にする」という考えのもと、以下のような DP が立つ。
$$
dp_{i, j} = \text{$c_i$まで処理した時点で、$j$個の区間が閉じ待ちのときの最小操作回数}
$$
これでは $j$ の値が最大 $nm$ 程度になるので、状態数が $\Theta(n^2 m)$ となり厳しい。
しかしよく考えてみると、 $j$ 個の区間が閉じ待ちということは直前の要素は $+j$ されていることになる。つまり $j \equiv c_i \pmod{m}$ なる $j$ のみ考えればいい。すると以下のような DP が立つ。
$$
dp_{i, j} = \text{$c_i$まで処理した時点で、$jm + c_i$個の区間が閉じ待ちのときの最小操作回数}
$$
これなら状態数は $\Theta(nm)$ となる。遷移は $j$ の差が高々 1 のものだけ考えればいいので、全体の計算量は $\Theta(nm)$ となる。
実装例
遷移は $c_i, c_{i+1}$ の大小関係によって変わる。
Run #4812557 < misteer < Solutions | Aizu Online Judge
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
|
#include <iostream>
#include <algorithm>
#include <vector>
constexpr int INF = 1 << 30;
bool solve() {
int n, m;
std::cin >> n >> m;
if (n == 0) return false;
std::vector<int> xs(n);
for (auto& x : xs) std::cin >> x;
for (auto& x : xs) {
int y;
std::cin >> y;
x = y - x;
if (x < 0) x += m;
}
// 開いている区間の数がm*i+x個のときの最小操作回数
std::vector<int> dp(n + 1, INF);
dp[0] = 0;
int p = 0;
for (auto x : xs) {
if (x == p) continue;
std::vector<int> ndp(n + 1, INF);
if (p < x) {
int d = x - p;
for (int i = 0; i <= n; ++i) {
// produce
ndp[i] = std::min(ndp[i], dp[i] + d);
// consume
if (i < n) ndp[i] = std::min(ndp[i], dp[i + 1]);
}
} else {
int d = x - p + m;
for (int i = 0; i <= n; ++i) {
// produce
if (i > 0) ndp[i] = std::min(ndp[i], dp[i - 1] + d);
// consume
ndp[i] = std::min(ndp[i], dp[i]);
}
}
std::swap(dp, ndp);
p = x;
}
std::cout << *std::min_element(dp.begin(), dp.end()) << "\n";
return true;
}
|