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

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

AtCoder ABC 128 F - Frog Jump (600 点)

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

というタイプの問題。結構重たい。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;
}