ジャンプの過程を無視して、最終的に出来上がるものがどうなるかを考えて、それをわかりやすく特徴づける
調和級数になるタイプの全探索

というタイプの問題。結構重たい。AGC なら C 問題でありそう。

問題概要

$N$ 個の地点 $0, 1, \dots, N-1$ にそれぞれ $s_{0}, s_{1}, \dots, s_{N-1}$ のスコアがある。

0 から出発してぴょんぴょんジャンプしながら $N-1$ を目指す
「すでに踏んだところ」または「0 未満」または「N 以上」の地点を踏んだらゲームオーバー

というルールで、最初に整数 $A, B$ を決めて、

$0$ から出発して、 $A$ 右に飛んで、 $B$ 左に飛んで、、、(踏んだところのスコアを得ていく)

を繰り返す。最終的に $N-1$ に到達する方法のうち、得られる総スコアの最大値を求めよ。

制約

$3 \le N \le 10^{5}$
$s_{0} = s_{N-1} = 0$

考えたこと

$A = N-1$ の場合はスコア 0。以後 $A \lt N-1$ とする。

とりあえず $A \gt B$ としてよい。そうでなかったら 2 ターン目で終わってしまう。ここで $C = A - B$ とおくと、これがちょっと特別な感じの値になっている。というのも最終的に踏む地点は

$C, 2C, \dots$
$N-1, N-1-C, N-1-2C, \dots$

みたいになる。 $C$ の値をすべて調べて、両端からどこまで伸ばすかを全部調べれば OK。これは調和級数の和になってて全部で $O(N\log{N})$ の計算量になる。

$C$ が $N-1$ の約数のときだけ注意して場合分けしてやった。

#include <iostream>
#include <vector>
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 main() {
    int N; cin >> N;
    vector<long long> s(N);
    for (int i = 0; i < N; ++i) cin >> s[i];

    long long res = 0;
    for (int p = 1; p <= N-1; ++p) {
        if ((N-1) % p == 0) {
            long long tmp = 0;
            long long cur = 0;
            int i = 0, j = N-1;
            for (; i < j; i += p, j -= p) {
                cur += s[i] + s[j];
                chmax(tmp, cur);
            }
            chmax(res, tmp);
        }
        else {
            long long tmp = 0;
            long long cur = 0;
            int i = 0, j = N-1;
            for (; i < N-1 && j > p; i += p, j -= p) {
                cur += s[i] + s[j];
                chmax(tmp, cur);
            }
            chmax(res, tmp);
        }
    }
    cout << res << endl;
}

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

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

AtCoder ABC 128 F - Frog Jump (橙色, 600 点)

問題概要

制約

考えたこと