結果

問題 No.409 ダイエット
ユーザー keikei
提出日時 2018-02-04 12:25:22
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,774 bytes
コンパイル時間 1,692 ms
コンパイル使用メモリ 175,100 KB
実行使用メモリ 12,380 KB
最終ジャッジ日時 2024-06-30 03:55:26
合計ジャッジ時間 5,629 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 1 ms
6,944 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 2 ms
6,944 KB
testcase_14 AC 2 ms
6,944 KB
testcase_15 AC 2 ms
6,940 KB
testcase_16 AC 2 ms
6,940 KB
testcase_17 AC 2 ms
6,944 KB
testcase_18 AC 2 ms
6,944 KB
testcase_19 AC 2 ms
6,944 KB
testcase_20 AC 2 ms
6,944 KB
testcase_21 AC 2 ms
6,944 KB
testcase_22 AC 2 ms
6,940 KB
testcase_23 AC 2 ms
6,944 KB
testcase_24 AC 2 ms
6,940 KB
testcase_25 AC 2 ms
6,940 KB
testcase_26 AC 2 ms
6,944 KB
testcase_27 AC 2 ms
6,940 KB
testcase_28 AC 2 ms
6,940 KB
testcase_29 AC 2 ms
6,940 KB
testcase_30 AC 1 ms
6,940 KB
testcase_31 AC 2 ms
6,944 KB
testcase_32 AC 2 ms
6,944 KB
testcase_33 AC 2 ms
6,944 KB
testcase_34 AC 1 ms
6,944 KB
testcase_35 AC 2 ms
6,940 KB
testcase_36 AC 2 ms
6,940 KB
testcase_37 AC 2 ms
6,944 KB
testcase_38 AC 2 ms
6,940 KB
testcase_39 AC 2 ms
6,944 KB
testcase_40 AC 3 ms
6,944 KB
testcase_41 AC 2 ms
6,944 KB
testcase_42 AC 3 ms
6,940 KB
testcase_43 AC 3 ms
6,940 KB
testcase_44 AC 2 ms
6,940 KB
testcase_45 AC 2 ms
6,940 KB
testcase_46 AC 2 ms
6,944 KB
testcase_47 AC 3 ms
6,944 KB
testcase_48 AC 3 ms
6,944 KB
testcase_49 AC 3 ms
6,940 KB
testcase_50 AC 2 ms
6,944 KB
testcase_51 AC 2 ms
6,944 KB
testcase_52 AC 3 ms
6,944 KB
testcase_53 AC 2 ms
6,944 KB
testcase_54 AC 2 ms
6,944 KB
testcase_55 WA -
testcase_56 AC 25 ms
11,968 KB
testcase_57 WA -
testcase_58 WA -
testcase_59 WA -
testcase_60 WA -
testcase_61 WA -
testcase_62 WA -
testcase_63 WA -
testcase_64 WA -
testcase_65 WA -
testcase_66 WA -
testcase_67 WA -
testcase_68 WA -
testcase_69 WA -
testcase_70 WA -
testcase_71 WA -
testcase_72 WA -
testcase_73 WA -
testcase_74 WA -
testcase_75 WA -
testcase_76 WA -
testcase_77 WA -
testcase_78 WA -
testcase_79 WA -
testcase_80 WA -
testcase_81 WA -
testcase_82 WA -
testcase_83 WA -
testcase_84 WA -
testcase_85 AC 6 ms
6,940 KB
testcase_86 WA -
testcase_87 WA -
testcase_88 WA -
testcase_89 WA -
testcase_90 WA -
testcase_91 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e16;

