D - サプリメント

時間制限 : 3sec / メモリ制限 : 256MB

問題文

健康志向の高橋君は通販で購入したサプリメントを摂取することにした。

サプリメントは N 個あり、1 から N まで番号が付けられている。

また、サプリメントの味は M 種類あり、1 から M まで番号が付けられている。サプリメント i(1≦i≦N) の味は fi(1≦fi≦M) である。

高橋君はサプリメントを番号順に複数日かけて摂取する予定である。高橋君はサボらないように、サプリメントが 1 つ以上残っている場合はその日中に必ず 1 つ以上サプリメントを摂取しなければならないという規則を定めた。

高橋君は強靭な肉体を持っているため、1 日にどれだけサプリメントを摂取しても大丈夫だが、同じ味には飽きてしまうので、同じ日に同じ味のサプリメントを 2 つ以上摂取することはできない。

高橋君は、サプリメントの摂取方法の是非について吟味するため、このような条件下で全部で何通りの摂取方法があるかを知りたい。

ここで 2 つの摂取方法についてそれらが違うというのは、ある日について摂取したサプリメントの番号の組み合わせが異なることを定義する。

note

累積和と動的計画法でとける。計算量はO(n+m)

#include <iostream>
#include <vector>
#define NMAX 1000010
#define ll long long
#define MOD 1000000007
using namespace std;

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int main(){
    int n,  m;
    //tastes[i] i番目のサプリメントの味
    vector<int> tastes;
    cin >> n >> m;
    tastes.push_back(0);

    for (int i = 0; i < n; ++i)
    {
        int tmp;
        cin >> tmp;
        tastes.push_back(tmp);
    }

    ll dp[NMAX];
    Fill(dp, 0);
    dp[0] = 1;

    ll imos[NMAX];
    imos[0] = 1;

    int start = 0;
    bool check[NMAX];
    Fill(check, false);
    for (int i = 1; i <= n; ++i)
    {
        if(check[tastes[i]]){
            for (int j = start; j < i; ++j)
            {
                if(tastes[i] == tastes[j]){
                    // その味がなくなるまでしゃくとりの左をすすめる
                    start = j + 1;
                    break;
                }
                check[tastes[j]] = false;
            }
        }
        check[tastes[i]] = true;

        if(start == 0){
            dp[i] = imos[i - 1] % MOD - 0;
        }else{
            dp[i] = (imos[i - 1] - imos[start - 2] + MOD) % MOD;
        }
        dp[i] %= MOD;
        imos[i] = imos[i-1] + dp[i];
        imos[i] %= MOD;
        // cout << dp[i] << " " << imos[i] << " "<< start  << " i "<< i << endl;
    }
    cout << dp[n] % MOD << endl;

}

TakefumiYamamura / programming_contest

AtCoder Beginner Contest 017 #30

D - サプリメント

問題文

note