C - Minimization arc099_a

問題

• https://atcoder.jp/contests/abc101/tasks/arc099_a

提出

• https://atcoder.jp/contests/abc101/submissions/3823261

方針

• 1を左右に伸ばしていく

注意ケース

• 全力で左を伸ばしに行くのではなく、1発目で右側にも少し伸ばしておいたほうがいい場合がある

• 左から攻めると3回だけど、右から攻めると2回になる

振り返り

• 証明ができていない
• 左右両方からやってminを取るのは2倍時間がかかっていまう
  • 通ったけれど
• 何度かWAして、テストケースの漏れに気づく。ペナルティのある環境では望ましくない

2020/10/30

• 右に全力で伸ばすと無駄があることがあることに注意すると、無駄になった分（余剰）は左の伸ばしに使ったことにすればいい
• AC https://atcoder.jp/contests/abc101/submissions/17724805

// 何回必要か
ll f(VI A, ll K){
  ll N = A.size();
  ll idx = -1;
  rep(i,N){
    if(A[i]==1){
      idx=i;break;
    }
  }

  // まず右側を埋める
  // 1回の操作でN-1マスを1にすることができる
  ll right_space = N-1-idx;
  ll num = (right_space+K-2)/(K-1); // 操作回数
  ll len = num * (K-1);
  ll surplus = len-right_space; // 余剰

  // 余剰分は左に伸ばしておく
  ll left_space = idx;
  left_space -= surplus;
  if(left_space<=0){
    return num;
  }
  // 左側に伸ばす操作回数
  ll num2 = (left_space+K-2)/(K-1);
  return num+num2;
}

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

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

    VI A(N);
    rep(i, N) cin >> A[i];

    ll a = f(A,K);
    reverse(ALL(A));
    ll b = f(A,K);

    ll ans = min(a,b);
    p(ans);    
    
    return 0;
}