abc334 C - Socks 2 累積和を使わない解法

  • 問題 https://atcoder.jp/contests/abc334/tasks/abc334_c
  • C問題にしては難しい！
  • Kが偶数の時は自明なので省略します
  • Kが奇数の時、i=0, 2, 4, 6, ... を除外した時の奇妙さをそれぞれ求めてminを取りたい。そのまま実装するとO(N2)
  • まず、i=0を除外した時の解をO(N)かけて求めます
  • 次に、i=2を除外した時の解を、上の解を利用してO(1)で求めます。変化する箇所がi=0,1,2しかないので、差分を見ればいいです
    • i=1,2のペアを解除して、i=0,1をペアにする

code

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N,K;
    cin>>N>>K;

    VI A(K);
    rep(i, K){
      cin >> A[i];
    }

    ll ans;
    if(K%2==0){
      ll sum=0;
      rep(i,K/2){
        ll a = A[2*i];
        ll b = A[2*i+1];
        sum += b-a;
      }
      ans=sum;
    }
    else{
      // どれを除去する？
      ll sum=0;
      rep(i,K/2){
        ll a = A[2*i+1];
        ll b = A[2*i+2];
        sum += b-a;
      }
      ans=sum;

      // iを除去した場合
      for(int i=2; i<K; i+=2){
        ll kesu = A[i]-A[i-1];
        ll tasu = A[i-1]-A[i-2];
        sum -= kesu;
        sum += tasu;
        chmin(ans,sum);
      }
    }
    p(ans);   
    
    return 0;
}