ABC162 F - Select Half
April 14, 2020
問題
考えたこと(間違い解法)
Nが偶数の場合は取り方は2つしかないはず
例えばN=8として、●=取る ○=取らない とした場合
○●○●○●○●●○●○●○●○
この2つの大きい方が解と出来そう
問題は奇数の場合, N=5とした場合以下の取り方が考えられる
●○●○○●○○●○●○○○●○●○●○○●○○●○○●○●
このままだとパターンが多過ぎて計算できない。
そこで5番目の要素を取るか取らないかで場合分けしてみる
5番目の要素を取らない場合
1から4までの中から2つ取るという問題になる。
これは偶数の時考えた方法なので、2パターンしかない、つまり
●○●○○●○●
5番目の要素を取る場合は、隣り合う数は選べないので4番目の数は使えなくなる
1~3番目の中から1つとって一番大きいのを5番目の値と組み合わせたのが、5番目を選んだときの最大値となる
これを再帰的にやっていくとできそう、計算量もO(N)なので
// 予め, 奇数/偶数番目を全て取った時にi時点までに合計いくつになるかというのを計算しておく
vector<ll> odd(n);
vector<ll> even(n);
// 現在選ばれている数の合計を覚えておく
ll now = 0;
ll ans = 0;
for(int i=n-1; i > 0; i-=2) {
// iを取らない場合
ans = max(ans, even[i] + now);
ans = max(ans, odd[i] + now);
// iを取る場合
now += a[i];
}
間違い
偶数の時に2パターンしかないというのが誤り
以下のようなパターンもあり得る
●○○●
解法
解説をみながら考える
2次元DPでやるDP[i][j]として、i番目までのうち、連続しないj個を選んだ時の和の最大値
ただこれだと、O(N^2)になってしまうので、遷移を減らす必要がある
解法にも記載されているように、連続したのを選ばずにN/2個を選ぼうとすると
i時点で最低でもX個は選ばないといけないし, 最大でもY個しか選べないので[j]の遷移はかなり少ない
実際いくつ必要か実験してみる
ちょっとシミュレートしてみよう
N=7とした場合
取らないといけないのは7/2 == 3個
ここでi=3時点でのX,Yを考える
i=4~7で3つ取ることは不可能なので最低でも1つは取っておかないといけない
つまりX=1
最大は1番目と3番目を取ることで、2つ取れるのでY=2となる
i=4時点を考える
i=5~7で取れる最大は2つなので最低でも1つは取っておかないといけないのでX=1
1~4では2つ作れるのでY=2
i=5時点を考える
i=6,7では最大でも1つしか作れないので、1~5で2つ作らないといけないX=2
1,3,5を選んだ場合に3つ作れるのでY=3
残りはi=6はX=2, Y=3, i=7はX=3, Y=4
となる
i番目における状態はたかだか2つ
こうみると,i時点での状態は必ず2状態(Y-X == 1)しかないことがわかる
この2状態の遷移だけ考えるとよさそう
dp[i][0] : i番目までの中から最小限を選ぶ時の和の最大値dp[i][1] : i番目までの中から最大限を選ぶ時の和の最大値
あとはこれら2つに対して、a[i]を取るか取らないかでやればいい
実際は以下のようになる
奇数の場合の最大限の取り方だけは条件があるので気を付けること
for(int i=2; i<n; i++) {
// i番目を選んで, 最小限が選ばれている状態
dp[i][0] = max(dp[i][0], dp[i-2][0] + a[i]);
// i番目を選ばずに, 最小限が選ばれている状態
dp[i][0] = max(dp[i][0], dp[i-1][1]);
// 最大限を選ぶ状態は偶奇で別れる
if(i%2==0) {
// 奇数の場合は、i番目を選ばないと絶対に最大限は選べない
// i == 5の場合の最大限は3, それを達成するには1,3,5という取りかたしかない
// i番目を選んで, 最大限選ばれてる状態
dp[i][1] = max(dp[i][1], dp[i-2][1] + a[i]);
} else {
// 偶数の場合は, i番目を選ぶ時と選ばないときの2パターンがある
dp[i][1] = max(dp[i][1], dp[i-2][1] + a[i]);
dp[i][1] = max(dp[i][1], dp[i-1][1]);
}
}
実装で引っかかった部分
vectorのサイズを大きくしすぎるとTLEになる
最初はdpテーブルのサイズをdp[n][n+1]ってやってた
(最小限、最大限って感じ出なく、最小限, 最大限の実際の値で遷移してた)
これだとTLEになる(MLEじゃないんだな)
vector<vector<ll>> dp(n, vector<ll>(n+1, -LONG_MAX));
for(int i=2; i<n; i++) {
chmax(dp[i][i/2], dp[i-2][(i/2)-1] + a[i]);
chmax(dp[i][i/2], dp[i-1][i/2]);
chmax(dp[i][(i+1)/2], dp[i-2][((i+1)/2)-1] + a[i]);
}
dpテーブルの初期値が十分に小さくなった
制約見てA[i]の最小値が-1e9だったので、dpテーブルの初期値を-(1e9+5)くらいにしていたがこれだとA[i]が全て-1e9とかの場合に初期値以下の答えになってしまう。-1e9 * 1e5(nの最大値)くらいにしておかないといけない
提出コード
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }
using Graph = vector<vector<int>>;
using P = pair<int, int>;
using Tuple = tuple<int, int, int>;
int main() {
ll n; cin >> n;
vector<ll> a(n);
rep(i, n) cin >> a[i];
// dpテーブルの用意
// dp[i][0] = a[0]~a[i]までから最小限をとるときの最大値
// dp[i][1] = a[0]~a[i]までから最大限をとるときの最大値
// 初期値は十分小さな値にしておくこと
// a[i]が全て `-10^9` だとしたら、-10^9 * 10^5(nの最大値)より小さい値でないとだめ
vector<vector<ll>> dp(n, vector<ll>(2, -1e17));
// 初期値を埋めておく
dp[0][0] = 0;
dp[0][1] = a[0];
dp[1][0] = max(a[0], a[1]);
dp[1][1] = max(a[0], a[1]);
// dpテーブルを埋めていく
for(int i=2; i<n; i++) {
// i番目を選んで, 最小限が選ばれている状態
dp[i][0] = max(dp[i][0], dp[i-2][0] + a[i]);
// i番目を選ばずに, 最小限が選ばれている状態
dp[i][0] = max(dp[i][0], dp[i-1][1]);
// 最大限を選ぶ状態は偶奇で別れる
if(i%2==0) {
// 奇数の場合は、i番目を選ばないと絶対に最大限は選べない
// i番目を選んで, 最大限選ばれてる状態
dp[i][1] = max(dp[i][1], dp[i-2][1] + a[i]);
} else {
// 偶数の場合は, i番目を選ぶ時と選ばないときの2パターンがある
dp[i][1] = max(dp[i][1], dp[i-2][1] + a[i]);
dp[i][1] = max(dp[i][1], dp[i-1][1]);
}
}
// 奇数でも偶数でも最小限を選んでる状態を出せばいい(nが奇数の時に最大限だと取りすぎになる
cout << dp[n-1][0] << endl;
return 0;
}