ABC161 - F - Select Half
概要
N個の要素からなる数列A[]で、floor(N/2)個の要素を選ぶ。ただし、選ばれたものは隣り合ってはならない。その和を最大化せよ。
制約： 1 <= N <= 2 * 10^5, |A[i]| <= 10^9
ACするまで
考察ノートを考察パートで載せる。
考察
僕の解法
これが本番中書いた考察ノート。(DPの実装に手間取ってて時間内ACできなかったorz 猛反省しろ to me)
まず、Nが偶数の場合は上の通りである。これは、両側から(ox)パターンと(xo)パターンの累積和を取っておけば、変化するポイントごとにO(1)で計算できるため、O(N)で求まる。
Nが奇数だった場合、選ばれない(ここでは×)が1つ増えて、さらに場合分けが増える。これは考察ノートの下に書いてある通り
この時、同偶の記号がついてるのは、偶数の場合での操作でカバーできてる。
カバーできてないのは、1つoを飛ばしたパターン(xoxxxoxの場合)と、一番下にある、xxが2回連続するパターン
- 1つ飛ばし、つまりoxoxoxoの場合は、累積和を使えば、飛ばす場所ごとにO(1)で計算できるので、全部試すことでO(N)でできる。
- xxが2回連続するパターンは、
dp[i][j] := i個目まで見て、jの状態(最初の(ox)中か、次の(xo)中か、最後の(ox)中か)での最大値
とDPを計算すればできる。(To me: 素直に実装しろ!!!)
ACソースコード：
Submission #11860512 - AtCoder Beginner Contest 162
解説の解法
上のような場合分けをした理由としては、単純に
dp[i][j] := i個目まで見て隣り合わずにj個選んだ時の最大値
これは遷移にO(1)、回すのにO(N^2)なので、間に合わない。
しかし、大体半分選ぶ上、かつ2つ連続は無理ということから、あるiについてのとれる数jというのは実はかなり少ない。(たかだか3通りしかない)
よって、計算量はO(N)にまで落ちる。(解説の方が分かりやすい)
一言
もう勝利には近いはず。
