SRM542 Div1 Med LongestSequence

2015/10/29 (Thu) SRM 牛ゲー 累積和 ☆

問題

問題文

整数列に対する $n$ 個の条件が与えられるので，それらを全て満たす最も長いものを求めてください． ただし $i$ 番目の条件は「数列の任意の長さ $C_i$ の区間の和が正 (または負) になっていないとけない」というものです．

方針

ある数列 $a$ があったとして，その累積和の数列を $s$ とします．つまり，$s[0] = 0, s[i+1] = \sum_{i = 0, \cdots ,i} a[i]$ です． $s$ において，「数列の任意の長さ $c$ の区間の和が正(負)になっていないとけない」という条件は，「任意の $i$ に対して $s[i] < s[i+c]$」と書けます (負なら不等号が逆)． これは $s[i]$ の各要素を頂点，不等式をその向きの有向辺とするグラフと見なせます． 2-SAT と同じような雰囲気の考察をすると，グラフに閉路がない $\Leftrightarrow$ 累積和 $s$ が条件を満たすと言えます． 閉路検出にはいろいろな方法がありあますが，個人的には強連結成分分解を使うのが感覚と一致します．

ちなみに $x_i + c < x_j$ の形の制約のみからなる線形計画問題 (この問題では $c = 0$) を有向グラフに帰着させてとくテクニックのことを俗に牛ゲーというらしいです． よく聞く言葉でしたがはじめて意味を理解しました…

実装

#include <bits/stdc++.h>
using namespace std;

// CUT begin
// TIMESTAMP: 1446055619
// CUT end

struct Edge {
    int src, dst;
    Edge(int src_, int dst_) :
        src(src_), dst(dst_) { }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

int const MAX_V = 100010;
bool scc(const Graph &g){
    static int cmp[MAX_V], added[MAX_V], visited[MAX_V], ord[MAX_V], S[MAX_V];
    const int n = g.size();
    Graph rg(n);
    for(int i = 0; i < n; i++){
        for(auto &e : g[i]) rg[e.dst].emplace_back(e.dst, e.src);
        added[i] = visited[i] = cmp[i] = 0;
    }
    int sz = 0;
    for(int i = 0; i < n; i++){
        if(visited[i]) continue;
        int s = 0;
        S[s++] = i;
        while(s){
            int v = S[s-1];
            visited[v] = true;
            bool pushed = false;
            for(auto & e : g[v]){
                int dst = e.dst;
                if(visited[dst]) continue;
                S[s++] = dst;
                pushed = true;
            }
            if(!pushed){
                int t = S[--s];
                if(added[t]) continue;
                added[t] = true;
                ord[sz++] = t;
            }
        }
    }
    int k = 1;
    for(int i = 0; i < n; i++){
        int u = ord[n-i-1], s = 0;
        if(cmp[u]) continue;
        S[s++] = u;
        while(s){
            int v = S[--s];
            cmp[v] = k;
            for(auto & e : rg[v]){
                int d = e.dst;
                if(!cmp[d]) S[s++] = d;
            }
        }
        k++;
    }
    return k-1 == n;
}

class LongestSequence {
public:
    vector<int> C;
    int maxLength(vector<int> c) {
        C = c;
        int lo = -3, hi = 10000;
        while(lo + 1 < hi){
            int m = lo + (hi - lo)/2;
            if(check(m)){
                lo = m;
            } else {
                hi = m;
            }
        }
        if(hi == 10000) return -1;
        return lo;
    }
    bool check(int l){
        if(l <= 0) return true;
        Graph g(l+1);
        for(int c : C){
            for(int i = 0; i <= l; i++){
                if(i+c >= 0 && i+c <= l){
                    g[i].emplace_back(i,i+c);
                }
            }
        }
        return scc(g);
    }
};