ARC 170

Fri, May 16, 2025

A. Yet Another AB Problem

https://atcoder.jp/contests/arc170/tasks/arc170_a

B. Arithmetic Progression Subsequence

https://atcoder.jp/contests/arc170/tasks/arc170_b

解説 AC.

以下のサイトを見て理論は理解したが、$O(NM^2)$ 解法の等差数列判定の部分が理解できなかった。 https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2024/0121_arc170

$O(NM^4)$ 解法であれば解けた。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;
    vint A(N);
    rep(i, N) cin >> A[i];

    auto is_seq = [&](int l, int r) -> bool {
        bool ok = false;
        r++;
        rep2(i, l, r) {
            rep2(j, i + 1, r) {
                rep2(k, j + 1, r) {
                    if (A[j] - A[i] == A[k] - A[j])
                        ok = true;
                }
            }
        }
        return ok;
    };

    ll ans = N * (N + 1) / 2;
    rep(l, N) {
        rep2(r, l, N) {
            if (is_seq(l, r)) {
                break;
            } else {
                ans--;
            }
        }
    }
    cout << ans << endl;
}