[AGC065] Shuffle and mod K

[Q] Shuffle and mod K

考察
1. permutationで全パターン試す。最善スコアがどのような出力になるかを観察する

sample K=10

33:3 1 9 8 6
26:2 1 9 8
40:2 1 0 6 5 2
30:0 5 1 0 1 0
30:0 1 0 5 1 0
70:7 6 5 2 1

1. 数がばらけている場合、降順のかたまりが1or2つできてる
2. 同じ値が複数ある場合、降順のかたまりがいくつかできている。

2. 次の3パターンを網羅したら同一結果になった
a. スタート値を適当に決めたら、貪欲的にスコアが最善になる値を選ぶ
b. もし同じ値のAがある場合、最も重複数の多いAをスタート値に選ぶ
c. aで選んだスタート値が最善とは限らない。開始地点を0~N-1までスライドさせる。

実装

int main()
{
  cincout();
  ll N, K;
  cin >> N >> K;
  if (K == 1)
  {
    cout << 0 << endl;
    return 0;
  }

  vector<ll> A(N);
  rep(i, N) cin >> A[i];

  // 1. 重複の多い数をスタート値にする
  map<ll, ll> mp;
  ll target = 0;
  ll max_cnt = 0;
  rep(i, N)
  {
    mp[A[i]]++;
    if (chmax(max_cnt, mp[A[i]]))
    {
      target = A[i];
    }
  }
  vector<ll> B(N);
  B[0] = target;

  // 2. 貪欲的に、スコアが最も大きくなる値を選ぶ
  // これは2パターンで、残存値から最大をとるか、前の値から少し小さい値をとるか。
  multiset<ll> S; // 残存値を管理する
  rep(i, N) S.insert(A[i]);
  S.erase(S.find(target)); // targetは使用済み

  ll ans = 0;
  for (ll i = 1; i < N; ++i)
  {
    // B[i - 1] との差分が大きいものを選ぶ
    ll nx = 0;
    ll best_score = -1;
    auto it = S.lower_bound(B[i - 1]);
    if (it != S.begin()) // 少し小さい値
    {
      --it;
      if (chmax(best_score, K - (B[i - 1] - *it)))
      {
        nx = *it;
      }
    }
    if (chmax(best_score, *S.rbegin() - B[i - 1])) // 最大値
    {
      nx = *S.rbegin();
    }
    B[i] = nx;
    S.erase(S.find(nx));
    ans += best_score;
  }

  // 3. B[0]を固定したが、開始位置と終端との差分がベストとは限らない。
  // 5 10 3 1 9 8 6
  // 32:1 9 8 6 3 が得られるが、
  // 33:3 1 9 8 6 が最善。
  // スライドして改善する可能性がある。

  // 開始位置をN通り試して、ベストスコアを選ぶ
  ll best_ans = ans;
  rep(i, N)
  {
    ll pi = (i - 1 + N) % N;
    ll ni = (i + 1) % N;
    ll dis = B[ni] - B[i];
    if (dis < 0)
      dis += K;
    ans -= dis;

    ll add = B[i] - B[pi];
    if (add < 0)
      add += K;
    ans += add;
    chmax(best_ans, ans);
  }
  cout << best_ans << endl;
}

https://atcoder.jp/contests/agc065/submissions/48626275