C - Yarik and Array / Codeforces Round 909 (Div. 3)

問題

個の整数からなる数列 が与えられる。

数列 の連続部分列のうち、どの要素も隣接する数字の偶奇が異なるようなものについて、部分列内の要素の和の最大値を求めよ。

入力

まず最初の1行目に、テストケースの個数を表す整数 が与えられる。

その後、 個のテストケースのそれぞれに対して、以下のように入力が与えられる。

• 最初の1行目には、整数 が与えられる。
• 次の1行には、 個の整数 が順に与えられる。

条件

• 
• 
  • すべてのテストケースにおける の値の合計は を超えない。
• 

出力

行にわたり、各テストケースでの答えを1行ごとに出力すること。

解法

まず、要素が1つのみの数列 は条件を満たす部分列となります。 そのため、数列 のすべての要素 について、「条件を満たす部分列のうち、値 が含まれるもの」は必ず存在すると言えます。

このことより、値 を「最終要素を とする条件を満たす部分列のうち、全要素の和として考えられる最大値」として定義します。

ここで が計算されているときに、 の値がどのようになるのか考えます。 問題文より、 と の値の偶奇の組み合わせによって、部分列に入れられるのかどうかが変わるため、

• と の偶奇が異なるとき: 「 を の入る部分列に入れる」もしくは「 のみの部分列にする」が可能
  • を の入る部分列に入れるとき: 和の値は
  • のみの部分列にするとき: 和の値は
• と の偶奇が一致するとき: 「 のみの部分列にする」のみ可能
  • このときの和の値は

というように整理できます。 すなわち、

• と の偶奇が異なるとき:
• と の偶奇が一致するとき:

となります。

従って、 の順に の値を計算していくと、各 を最終要素とする部分列の総和の最大値が求まります。 和の最大値を与える部分列も、いずれかの を最終要素とすることから、 の最大値が求める値となります。

これは、 の計算量で求めることができるので、実行時間制限にも十分間に合います。

ソースコード

求める最大値を返す関数 solve() を以下のように実装しました。

int n, a[int(2e5 + 5)], dp[int(2e5 + 5)];

int solve() {
  // 値の入力
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }

  int ans = -1e9; // 最終的に答えとして出力する値 ans
  for (int i = 1; i <= n; i++) {
    // i = 1 のときは必ず dp[1] = a[1] であり、どちらの分岐になったとしてもこれが得られるので無視しました
    if ((a[i] + a[i - 1]) % 2 == 0) { // 2数の和が偶数であれば、その2数の偶奇は一致する
      dp[i] = a[i];
    } else {
      dp[i] = max(a[i], dp[i - 1] + a[i]); // 偶奇が異なるときは、前の dp[i-1] の値も用いて比較する
    }
    ans = max(ans, dp[i]); // ans の値の更新
  }

  return ans; // 最大値を返す
}

• 提出したコード: https://codeforces.com/contest/1899/submission/237867455
• GitHub

感想

DP（動的計画法）の問題として、非常にシンプルかつ初学者でも取り組みやすい、いい問題だと思いました。