Codeforces Round #676 (Div. 2) E. Swedish Heroes

問題

面白いな〜と思った問題なので、是非一度考えて見てください!

codeforces.com

長さNの数列Aに対して隣接する要素 A_i,A_{i+1} を選び、その和の符号を逆にしたもので置き換える操作を繰り返して、長さ1の数列を作る。 残る要素を最大化せよ。

解法(ネタバレ注意)

最後に残る要素は、各要素A_iについて正負を決め(+A_i / -A_i)、その和を取ったものになっています。 ある正負の決め方が達成可能かどうかは以下の条件で簡潔に書くことができます。

正負の決め方を +-++-.... のように書くとき、出現する-の個数をMとすると

  • 「(N+M) mod 3 = 1」 かつ「 +- が常に交互に現れる列ではない」

まず、1つ目の条件は実は正負の決め方に対して (N+M) mod 3 が不変量になっていることからわかります。 操作前の状態を(N,M)とすると、操作による変化は以下の2通りです。

  1. ++- とする変化、(N,M)→(N-1,M+1)
  2. --+ とする変化、(N,M)→(N-1,M-2)

これによって (N+M) mod 3 の値は変化しません。 最後(N=1)の正負の決め方は + が残るようにしなければならないことを考えると (N+M) mod 3 = 1 となります。

この条件だけでは、+-+-+-+-+ のように交互に現れる列に対応することができません。 一方、初期状態がこのように常に交互に現れる列でなければ必ず最後まで操作をやり切ることができます。

よって、最初に書いたような条件が成立する正負の決め方は必ず達成でき、これを満たす列を考えたDPによって問題を解くことができます。

DP[i][j][k][pre] := 「iまで見て」「mod 3 の値が j」 「常に交互が連続しているか k」 「1つ前の符号がpre」 の状態の最大値

のような形になります。

ll dp[200010][3][2][2];

int main(){
  int n;
  cin>>n;
  vector<ll> a(n);
  rep(i,n)cin>>a[i];
 
  if(n==1){
    cout<<a[0]<<endl;
    return 0;
  }
 
  int ar=1-(n%3);
  if(ar<0)ar+=3;
 
  rep(i,n+1)rep(r,3)rep(con,2)rep(pre,2)dp[i][r][con][pre]=-INF;
  // +
  dp[1][0][0][0]=a[0];
  // -
  dp[1][1][0][1]=-a[0];
  repl(i,1,n)rep(r,3)rep(con,2)rep(pre,2){
    // +
    maxch(dp[i+1][r][!(con==0&&pre==1)][0],dp[i][r][con][pre]+a[i]);
    // -
    maxch(dp[i+1][(r+1)%3][!(con==0&&pre==0)][1],dp[i][r][con][pre]-a[i]);
  }
  cout<<max(dp[n][ar][1][0],dp[n][ar][1][1])<<endl;
 
  return 0;
}