mayoko’s diary

プロコンとかいろいろ。

SRM 524 med: LongestSequence

解法

長さ x を決め打ちして, その長さの数列が存在するかを判定します。これができれば後は二分探索をやるだけなので判定方法を考えます。

数列の 1-indexed での座標 x までの和を S[x] とすると, 条件より以下のようにわかります。

C[i] > 0 の時 S[j+C[i]] > S[j]
C[i] < 0 の時 S[j+C[i]] > S[j]
(0 <= j <= x)

(結局式としては同じなんですね)

よって, S[i] > S[j] をみたす整数の組 (i, j) に対して j -> i の有向辺を引いてグラフを作ると,
仮にこのグラフにループがあった場合, ある整数の組 (a, b) について S[a] < S[b] かつ S[a] > S[b] が成り立つことになり矛盾
ループがなかった場合上手いことトポロジカルソートすることによって各 i に対する累積和 S[i] が存在することがわかる

よって, あとはこのグラフに対してループがないことを確認すれば良いです。下のコードでは dfs でやってますがなんでこれで通るのかわからなくなってきました。すぎむさんが強連結成分分解でやっていたと思いますがこっちのほうが安全だと思います。

int n;
bool visit[3030];

bool dfs(int v, int s, const vector<vi>& G) {
    if (visit[v]) return false;
    visit[v] = true;
    for (int ch : G[v]) {
        if (ch == s || dfs(ch, s, G)) return true;
    }
    return false;
}

bool ok(int x, const vi& C) {
    vector<vector<int> > G(x+1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= x; j++) {
            int k = j+C[i];
            if (0 <= k && k <= x) G[j].push_back(k);
        }
    }
    memset(visit, false, sizeof(visit));
    for (int i = 0; i <= x; i++) {
        if (!visit[i]) if (dfs(i, i, G)) return false;
    }
    return true;
}

class LongestSequence {
public:
    int maxLength(vector <int> C) {
        n = C.size();
        int low = 0, high = 3000;
        while (high-low > 1) {
            int med = (high+low)/2;
            if (ok(med, C)) low = med;
            else high = med;
        }
        if (low > 2000) return -1;
        return low;
    }
};