保存されている過去のバージョンの一覧

2014年12月05日00時50分39秒
2014年12月05日00時49分17秒

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: 2024年04月23日15時24分20秒
Last modified: 2014年12月05日00時50分39秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン：