裏紙

ほぼ競プロ、たまに日記

CF 624 D - Array GCD

問題

Problem - D - Codeforces

問題概要

長さnの数列aを考える。この数列に対して2つの操作を行うことを考える:

  • 連続している部分の除去( a_i, ..., a_jの区間の値を取り除く)、これを区間の長さがm(\lt n)の時にm*aのコストで行う
  • 1つの要素の値を1だけ増加または減少させる、これをbのコストで行う

これらの操作は回数に限りがある。部分の除去は1回しか行うことが出来ないし、コストbの操作は各要素に対しては1回までしか出来ない、つまり増減は1までしか許されていない。

このような状況において、数列全体の最大公約数が1より大きくなるようにするために必要なコストの最小値を求めよ。

イデア

まず、問題を誤読していた。コストbの操作が数列1つの要素に対して1回しか出来ないというものだと解釈してしまっていたが、どうやら各要素に対して1回までらしい。サンプルに複数要素を変更したものが最小になる例がないのはちょっとセコい...というのはおいといて。普通に通している人もいるのだから...

まず、数列の値は全て2以上なので、n-1個の値を除去すればかならずGCDを1より大きい値にすることは可能なので、そのような方法が無いという状況はありえない。そして、どのような状況になっても数列の先頭a_1または数列の末尾a_nは残ることになる。これらに対して変更が加えられる可能性も考慮すると、想定されるGCDの値はa_1 -1, a_1, a_1 +1, a_n -1, a_n, a_n +1のうちの素因数であることが分かる。そのような値について調べていく。

いま、素数pを固定すると、数列のそれぞれの値はpで割り切れるか、またはコストbを払って直すべきか、またはコストaを払って除去範囲に入れるべきかを以下のDPにより計算できる;

dp[今注目している要素のインデックス][除去区間が まだ始まっていない/始まっている/もう終わった]=最小値

実装(C++)

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

typedef long long ll;
#define rep(i,n) for(i=0;i<n;++i)
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); itr++)
#define mp make_pair
#define pb push_back
#define fi first
#define sc second

const ll INF = 3000000000000000000LL;

//dp[今注目している要素][除去区間が 0:まだ始まっていない/1:始まっている/2:もう終わった]
ll dp[1000001][3];

//素因数を返す
void pf(long a, set<long> &s){
  long i;

  for(i=2; i*i<=a; ++i){
    if(a%i==0){
      s.insert(i);
      while(a%i==0) a/=i;
    }
  }

  if(a>1) s.insert(a);
}


int main(int argc, char const *argv[]) {
  long i,j;

  long n;
  ll A,B;
  cin >>n >>A >>B;
  std::vector<long> a(n);
  rep(i,n) scanf(" %ld",&a[i]);

  set<long> p;
  //まずGCDの候補になる値を列挙しておく
  pf(a[0]-1,p);
  pf(a[0]  ,p);
  pf(a[0]+1,p);
  pf(a[n-1]-1,p);
  pf(a[n-1]  ,p);
  pf(a[n-1]+1,p);

  ll ans=INF;
  each(it,p){//各要素に対して
    //cout << *it << endl;
    int d = *it;

    //初期化
    rep(i,3) dp[0][i]=0;

    //dpを更新していく
    rep(i,n){
      //このxの値によって場合分け
      long x=a[i]%d;
      if(x==0){
        //そのまま
        dp[i+1][0]=dp[i][0];
        //次から開く、もしくは開いている区間の継続
        dp[i+1][1]=min(dp[i][0],dp[i][1]+A);
        //次で閉じる、または既に閉じている
        dp[i+1][2]=min(dp[i][1],dp[i][2]);
      }
      else if(x==1 || x==d-1){
        //区間を開かないなら値を変更するしか無い
        dp[i+1][0]=dp[i][0]+B;
        //今注目している値を変更して次から開く、もしくは開いている区間の継続
        dp[i+1][1]=min(dp[i][0]+B,dp[i][1]+A);
        //ここで閉じて値を変更する、もしくは既に閉じているので値を変更する
        dp[i+1][2]=min(dp[i][1]+B,dp[i][2]+B);
      }
      else{
        //絶対に区間をひらかないといけない
        dp[i+1][0]=INF;
        //区間を開いておく
        dp[i+1][1]=min(dp[i][0],dp[i][1])+A;
        //列の末尾で閉じる
        dp[i+1][2]=dp[i+1][1];
      }
    }

    ll tmp=INF;
    rep(i,3) tmp=min(tmp,dp[n][i]);
    ans=min(ans,tmp);
  }

  std::cout << ans << std::endl;
  return 0;
}