D - サプリメント 〜ABC017〜

問題

D: サプリメント - AtCoder Beginner Contest 017 | AtCoder

考え方

動的計画法を用いる。

AtCoder Beginner Contest 017 解説 の言葉で言う，「dpで足せる区間」を求める際に自分はlatest[i] = jを使った（i というサプリメントが直近で一番最初に出てくる番号はj）。

実装が大変でした。プログラム自体はそこまで長くはないのですが，「dpで足せる区間」が具体的に何に該当するか分かるまでに時間がかかりました。

Accepted Program

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

#define ll long long
#define mod 1000000007
#define max 100001

ll pure[max], latest[max];

void init (void) {
  // 2^n 
  ll sub = 1;
  pure[0] = 1;
  pure[1] = 1;
  latest[1] = -1;
  for (ll i = 2; i < max; i++) {
    latest[i] = -1;
  }
}

int main () {
  init();
  ll n, m;
  cin >> n >> m;
  ll f[n];
  ll ans[n];
  ll sum[n + 1];
  sum[0] = 0;
  ll num[n];
  bool ok[n];
  for (ll i = 0; i < n; i++) {
    cin >> f[i];  
    ans[i] = 0;
    sum[i + 1] = 0;
    num[i] = 0;
    ok[i] = false;
  } 
  for (ll i = 0; i < n; i++) {
    if (i == 0) {
      num[i] = 1;
      latest[f[i]] = 0;  
    }    
    else {
      if (latest[f[i]] == -1) {
        num[i] = num[i - 1] + 1;  
      }  
      else {
        // まずは i の位置とlatest[f[i]]の位置の差を見て
        // num[i - 1]との関係を求める.  
        int j = i - num[i - 1];
        int l = latest[f[i]];
        if (j > l) {
          ok[i] = true;
          num[i] = num[i - 1] + 1;  
        }
        else {
          num[i] = i - l;   
        }
      }
      latest[f[i]] = i;
    }
  }
  for (ll i = 0; i < max; i++) {
    latest[i] = -1;  
  }
  for (ll i = 0; i < n; i++) {
    if (i == 0) {
      ans[i] = 1;
    }    
    else {
      if (num[i] == i + 1) {
        ans[i] = (ans[i - 1] * 2) % mod;  
      }
      else {
        if (ok[i]) {
          ans[i] = (ans[i - 1] * 2) % mod;  
        }
        else {
          ans[i] = (ans[i - 1]) % mod;
          ans[i] = (ans[i] + sum[i - 1]) % mod;
          ans[i] = (ans[i] + mod - sum[i - num[i]]) % mod;     
        }
      }
    }
    sum[i + 1] = (sum[i] + ans[i]) % mod;
    latest[f[i]] = i;
  }
  cout << ans[n - 1] << endl;
}