Codeforces Round #625 (Div. 1) A. Journey Planning (R1400)

面白かった

問題へのリンク

問題概要

要素の数列 が与えられる。以下の条件を満たすような部分数列のうち、要素和の最大値を求めよ。

• 抜き出した数列のどの 2 項についても「値の差分」と「index の差分」とが等しい

制約

• 

考えたこと

たとえば の場合は、このように考えれば簡明。各要素をその index で引く。そうすると

となる。元の条件は「抜き出した部分について、どの 2 項をとっても、この変換後の数列の値が等しい」という条件になる。あとは、この値ごとに調べれば OK。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int N;
vector<long long> a;

long long solve() {
    map<long long, long long> num, ma;
    for (int i = 0; i < N; ++i) {
        num[a[i] - i]++;
        ma[a[i] - i] += i;
    }
    long long res = 0;
    for (auto it : ma) chmax(res, it.first * num[it.first] + it.second);
    return res;
}

int main() {
    while (cin >> N) {
        a.resize(N);
        for (int i = 0; i < N; ++i) cin >> a[i];
        cout << solve() << endl;
    }
}