tekiheiの日記

競技プログラミングについて書きます

CODE FESTIVAL 2016 qual B Greedy customers(700)

atcoder.jp

問題

要素数 Nの数列 Aに対して、以下の操作を行う。
操作: \max A_{i}以下の正の整数 Pを選び、初めて P以上になるような要素から Pを引く。ただしこの操作によって要素が 0になってはいけない。
この操作を最大で何回行えるか。

制約

1 \le N \le 100000
1 \le A_{i} \le 10^{9}

解法の概要

前から順番に操作を行っていく。それより前の最大値が mxのとき、 A_{i} \gt mx+1ならば (A_{i}-1)/(mx+1)回操作を行う。 A_{i} = mx+1ならば mx を mx+1 に更新する。

考察

1. 前から順番に操作を行っていくとしてよい

連続する2回の操作に注目します。この2回の操作の対象のインデックスをそれぞれ i,jとします。 i \gt jだった場合、操作の順番を入れ替えられることが(図を書くと)分かります。また、この2回の操作による結果は変わりません。よってバブルソートの要領で、操作の対象を広義単調増加にすることができます。したがって前から順番に操作を行う場合だけを考えれば良いです。

2. 後のことを考えるとできるだけ小さくするのが良い

あるところまで操作したときの累積maxが hであった場合と、 h'(h' \lt h)であった場合を考えます。累積maxが hであったときにそれより後ろに対して行う操作は、累積maxが h'であるときにも行うことができます。つまり、累積maxが h'のときの、それより後ろに対して行える操作列の集合は、累積maxが hのときに行える操作列の集合を含んでいます。よって要素を小さくすることで(累積maxが大きくなることはないので)、それより後ろに対する結果が悪くなることはないです。

3. 1,2を踏まえてやってみる

2より a_{1} = 1とするのが良いです。操作回数の上界は a_{i}-1で、達成可能です。次に a_{2}以降を見ていきます。 P \ge2でなければならないことと、 1以上残さないといけないことから、操作回数の上界は (a_{i}-1)/2です。これは 2が出てくるまでは、累積maxを変えずに達成することができます(1回以上操作できる場合は、 2を (a_{i}-1)/2-1回引いてから、 (a_{i}-1)/2+(a_{i}-1)\%2を引くことで1にできます)。 2が出てきた場合は、累積maxが 2に変わります。それ以降は 3が出てくるまで、同様にして累積maxを変えずに上界を達成することができます。これを繰り返すことで、各場所で上界を達成しているので、最適解を得ることができます。

実装

ACコード

#include<bits/stdc++.h>
using namespace std;

using Lint=long long;

int main()
{
   int N; cin>>N;
   vector<int> a(N);
   for(int i=0;i<N;i++) cin>>a[i];

   Lint ans=a[0]-1;
   int mx=1;
   for(int i=1;i<N;i++){
      if(a[i]==mx+1){
         mx++;
      }else{
         ans+=(a[i]-1)/(mx+1);
      }
   }
   cout<<ans<<endl;
   return 0;
}

まとめ

  • 操作の順番を入れ替えてみる
  • 現在最適な選択をとりつつ、あとの選択肢が減らないように(?)できるならば貪欲にする
  • 最大値を求める問題で、上界を達成できるか考える

感想

慣れていないので記事を書くのが大変でした(おかしなところがありそう(あります))。証明が書けません。