ARC128 F問題：Frog Jump

問題. Frog Jump

個の蓮が一列に浮かんでいる． 番目の蓮の座標は でスコアを とする．正の整数 を決めて次のゲームを 0 番目の蓮から行う．現在の座標を として， の蓮に移動する．このとき現在のスコアに 加算され， にある蓮は消滅する．次に， から に移動して現在のスコアに が加算され， にある蓮が消滅する．このことを繰返し行いゴールである 番目の蓮を目指す．途中で蓮の無い場所に移動したらゲームは終了でスコアが が減少される．スコアが最大となる を求めて，そのときのスコアの答えよ．

制約： ，　,　

解法

snukeさんの 解説 を参考にした．

を に設定することによってスコア 0 でゲームを終了することができるので，スコアを最大とするような移動方法では蓮の無い場所には移動しないことが分かる．
を固定したときの移動する蓮の座標の列は，
　
となる．偶数番目から奇数番目への座標は右に 移動して，奇数番目から偶数番目への座標は左に 移動しているので，最後のゴールに移動するときは右に 移動する必要があるので， は奇数番目になる．ここで， と置き上の列を整理すると，
　
となる． は適当な非負整数とする．列の偶数番目を取り出すと左から となり，奇数番目を取り出すと右から となるので， と に対して全探索を行う． が1増えるごとに訪れる蓮の数が 2 増えるので高々 しかならない（← 大嘘）． なので， なので 時間である．

計算時間：

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    // cout << setprecision(8) << setiosflags(ios::fixed);

    int n;
    cin >> n;

    vector<ll> s(n);
    for (auto &s_i : s) cin >> s_i;

    ll max_score = 0;
    vector<int> visited(n);
    for (int c = 1; c <= n - 1; ++c) {
        ll sum = 0;

        for (int k = 0; (k + 1) * c < n - 1; ++k) {
            if (k * c == n - 1 - k * c) break;
            if (visited[k * c] == c or visited[n - 1 - k * c] == c)
                break;
            visited[k * c] = visited[n - 1 - k * c] = c;

            sum += (s[k * c] + s[n - 1 - k * c]);
            max_score = max(max_score, sum);
        }
    }

    cout << max_score << endl;

    return 0;
}

最後の解析で大嘘を言ってしまった．戒めのために残す．
最後らへん適当になってしまった．左と右から伸ばすときに重複した場所を訪れてないかの判定で std::set を使うと 時間となる．直接アドレス法で実装すると初期化が必要となり一見 時間必要かと思うけど，訪れたか訪れていないかを の値で管理すると初期化が必要なくなり 時間となる． の値が long long に収まらない場合（ほとんど無いけど・・・）は，ここを参照 すると定数時間で初期化できる．