ARC 022 B

今回はこの問題を解きました。

arc022.contest.atcoder.jp

Ncmの細長いお菓子があります。このお菓子は1cmごとにブロックで分けられていて、i番目のブロックはAi番目の味がします。同じ味のブロックを二つ以上含まないひとつながりになった部分のうち、最も長いものの長さを求めましょう、という問題です。

わからなかったので解説を見ました。しゃくとり法で解きました。

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring> 
#include <sstream>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
 
using namespace std;
 
#define pai 3.14159265359
#define mod 1000000007

int main()
{
    int n;
    cin >> n;
    vector<int> result(n + 1, 0);
    int a[100001];
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    vector<int> lastappear(100001, 0);
    result[0] = 1;
    for(int i = 1; i <= n; i++){
        // cout << i << endl;
        // resultは一つ前のものより1減る
        result[i] = result[i - 1] - 1;
        // 今からa[i + result[i]]番目のをつける
        while(i + result[i] <= n){
            int nextcolor = a[i + result[i]];
            if(lastappear[nextcolor] >= i) break;
            lastappear[nextcolor] = i + result[i];
            result[i]++;
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
        // cout << result[i] << endl;
        ans = max(ans, result[i]);
    }
    cout << ans << endl;
}

1番目のブロックから、どこまで長くのばせるかを見ていきます。その結果がresultに記録されていきます。lastappear[i]はi番目の味がするブロックが最後に現れたのが何番目かを表しています。
i番目のブロックをどこまでのばせるか考えます。i-1番目がのばせたところまではのばすことができるので、とりあえずresult[i]=result[i-1]-1にします(1減らしたのはi番目のブロックの分)。そこから、順番に追加できるか判別していきます。nextcolorが次に追加しようとしているブロックの味です。味じゃなくて色と勘違いしてたのでcolorになってます。で、この味が最後に出てきたのがi番目のブロックより左側であったら追加できるのでlastappearとresultを更新します。これを右端にたどり着くまで、もしくは追加できなくなるまで繰り返します。
あとはresultのうち最大のものを出力すればオッケーです。