[JOI精進録] 難易度7「お菓子の分割」(第9回日本情報オリンピック 本選B)

問題リンク

atcoder.jp

問題概要

mmのお菓子がある。このお菓子をmmずつ2人で分ける。
このお菓子は切る場所によって違うコストがかかる。
このコストの総和の最小値を求めなさい。

解説

AC解法と同じ計算量だがMLEする解法 (12/20点)

人1がmm、人2がmm分先頭から切り分けて配ったとき、コストの最小値
とする。更新はだけを変えて計算済みの場所のコストの最小値とだけを変えて計算済みの場所のコストの最小値の小さい方に今から切る分のコストを足したものとする。
累積minを取ることでで計算できる。
累積minは1次元+0次元、dp配列は2次元である。

AC解法 (20/20点)

dp配列は更新に累積minしか使わないので0次元のみでよい。
ということで計算量は同じで、dp配列を0次元にしたのでメモリの使用量が大幅に減る。

ACコード

このブログ書いてて配列外参照起こしてることに気づきました。以下は修正版のコード、提出結果です。

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

int main(){
  int n, acc1,t; cin >> n;
  vector<int> A(n-1),acc0(n/2+1,numeric_limits<int>::max()); for (int& a:A) cin >> a;
  A.emplace_back(0);
  for (int k(1);k <= n/2;++k) acc0[k] = A[k-1];
  for (int i(1);i <= n/2;++i){
    acc1 = A[i-1];
    for (int k(1);k <= n/2;++k){
      t = min(acc1,acc0[k])+A[i+k-1];
      acc0[k] = min(acc0[k],t),acc1 = min(acc1,t);
    }
  }
  cout << t << endl;
}

提出結果

atcoder.jp