【AtCoder】ABC 466 E - Range Flip

2026-07-14

AtCoder/ABC/E問題 AtCoder/ABC/450点問題 AtCoder/緑Diff AtCoder/NoviSteps/1Q AtCoder/条件の言い換え AtCoder/動的計画法/Next DP 競技プログラミング

E - Range Flip

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 1027 / NoviSteps: 1Q / 配点: 450 点

問題概要

$N$ 枚のカードが並んでいて、カードには $1, 2, \ldots, N$ の番号が付けられている。カード $i$ の表面には整数 $A_i$ が、裏面には整数 $B_i$ が書かれており、はじめ、すべてのカードは表面が上を向いている。

これから、以下の操作を高々 $K$ 回行うことができる。

$1 \leq l \leq r \leq N$ なる整数 $l, r$ を選ぶ。 $l \leq i \leq r$ なる各整数 $i$ について、カード $i$ を裏返す。

操作を終えた後、各カードの上を向いている面に書かれている数の総和として考えられる最大値を求めよ。

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq K \leq 10$
$1 \leq A_i, B_i \leq 10^9$
入力される値はすべて整数

考察

問題の言い換え

まず、重要な考察として、「重複した区間の操作は考える必要がない」ということが挙げられる。

例えば、 $(l, r) = (2, 5), (4, 7)$ という2回の操作を行った場合、カード $4, 5$ は2回裏返されることになり、元の状態に戻ってしまう。つまり、これらの操作は、 $(l, r) = (2, 3), (6, 7)$ という2回の操作と同じ結果になる。

したがって、高々 $K$ 回の区間反転によって裏面になるカードの集合は、必ず高々 $K$ 個の互いに重ならない区間で表すことができ、逆に、高々 $K$ 個の互いに重ならない区間をそれぞれ1回ずつ裏返せば、その状態を実現できる。

また、カード $i$ を裏返すことによって変化する $N$ 枚のカードの総和は、 $D_i = B_i - A_i$ と書ける。

したがって、この問題は

長さ $N$ の数列 $(D_1, D_2, \ldots, D_N)$ が与えられるので、高々 $K$ 個の互いに重ならない区間を選び、その区間に含まれる整数の総和を最大化せよ。

と言い換えられる。

動的計画法で解く

言い換えた問題は、動的計画法によって解くことができる。

ここでは、以下の2つのDPテーブルを定義する。

$\mathrm{dp}_0[i][j] :=$ ここまでに $j$ 個の区間を選び、カード $i$ を裏返さない場合の $D_i$ の総和の最大値
$\mathrm{dp}_1[i][j] :=$ ここまでに $j$ 個の区間を選び、カード $i$ を裏返す場合の $D_i$ の総和の最大値

初期値は、 $\mathrm{dp}_0[0][0] = 0$ であり、他の値は $-\infty$ とする。

各 $i = 1, 2, \ldots, N$ について、以下の遷移を行う。

カード $i$ $i$ を裏返さない場合
- カード $i-1, i$ 共に裏返さない場合と、 $j$ 個目の区間をカード $i-1$ までで終了させる場合の2パターンを考える(カード $i-1$ の状態は関係ない)。
- $\mathrm{dp}_0[i][j] = \max(\mathrm{dp}_0[i-1][j], \mathrm{dp}_1[i-1][j])$
カード $i$ $i$ を裏返す場合
- カード $i$ を $j$ 個目の区間の最初のカードとして裏返す場合と、 $j$ 個目の区間に含める場合の2パターンを考える。
- $\mathrm{dp}_1[i][j] = \max(\mathrm{dp}_0[i-1][j-1], \mathrm{dp}_1[i-1][j-1]) + D_i$

言い換えた問題の答えは $\max(\mathrm{dp}_0[N][j], \mathrm{dp}_1[N][j]) \quad (j = 0, 1, \ldots, K)$ であり、最終的な答えはこれに $\sum_{i=1}^{N} A_i$ を加えた値となる。

各カードについて、区間数 $j = 0, 1, \ldots, K$ を考えるため、計算量は $O(NK)$ となる。

実装例

DPテーブルを使いまわすことで、空間計算量を $O(K)$ に削減することができる。

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5. 
6.constexpr long long INFL = 1e+18;
7. 
8.using ll = long long;
9. 
10.template <typename T>
11.inline bool chmax(T& a, T b) { return ((a < b) ? (a = b, true) : (false)); }
12. 
13.// ======================================== //
14. 
15.int main()
16.{
17.    int N, K;
18.    cin >> N >> K;
19.    vector<ll> A(N), B(N);
20.    ll ans = 0;
21.    rep(i, 0, N) cin >> A[i] >> B[i], ans += A[i];
22. 
23.    vector<ll>  dp0(K + 1, -INFL), dp1(K + 1, -INFL);
24.    dp0[0] = 0;
25.    rep(i, 0, N) {
26.        ll diff = B[i] - A[i];
27. 
28.        vector<ll> ndp0(K + 1, -INFL), ndp1(K + 1, -INFL);
29.        rep(j, 0, K + 1) {
30.            ndp0[j] = max(dp0[j], dp1[j]);
31. 
32.            if (j >= 1) {
33.                ndp1[j] = max(dp0[j - 1], dp1[j]) + diff;
34.            }
35.        }
36. 
37.        swap(ndp0, dp0);
38.        swap(ndp1, dp1);
39.    }
40. 
41.    ll add = 0;
42.    rep(i, 0, K + 1) chmax(add, max(dp0[i], dp1[i]));
43. 
44.    cout << ans + add << endl;
45. 
46.    return 0;
47.}