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

全探索思考に慣れてさえいれば、 の解法ならすぐに思いつく。少し工夫して、 の解法になる！

• 問題へのリンク

問題概要

長さ の数列 が与えられる。数列 の部分数列 であって

• が等差数列である
• である

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

制約

• 
• 

考えたこと

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

---

• を全探索する
• そのそれぞれについて、等しい値がどこまで続くかを求める

---

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

実はちゃんと計算量解析すると、上記の全探索解法の計算量は でもあることが言えて、これでも通るのだけど、ここでは、より分かりやすい の解法を考える。

　

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

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

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

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

---

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

---

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

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

コード

#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;
}