CS Academy 081 DIV2 D - Gerrymandering

貪欲でも、実家 DP でも、ソシャゲ DP 的な DP でも解けるみたいなのんな。これ、実装がややこしくて、苦手なんて言葉ではいい表せないほどの超絶苦手系なのん。。。

Gerrymandering 問題へのリンク

問題概要

N 個の街が一直線上に並んでいて、各街は 2 種類の属性をもっており 4 種に分類される。

• A or B？ (A 国か B 国か)
• S or L？ (small か large か)

各街を連続する区間に分割して行きたい。ただし

• どの区間も L を含まないといけない

という制約がある。あらゆる分割方法を考えたとき、「A が B よりも多く含まれている区間の個数」が最大になるようにせよ。

制約

• [tex: 1 \le N \le 10⁵]

考えたこと

公式解法はこっちっぽい。区間を分割する DP は定番で、この問題でも以下のように書けるん (配る DP):

---

dp[ i ] := 最初の i 個で一区切りつけたときの、そこまでの条件を満たす区間の個数の最大値

[j, i) が L を含むような j に対して

dp[ i ] = max(dp[ i ], dp[ j ] + f(j, i))
f(i, j) = 区間 [j, i) が A を B より多く含むかどうか (含むなら 1)

---

このままだと、[tex: O(N²)] かかるん。そこで世の中にはこういうのを高速化するために、

• 累積和
• スライド最小値
• インライン DP
• Convex Hull Trick
• ソシャゲ DP

といったテクニックたちが知られているん。今回はソシャゲ DP 的なのが結構いい感じなん。まず、

• 分割された各区間に L はちょうど 1 個ずつ含むとしてよい

これは最適解に L を 2 個以上含むような区間があったとき、解を悪化させずに分割できるからなん。次に、dp[ i ] を dp[ j ] から更新するような j として特に

• [j, i) に L があって Aの数 >= Bの数になるような j があるなら、そのような j の中で dp[j] が最大となるような j
• dp[j] が最大となるような j

のみを考えればよいことがわかる。前者が一見 かかるように見えるのだが、

• dp[ j ] の値が、[0, j) の L の個数が同一の場合には、(A の個数 ) - (B の個数) に応じて決まる

ということを利用すると、上手く処理することができる。

#include <iostream>
#include <vector>
using namespace std;

int N;
vector<int> isA, isL, sumA;

int main() {
  cin >> N;
  int INF = N+10;
  isA.resize(N+1); isL.resize(N+1); sumA.resize(N+1);
  sumA[0] = 0;
  for (int i = 0; i < N; ++i) {
    char a, b; cin >> a >> b;
    isA[i] = (a == 'A' ? 1 : -1);
    isL[i] = (b == 'L');
    sumA[i+1] = sumA[i] + isA[i];
  }

  int curL = 0, preL = 0, maxdp = -1, minsum, maxsum;
  vector<int> dp(N+1, -INF), dps(N*2+10, -1);
  dp[0] = 0;
  for (int i = 1; i <= N; ++i) {
    if (isL[i-1]) {
      preL = curL;
      curL = i;

      minsum = 1<<29, maxsum = -1;
      for (int j = preL; j < curL; ++j) {
        minsum = min(minsum, sumA[j]);
        maxsum = max(maxsum, sumA[j]);
      }

      for (int j = 0; j <= maxsum - minsum; ++j) dps[j] = -1;
      for (int j = preL; j < curL; ++j) {
        dps[sumA[j] - minsum] = max(dps[sumA[j] - minsum], dp[j]);
      }
      for (int j = 1; j <= maxsum - minsum; ++j) {
        dps[j] = max(dps[j], dps[j-1]);
      }

      maxdp = dps[maxsum - minsum];
    }
    
    if (maxdp == -1) continue;

    if (sumA[i] >= maxsum) dp[i] = maxdp + 1;
    else if (sumA[i] >= minsum) dp[i] = max(maxdp, dps[sumA[i] - minsum] + 1);
    else dp[i] = maxdp;
  }
      
  cout << dp[N] << endl;
}