問題概要

2×nの大きさの配列aが与えられる．0-indexedでi番目にa[y][x]を訪れるとa[y][x]×i点を得る．y=0,x=0からスタートし，配列中のすべての要素をちょうど1回ずつ訪れるときに得られる得点を最大化せよ．

解法概要

わりかし面倒．

y=0,x=0からスタートし，配列中のすべての要素をちょうど1回ずつ訪れる経路はn通りしかない．しかも，そのn通りの経路はすべて「ジグザグ進行 (図中の///, 赤) 」と「行けるところまで行って，端まできたらUターン(図中の\\\，青) 」の2つの進み方を組み合わせてできる．それぞれの進み方における途中の点数を配列b, cに保存しておく O(n) の前処理をしておけば，最大の点数は O(n) で求められる．

ただし，cについては以下の2点に気づかなければならない．

y=0,x=0からスタートする場合とy=1,x=0からスタートする場合の両方を前処理で用意しておく必要がある．
途中の点数だけではなく，「そこまでに通ったa[y][x]の累積和」も保存しておく必要がある (ソースコードではc_total)．

f:id:noimin:20180809163904j:plain

前処理が終わったら，bとcを頑張って組み合わせて，n通りの経路での点数をそれぞれ求める．cの進行方向においてi番目に通った要素も，組み合わせた後の経路でもi番目に通るとは限らないことに注意．この点はcの値を元に (c_totalを使って求まる累積和)×(通る順序のズレ) で調節すると良い．

ソースコード

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

int main(){
    int n;
    cin >> n;
    ll a[2][n];
    for(int i=0;i<2;i++) for(int j=0;j<n;j++) cin >> a[i][j];

    /* bを構成する */
    int y = 0, x = 0;
    int dyx[4][2] = {
        {1, 0}, {0, 1}, {-1, 0}, {0, -1}
    };
    ll b[2*n];
    b[0] = 0LL;
    for(int i=0;i<2*n-1;i++){
        int i4 = i % 4;
        if(i4 == 3) i4 = 1;
        y += dyx[i4][0];
        x += dyx[i4][1];
        b[i+1] = b[i] + a[y][x]*(i+1);
    }

    /* cを構成する ついでにa[y][x]の値の累積和c_totalも*/
    ll c[2][2*n], c_total[2][2*n];
    for(int k=0;k<2;k++){
        c[k][0] = 0LL;
        c_total[k][0] = 0LL;
        for(int i=0;i<n-1;i++){
            c[k][i+1] = c[k][i] + a[k][i+1]*(i+1);
            c_total[k][i+1] = c_total[k][i] + a[k][i+1];
        }
        c[k][n] = c[k][n-1] + a[1-k][n-1]*n;
        c_total[k][n] = c_total[k][n-1] + a[1-k][n-1];
        for(int i=0;i<n-1;i++){
            c[k][n+i+1] = c[k][n+i] + a[1-k][n-2-i]*(n+1+i);
            c_total[k][n+i+1] = c_total[k][n+i] + a[1-k][n-2-i];
        }
    }

    /* 最大を求める */
    ll ans = c[0][2*n-1];
    for(int i=1;i<n;i++){
        ll point = b[2*i-1];
        int s = i-1, t = 2*n-1-i;
        point += (c[i%2][t] - c[i%2][s]) + (c_total[i%2][t] - c_total[i%2][s]) * i;
        ans = max(ans, point);
    }
    cout << ans << endl;
}

所感

これ苦手……．本番は解けなくて先にDを解いたところそこそこ良い順位が取れた．

NoiminのNoise

Educational Codeforces Round 48 C. Vasya And The Mushrooms

問題概要

解法概要

ソースコード

所感