全探索思考に慣れてさえいれば、 $O(N^{3})$ の解法ならすぐに思いつく。少し工夫して、 $O(N^{2})$ の解法になる！

問題へのリンク

問題概要

長さ $N$ の数列 $H_{1}, H_{2}, \dots, H_{N}$ が与えられる。数列 $H$ の部分数列 $H_{i_{1}}, H_{i_{2}}, \dots, H_{i_{K}}$ であって

$i_{1}, i_{2}, \dots, i_{K}$ が等差数列である
$H_{i_{1}} = H_{i_{2}} = \dots = H_{i_{K}}$ である

という条件を満たすものを考える。それらの数列の最大長を求めよ。

制約

$1 \le N \le 3000$
$1 \le H_{i} \le 3000$

考えたこと

パッと思いつくのは、次の解法だと思う。

$i_{1}, i_{2}$ を全探索する
そのそれぞれについて、等しい値がどこまで続くかを求める

調べるべきものは $O(N^{2})$ 通りある。それぞれの場合に対して、等しい値がどこまで続くかを求めるのには $O(N)$ の計算量を要するので、全体として $O(N^{3})$ の計算量となる。

実はちゃんと計算量解析すると、上記の全探索解法の計算量は $O(N^{2} \log N)$ でもあることが言えて、これでも通るのだけど、ここでは、より分かりやすい $O(N^{2})$ の解法を考える。

部分数列の間隔ごとに考えてみる

ここで、部分数列の間隔 $d$ のみを固定して考えることにする。

まず、数列 $H_{1}, H_{2}, \dots, H_{N}$ は、添字を $d$ で割った余りで分類することで、 $d$ 個の数列に分けて考えることができるに注意する。下図は $N = 14$ , $d = 3$ の場合を 0-indexed で示したものである。この例では、添字 4, 7, 10 がすべて値「2」で、3 が最大長となる。

このように数列を分けると、各数列に対して次の問題を考えればよいことになる。

与えられた数列において、同じ値が最大で何個連続しているかを求めよ。

この問題は、数列の長さを $L$ として、 $O(L)$ の計算量で解ける。

$d$ 個の数列の長さの総和は $N$ であるから、結局、 $d$ 個の数列について上記の問題を解くのに要する計算量は $O(N)$ と評価できる。 $d$ が $O(N)$ 通りあるから、全体の計算量は $O(N^{2})$ と評価できる。

コード

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

int main() {
    int N;
    cin >> N;
    vector<int> H(N);
    for (int i = 0; i < N; i++) cin >> H[i];

    int res = 1;

    // 数列の間隔 d を全探索する
    for (int d = 1; d < N; d++) {
        // 数列全体を d 個に分割して解く
        for (int r = 0; r < d; r++) {
            // 分割して得られた数列に対して、同じ値が最大何個連続しているかを求める
            int num = 1, prev = -1;
            for (int i = r; i < N; i += d) {
                if (H[i] == prev) {
                    num++;
                    res = max(res, num);
                } else {
                    num = 1;
                    prev = H[i];
                }
            }
        }
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 385 C - Illuminate Buildings (2Q, 茶色, 350 点)

問題概要

制約

考えたこと

部分数列の間隔ごとに考えてみる

コード