こんにちは。こどふぉでした。
レートちょっと下がったと思う。悲しい。ちなみに↑の提出コードはSubmission #85050166 - Codeforces
さて、今回は、本番中に解けなかったDを解きます。
Dについてコンテストページのチャットなどを見ていたら「Kadane's algorithm」というワードが出てきました。それを手掛かりになんとか解けそうな気がしたので解いていきます。
問題
（本家→）Problem - D - Codeforces
（概略）数列 $a$ が与えられる。数列の中から連続する部分列を最大1つ選んで反転させることができる。0-based（0始まり）で数えて偶数番目の数字の和（$a_0 + a_2 + \cdots$）を最大にせよ。
例
$a = \{1,2,1,2,1\}$ のとき、範囲 $[0,4]$ を反転させて $a = \{2,1,2,1,1\}$ にすれば $a_0+a_2+a_4 = 2+2+1 = 5$ で最大。
解法
発想
まず、反転させる範囲は偶数個でないといけない。奇数個の範囲を反転させてもそれぞれの数字のindexの偶奇は変わらないため。
偶数個の範囲を反転させるという操作は、偶数index（$:=$indexが偶数の項）の和を考えると「隣同士反転させる」の連続と同じ
$$
a = \{1,2,3,4,5,6\}
$$
の全体を反転させると
$$
a = \{6,5,4,3,2,1\}
$$
だけど、偶数indexの和について知りたいだけなら
$$
a = \{[2,1],[4,3],[6,5]\}
$$
のようにしても同じ。
上記の操作は、各偶数indexが、自分の右側の数を「もらう」ことで偶数indexの和が大きくなっている。一方、以下のような数列 $a$ を考えると
\begin{align}
&a = \{9,6,5,4,3,2,1\} → \sum\rm{偶数index} = 9+5+3+1 = 18 \cr
&\rm{偶数index}が右からもらうと\cr
&a = \{[6,9],[4,5],[2,3],1\} → \sum\rm{偶数index} = 6+4+2+1 = 13 \cdots\rm{減ってる}\cr
&\rm{偶数index}が左からもらうと\cr
&a = \{9,[5,6],[3,4],[1,2]\} → \sum\rm{偶数index} = 9+6+4+2 = 21 \cdots\rm{増えた！}
\end{align}
ということで「左からもらう」ことも考えなければいけない。
以下、$\rm{偶数indexの和} = \sum\rm{偶数index} = a_0+a_2+\cdots$ を $x$ とする。
一旦「右からもらう」ことだけを考える。数列 $a =\{7,8,4,5,7,6\}, x=18$ についてもらったときの利益brを偶数indexの下に書いてみると以下のようになる
| i |
0 |
1 |
2 |
3 |
4 |
5 |
| a[i] |
7 |
8 |
4 |
5 |
7 |
6 |
| br |
1 |
|
1 |
|
-1 |
|
brは場合によっては負にもなるわけだが、ともかく、brの部分列の中で一番大きい括りで「反転」＝「右からもらうの連続」をやれば良さそうなので、$a_0, a_2$ が「右からもらう」と $a = \{[8,7],[5,4],7,6\}, x=20$ となる。
一方、「左からもらう」ことも考えてみると、左からもらったときの利益blは
| i |
0 |
1 |
2 |
3 |
4 |
5 |
| a[i] |
7 |
8 |
4 |
5 |
7 |
6 |
| br |
1 |
|
1 |
|
-1 |
|
| bl |
|
|
4 |
|
-2 |
|
となる。blの部分列のなかで一番大きくなる括りで「反転」すると $a_2$ が「左からもらう」ので $a = \{7,[4,8],5,7,6\}, x=22$ となる。
ということで最適なのは範囲 $1,2$ の反転でした。
Kadane's algorithm
さて、ここまでくると知りたいのが「最大部分配列」の求め方です。
を参考にしました。
最大部分配列問題(maximum subarray problem)とは、与えられた配列に対して、その(連続した)部分配列のうち和が最大となるものの値を求める問題のことです。
Kadane’s Algorithm | 最大部分配列 問題 - Ark's Blog
上記サイトをじっくり読んだら理屈はわかったので詳細は割愛しますが、プログラムとしては
long solve(int n, long[] as) {
long res = -INF;
long s = 0;
foreach(j; 0..n) {
s = max(s + as[j], as[j]);
res = max(res, s);
}
return res;
}
Kadane’s Algorithm | 最大部分配列 問題 - Ark's Blogより
となるそうです。↑はD言語なのでC++に書き換えると（数値は一旦intで）
int solve(int n, vector<int> &as){
int res = -INF;
int s = 0;
for(int j=0; j<n; j++){
s = max(s + as[j], as[j]);
res = max(res, s);
}
return res;
}
全然変わってないけど。
brやblは利益の配列なので、最大部分配列がそのまま最大の利益となる。よって最初に反転なしの偶数indexの和を出しておいて、「brについての最大部分配列」と「blについての最大部分配列」の（0を超えていて）大きい方を足せば求めたい $x$ になる。
実装
今回は $a$ の条件が $1 \le a_i \le 10^{9}$ なのでres = -1e9と初期値を設定しました。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vl = vector<ll>;
#define rep(i, n) for(int i=0; i<(int)n; i++)
ll kadane(ll n, vl &a){
ll res = -1e9;
ll s = 0;
for(ll j=0; j<n; j++){
s = max(s+a[j], a[j]);
res = max(res, s);
}
return res;
}
void solve(){
int N;cin>>N;
vl a(N);
ll sum = 0;
rep(i,N){
cin>>a[i];
if(i%2==0)sum += a[i];
}
vl br, bl;
for(int i=0; i<N; i+=2){
if(i!=0)bl.push_back(a[i-1]-a[i]);
if(i!=N-1)br.push_back(a[i+1]-a[i]);
}
ll add = max({
0LL,
kadane(br.size(), br),
kadane(bl.size(), bl)
});
cout<<sum+add<<endl;
}
int main(){
int t = 1;
cin>>t;
while(t--)solve();
}
kadaneで求めた最大部分配列が両方マイナスになる可能性（反転させないのが最適）があるのでll add = max()に初期化子リストで（0LL含め）3項入れています。
ACになりました→Submission #85071102 - Codeforces
まとめ
また一つ賢くなった。えらい。
kadene()の引数の配列の方、参照にする必要ないじゃんって思って直接渡したらメモリ使用量増えてあっそうかぁ……てなった（それはそう）。
参考
