abc268_c

問題:

atcoder.jp

解答:

#include <bits/stdc++.h>

#define rep(i, n) for(int i=0; i<(n); ++i)

using namespace std;

int main(){

    int n;

    cin >> n;

    vector<int> p(n);

    rep(i,n) cin >> p[i];

    vector<int> cnt(n);

    cnt[0] = 0;

    rep(i,n){

        cnt[((p[i]+n)-i)%n]++;

        cnt[((p[i]+n+1)-i)%n]++;

        cnt[((p[i]+n-1)-i)%n]++;

    }

   

    int ans = 0;

    rep(i,n) ans = max(ans, cnt[i]);

   

    cout << ans << endl;

    return 0;

}

Submission #34991662 - UNIQUE VISION Programming Contest 2022 Summer (AtCoder Beginner Contest 268)

方針:

テーブル回しながら、各人が喜んでるか見てくとTLEになる。

nの最大値が10^5なのでO(N^2)が間に合わないため。

目の前か左右1つずらした場所に料理があると喜ぶので、各料理3回かつ連続した場所で喜ばれることが分かる。

回す回数のリストを作り、各料理何回回すと目の前に行くかを求め、そことその前後をカウントアップ。回転数ごとに何人喜んでいるかのリストが出来る。それの最大値。