公式解説: https://img.atcoder.jp/abc128/editorial.pdf

問題概要

座標 $ 0, 1, 2, \cdots, N-2, N-1 (3 \leq N \leq 10^5) $ 上を移動する．移動は座標 0 から始めて，$ A (\gt 0) $ だけ正の方向に進むことと，$ B (\gt 0) $ だけ負の方向に進むことを交互に繰り返す． $ N-1 $ にたどり着いた地点で終了する．同じ座標を2度訪れてはいけない．

座標 0 と座標 $ N-1 $ 以外の各座標$ i $は，訪れると点数$ s_i $がもらえる．負の点数もありうる．

$ A $ と $ B $ を適切に定め，もらえる点数の合計を最大化せよ．

解法概要

座標 $ N $ 以降に移動することは考えなくて良いので，$ N-1 $ にたどり着くことができるとしたら正の方向に進んだときだけである．また，$ A \leq B $ であるような場合も考えなくて良い．したがって，座標の遷移は次のような形になるはずである:

$ 0, A, A-B, 2A-B, 2A-2B, \cdots, xA-(x-1)B, xA-xB, (x+1)A-xB=N-1 (2x+1 $回移動するとする) ．

これの奇数 / 偶数番目を抜き出した数列を考えると，隣接する要素の差が$ A-B $ の等差数列となっている:

奇数番目の要素を抜き出した数列: $ 0, A-B, 2A-2B, \cdots, xA-xB $

偶数番目の要素を抜き出した数列$ A, 2A-B, \cdots, xA-(x-1)B, (x+1)A-xB=N-1 (2x+1 $．

ここで，$ A-B=C$ とおくと

奇数番目の要素を抜き出した数列: $ 0, C, 2C, \cdots, xC $

偶数番目の要素を抜き出した数列$ A, A+C, \cdots, A+(x-1)C, A+xC=N-1$．

だいぶスッキリして見える (主観) ．偶数番目の要素について，(0 との差ではなく) N-1 との差に注目して式変形をすると:

奇数番目の要素を抜き出した数列: $ 0, C, 2C, \cdots, xC $

偶数番目の要素を抜き出した数列$ N-1-xC, N-1-(x-1)C, \cdots, N-1-C, N-1$．

したがって，題意の通りに移動したときのスコアは $ C,x $ の関数$ f(C,x) $ として表現することができる．

$ f(C,x) = f(C, x-1) + s_{xC} + s_{N-1-xC} $ と表現できることから，$ x, C $ が決まればスコアは程数時間で求めることができる．

また，$ xC \lt N $ でなければならないことから，全体の時間計算量は $ O(N \log N) $ である．*1

ただし，$ C $ が $ N-1 $ の約数であるような場合のみ注意が必要である．このような場合は，$ xC \leq N-1-xC $ となったとき，同じ座標のスコアを 2 回足してしまうことになる．同じ座標を 2 度訪れてはいけないから，$ C $ が $ N-1 $ の約数である場合には $ xC \leq N-1-xC $ となった地点でループを抜けなければならない．

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

int main() {
    int n;
    cin >> n;
    vector<ll> s(n);
    for(int i=0;i<n;++i){
        cin >> s[i];
    }

    ll score = 0LL;
    for(int c=1;c<n/2;++c) {
        ll tmp_score = 0LL;
        if((n-1) % c) {
            for(int x=0;n-1-c*x>=c;++x) {
                tmp_score += s[c*x] + s[n-1-c*x];
                score = max(score, tmp_score);
            }
        } else {
            for(int x=0;c*x<n-1-c*x;++x) {
                tmp_score += s[c*x] + s[n-1-c*x];
                score = max(score, tmp_score);
            }
        }
        
    }

    cout << score << endl;
}

所感

考察難易度 >> 実装難易度な問題は不得意．

*1:$ \log N = \sum_{i=1}^{\infty} \frac{1}{i} $ より

NoiminのNoise

AtCoder Beginner Contest 128 F - Frog Jump

問題概要

解法概要

ソースコード

所感