yukicoder No.31 - 悪のミックスジュース(writer担当)

Source

ニコニコミュニティ
問題文

問題概要

果物 $1,2,\ldots,N$ の容量 $1$ のジュースの値段は $C_k$ 円です(一部だけ買うことができませんが,一部だけ使うことはできます).
果物 $k$ のジュースの使用容量を $p_k$ としたとき,以下の条件をみたすようにミックスジュースを作りたいです.
$\quad p_1 + p_2 + \cdots + p_N = V$
$\quad p_1 \geq p_2 \geq \cdots \geq p_N > 0$
最小コストを求める問題.

解法

まず,全部のジュースを使わなければならないことから,$V \leq N$ の場合は,全てのジュースを容量 $1$ だけ買えば良い.
($V < N$ の場合は,適当に一部を使えば良い)
その他の場合は,無駄にしても良いことはないので,$p_k$ は整数の場合だけを考えれば良い.
また,全てのジュースを $1$ ずつは買わなくてはいけないことから,全てのジュースを $1$ 買った後の状態を考え,
$\quad p_1 + p_2 + \cdots + p_N = V$
$\quad p_1 \geq p_2 \geq \cdots \geq p_N \geq 0$
の条件で考える.(ジュースを買ったので $V \leftarrow V - N \geq 0$ になっている)
使う容量の差分 $s_k = p_k - p_{k+1}$ に着目する.ただし,便宜上 $p_{N+1}=0$ と思う.
$s_k$ は非負整数で,逆に,$s_k$ が非負整数ならば,条件 $\quad p_1 \geq p_2 \geq \cdots \geq p_N \geq 0$
を満たす.
よって,$s_k$ を変数としてみると,容量 $k$ のジュースが $C_1+C_2+\cdots+C_k$ 円で売っているというふうに見ることができる.
そして,自由に買って容量 $V$ のジュースを作るのに最小の金額を求めれば良い.
そこで,パック $k$ を買うと,容量 $k$ のジュースが $S_k = C_1+C_2+\cdots+C_k$ 円で手に入るとする.
これは,計算時間を無視すれば,典型的なDPで計算可能で,状態としてジュースの量を取り,そのジュースの量を買うのに必要な最小コストを計算すれば良い.
これだと,時間計算量 $O(NV)$ になり間に合わない.
直感的に,最も効率の良い,つまり,単位容量あたりの値段 $S_k/k$ の最も安いパック以外はたくさん買うことはないように思える.
それは実際に正しくて,単位容量あたりの値段が最も安いパックを $m$ とすると,その他のパック $k$ を $m$ 個買うぐらいなら,その分,パック $m$ を $k$ 個買ったほうが得になるので,パック $m$ 以外の購入する数は $m$ 個未満として良い.
その他のパックを買う数は最大で $O(N^2)$ 程度で,その他のパックの容量の合計は $O(N^3)$ 程度.
つまり,動的計画法で求めるのは,$O(N^3)$ 程度の量を買うところまでを求めれば良くて,残りは,貪欲に最も効率の良いパックを買えば良い.
これで時間計算量は $O(N^4)$ になり,十分に間に合う.
しかし,実際には,その他のパックを買う数は最大で $N$ 個であることが示せ,時間計算量 $O(N^3)$ で解くことができる.
これを示すには,以下のように鳩ノ巣原理を利用する.
最も効率の良いパック $m$ 以外に,$m$ 個のパックを買ったとし,それらを $r_1,r_2,\ldots,r_m$ とする.
ここで,$t_k = (r_1+r_2+\cdots+r_k)\ {\rm mod}\ m, \;\; k=0,1,\ldots,m$ という $m+1$ 個の量を考えると,同じ値になるものが存在する.
$t_i = t_j$ とすると,$r_{i+1}+t_{i+2}+\cdots+r_j$ が $m$ の倍数であるので,これらをパック $m$ のジュースで置き換えることで損はしない.
よって,再帰的に,パック $m$ 以外のパックを購入する数は $m$ 未満であることがわかる.
時間計算量は $O(N^3)$.

C++によるスパゲッティなソースコード

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

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

int N, V, C[111];
ll sum[111], dp[11111];

ll solve(void){
  int i, k, opt;

  V = max(0, V-N);
  sum[0] = 0;
  rep(i,N) sum[i+1] = sum[i] + C[i];

  dp[0] = 0;
  REP(i,1,11111) dp[i] = dp[i-1] + sum[1];
  REP(k,2,N+1) REP(i,k,11111) dp[i] = min(dp[i], dp[i-k]+sum[k]);

  opt = 1;
  REP(i,2,N+1){
    if(sum[opt] * i > sum[i] * opt) opt = i;
  }

  k = max(0, (V-11000) / opt);
  return k * sum[opt] + dp[V - k*opt] + sum[N];
}

int main(){
  int i;
  ll res;

  scanf("%d%d",&N,&V);
  rep(i,N) scanf("%d",C+i);

  res = solve();
  printf("%lld\n",res);

  return 0;
}

Current time: 2017年09月22日22時35分14秒
Last modified: 2014年12月05日00時50分39秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン: