ARC077E guruguru(700) - tekiheiの日記

考察

まずは愚直解を考えます。 $x$ を全探索してみます。明るさを $a_i$ から $a_{i+1}$ に変更するときの操作回数は、 $f(s,t)$ を明るさを $s$ から $t$ に変更するときの操作回数の最小値として、 $\min(f(a_{i},a_{i+1}),1+f(x,a_{i+1}))$ です。 $f(s,t)$ は $O(1)$ で計算できるので、全体の計算量は $O(NM)$ です。

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

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

   auto f=[&](int s,int t){ return (t-s+M)%M; };
   lint ans=N*M;
   for(int x=0;x<M;x++){
      lint sum=0;
      for(int i=0;i<N-1;i++){ sum+=min(f(a[i],a[i+1]),1+f(x,a[i+1])); }
      ans=min(ans,sum);
   }
   cout<<ans<<endl;
   return 0;
}

次に高速化を考えます。 $sum_x$ を、お気に入りの明るさを $x$ にしたときの操作回数の合計とします。明るさを $a_{i}$ から $a_{i+1}$ に変更するとき、各 $x$ に対して $sum_x$ にいくら足すかを考えます。

[1] $a_{i} \lt a_{i+1}$ のとき
明るさを $x$ に変更するほうが良いのは $a_{i} \lt x \le a_{i+1}$ の場合だけです。よって $sum_{x}$ には \begin{array}{ll} a_{i} \lt x \le a_{i+1}のとき \quad & 1+(a_{i+1}-x) \\ それ以外のとき & a_{i+1}-a_{i} \\ \end{array} を足せばよいです。
f:id:tekihei:20200212165017j:plain

これらは $x$ の一次関数になっているので、いもす法でできます。どのようにするかというと、例えばインデックスが $x$ のところに $a_{1}x+b_1$ と $a_{2}x+b_{2}$ を足すとすると、これらの合計は $(a_1+a_2)x+(b_1+b_2)$ です。よって、単に1次の係数の和と0次の係数の和を計算しておけば、合計でいくら足したかを求めることができます。

[2] $a_{i} \gt a_{i+1}$ のとき
場合分けが少し厄介ですが、頑張るとできます。もっと楽な方法があるので、説明は省略します。

#include<bits/stdc++.h>
using namespace std;
 
using lint=long long;
 
int main()
{
   int N,M; cin>>N>>M;
   vector<int> a(N);
   for(int i=0;i<N;i++) cin>>a[i],a[i]--;
 
   vector<lint> imos0(M+1);
   vector<lint> imos1(M+1);
   auto add=[&](int l,int r,int a,int b)
   {
      // for x in [l,r] add ax+b
      if(l>r) return;
      imos1[l]+=a; imos1[r+1]-=a;
      imos0[l]+=b; imos0[r+1]-=b;
   };
   for(int i=0;i<N-1;i++){
      int s=a[i],t=a[i+1];
      if(s<t){
         add(0,s,0,t-s);
         add(s+1,t,-1,t+1);
         add(t+1,M-1,0,t-s);
      }else{
         add(0,t,-1,t+1);
         add(t+1,s,0,M+t-s);
         add(s+1,M-1,-1,M+t+1);
      }
   }
   for(int i=1;i<M;i++){
      imos0[i]+=imos0[i-1];
      imos1[i]+=imos1[i-1];
   }
   lint ans=(lint)N*M;
   for(int i=0;i<M;i++){ ans=min(ans,imos1[i]*i+imos0[i]); }
   cout<<ans<<endl;
   return 0;
}

楽な実装方法(円環は2周持つ)

添字が循環する場合は2周持っておくと実装が楽になることがあります。今回の場合は、 $sum_{x}$ と $sum_{x+M}$ の和がお気に入りを $x$ にしたときの操作回数の合計だと思うことにします。そうすると、0をまたいでいたせいで厄介になっていた場合分けがなくなって楽になります。
f:id:tekihei:20200212165601j:plain

#include<bits/stdc++.h>
using namespace std;
 
using lint=long long;
 
int main()
{
   int N,M; cin>>N>>M;
   vector<int> a(N);
   for(int i=0;i<N;i++) cin>>a[i],a[i]--;
 
   vector<lint> imos0(2*M+1),imos1(2*M+1);
   auto add=[&](int l,int r,int a,int b)
   {
      imos1[l]+=a; imos1[r+1]-=a;
      imos0[l]+=b; imos0[r+1]-=b;
   };
 
   for(int i=0;i<N-1;i++){
      int s=a[i],t=a[i+1];
      if(t<s) t+=M;
      add(s+1,t,-1,t+1);
      add(t+1,s+M,0,t-s);
   }
   for(int i=1;i<2*M;i++) imos0[i]+=imos0[i-1],imos1[i]+=imos1[i-1];
 
   lint ans=(lint)N*M;
   for(int i=0;i<M;i++){
      lint sum=(imos1[i]*i+imos0[i])+(imos1[i+M]*(i+M)+imos0[i+M]);
      ans=min(ans,sum);
   }
   cout<<ans<<endl;
   return 0;
}