/*
 <url:https://yukicoder.me/problems/no/409>
 問題文============================================================
 btkさんは毎日ドーナツを食べています．
 ある日，btkさんは N 日間ダイエットをすることを決意しました．
 btkさんは毎日違うお店でドーナツを買っていて，
 ダイエット開始から i 日目に訪れるお店でドーナツを食べるとDikg体重が増えることが分かっています．
 また，1 日ドーナツを食べるのをやめると，Akg痩せることができます.
 
 しかし，ドーナツを食べない日が続くとストレスが溜まります．
 ここで，ストレス値というパラメータを定義します． ダイエット開始時点でのストレス値は0です．
 1 日ドーナツを食べないとストレス値が 1 溜まり，
 1日の終了時にbtkさんの体重はB∗(ストレス値)B∗(ストレス値)kg増加します．
 ドーナツを食べるとストレス値は 0 に戻ります．
 
 各日において，ストレス値の変化後に体重が変化することに注意してください．
 
 ダイエット開始前のbtkさんの体重を W kgとしたとき，N 日間で何kgに痩せることができるでしょうか．

 =================================================================
 
 解説=============================================================
 
 Convex hull trick
 
 ストレスがj-1溜まっている時 : -A + B * j kg増える
 i日目にドーナツを食べた時 : Di kg増える
 
 考察1 **********************************************
 
 dp[i][j] := i日目でストレスがj溜まっている時の体重の最小
 
 初期条件 dp[0][0] = W, dp[0][1...N] = INF
 
 漸化式
 dp[i][0] = min(dp[i-1][j] + Di)   0 <= j <= N
 dp[i][j] = dp[i-1][j-1] - A + B*j
 
 => ans := min(dp[N][j])  0 <= j <= N
 
 O(N^2)
 
 ***************************************************
 
 考察2 **********************************************
 
 別の考え方　＝＞　最後にドーナツを食べた日のみに注目　（その間の増分は t日間食べていなければ -t*A + t*(t+1)/2 * B とO(1)で計算できる)
 
 dp[i] := i日目にドーナツを食べた時の最小値
 
 初期条件 dp[0] = W
 
 漸化式
 dp[i] = min(Di + dp[j] - (i - j - 1)*A + (i - j - 1)(i - j)/2 * B)   0 <= j <= i-1
 
 iに着目した時（iを定数とみなせれる時)
 
 dp[i] = Di -(i - 1)*A + (i^2 - i)/2*B + min(-jB*i + dp[j] + j*A + (j^2 + j)/2 * B)  0 <= j <= i-1
 
 min内部に関して
 aj = jB
 bj = dp[j] + j*A + (j^2 + j)/2 * B
 Ci := Di - (i-1)*A + (i^2 - i)/2*B
 とすると
 dp[i] = Ci + min(-aj * i + bj)  0 >= j <= i - 1
 
 
 y=−ax+b の形をした k−1 本の直線のうち
 x=k の時 y が最小となるものを選べばよいことになり
 Convex hull trick でもとまる
 
 ================================================================
 */

struct CHT{
    typedef pair<ll,ll> PT;
    typedef ll RT;
    vector<PT> deq; // first * x + second
    int s,t;
    CHT(int n):s(0),t(0){ deq.resize(n); }
    void add(RT a,RT b){  // a: 単調減少
        const PT p(a,b);
        while(s+1 < t && check(deq[t-2],deq[t-1],p)) t--;
        deq[t++] = p;
    }
    RT incl_query(RT x){  // x: 単調増加
        while(s+1 < t && f(deq[s],x) >= f(deq[s+1],x)) s++;
        return f(deq[s],x);
    }
    RT query(RT x){   // 条件なし
        RT low = s-1, high = t-1;
        while(low+1<high) {
            RT mid = (low+high)>>1;
            if (isright(deq[mid], deq[mid+1], x)) low = mid;
            else high = mid;
        }
        return f(deq[high], x);
    }
    
private:
    bool isright(const PT &p1,const PT &p2,RT x){
        return (p1.second-p2.second) >= x * (p2.first-p1.first);
    }
    bool check(const PT &p1,const PT &p2,const PT &p3){
        return (p2.first-p1.first)*(p3.second-p2.second) >= (p2.second-p1.second)*(p3.first-p2.first);
    }
    RT f(const PT &p,RT x){
        return p.first*x + p.second;
    }
};

ll N,A,B,W;
vector<ll> D;
vector<ll> dp;

int main(void) {
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> N >> A >> B >> W;
    D.resize(N);
    for(auto &in:D) cin >> in;

    dp.resize(N+1,0);
    dp[0] = W;
    CHT cht((int)N);
    
    for(int i = 0; i< N;i++){
        cht.add(-B*i,dp[i] + B*(i*i-i)/2 + A*i);
        dp[i+1] = B*(i*i + i)/2 + D[i] - A*i + cht.query(i);
    }
    ll ans = LINF;
    for(int i = 0; i <= N;i++){
        ans = min(ans , dp[i] - A*(N-i)+ B*(N-i)*(N-i+1)/2);
    }
    cout << ans << endl;
    return 0;
}
0