2017-03-25

RUPC2017参加記

競技プログラミング参加記

3/22から3/24に立命館大学で行われたRUPC2017に参加した。

立命館大学競技プログラミング合宿2017 : ATND

Day1 : 立命館大学&大阪大学セット

コンテスト前

会場の設営のために10時半くらいにBKCに着いたけど、Twitterではすでに到着している参加者がいてびっくりした。

会場であるBKCで卒業式をしていて、人がとても多かった(怖い)。

あと、自己紹介フェーズがなくなってしまって悲しかった(運営側として申し訳ない気持ちもあります……)。

コンテスト

出題側だったので、コンテスト中はジャッジを眺めながら風船運びをしたり、B問題の解説スライドを作ったりしていた。

コンテストの問題は、B問題とK問題の原案を考えて、B問題の解説をした。

コンテスト後のRCOの宣伝コーナーが面白かった。競プロerに優しい会社。

懇親会

学内のユニオンフードコートというところで立食パーティーをした。

Twitterでよく見るうくさん(@ukuku09)やらてさん(@LatteMalta)、夏の会津合宿でチームを組んだそうめんさん(@somennagasi)たちとお話しした。とても楽しかったです！！！！

懇親会後

大学の宿泊施設に移動して、チェックイン。

これから2泊、8人部屋に1人で泊まります pic.twitter.com/wUgtj0GjqJ
— 素数うさぎりかさん (@wk1080id) 2017年3月22日

私の就寝時間までは時間が結構あったのと、RUPC前の1~2週間くらい前から全然競プロできてなくて鈍ってそうだったので、バチャコンをすることに。

最近競プロやらなすぎてマズいので、AVCやります
このあと23:40-25:00(1h20m)で、CODE FESTIVAL 2016 Final (Parallel)とJAG Contest 2016 Domesticの問題ですhttps://t.co/AO3mC8swc1
— 素数うさぎりかさん (@wk1080id) 2017年3月22日

こんな時間にもかかわらず5人も参加してもらえて嬉しかった。

そのあとはTwitterでタイムラインを監視していた。

@wk1080id 真ん中の床、とても魅力的じゃありませんか？
— ツカサし･×･U@Dの心となずな氏の愛 (@tsukasa_diary) 2017年3月22日

もちろんベッドで寝ました。

Day2 : 会津大学セット

コンテスト前

目覚ましをかける前に寝落ちしてしまって、起きるのがギリギリになって焦った。

湖西線トラップ*1 にかかってしまった人がいて、開催時刻が30分遅くなったので、お菓子を食べてた。おいしい。

コンテスト

.@_ybrliiu さんと@konbu1610 さんとチーム「ykw」で出ます！#RUPC2017
— 素数うさぎりかさん (@wk1080id) 2017年3月23日

私はB問題を担当することになったので、冷雨さん(@_ybrliiu)にA問題を実装してもらっている間に考察していた。参加者を1人決め打ちすると、その人が勝者になる回数と引き分けになる回数はupper_boundやlower_boundを使うとO(logN)で求められるので全体でO(NlogN)になっていけそうとわかる。A問題がバグっている間にコーディングを代わってもらってB問題をAC。

そのあとA問題を見て、場合分けでいけると思ったので、方針を伝えてから、コンブさん(@konbu1610)と一緒にC問題を考える。因数定理をつかって項を一つずつ見つけていけばいいという方針が立って、とりあえず構文解析の実装に移る。構文解析だけでもだいぶバグらせていて辛かった。

ここらで、A問題のバグが取れないので方針を変えて、tをループで回すことにした。冷雨さんが実装してA問題がAC。その後私は構文解析のところを書き終えてから、多項式の割り算を時間をかけながら実装してACした。

この段階で残りがあと1時間半くらいだったので、E問題をコンブさんと考えていた。各辺の労力/長さを計算して、労力/長さが大きい順に木を構成していけばいいんじゃないかと思って、コンブさんに実装してもらっていたけど、嘘解法だとわかって、どうしよう……となったところでコンテスト終了。

A,B,Cの3完でした(BとCの実装をしました)
— 素数うさぎりかさん (@wk1080id) 2017年3月23日

C割り算実装したの無駄だった……
#RUPC2017
— 素数うさぎりかさん (@wk1080id) 2017年3月23日

悲しかったけど、「展開する前のそれぞれの一次式の元の定数項は相異なることが保証される」を理解していなかったのが悪かった。うん。

懇親会

南草津駅前の魚民に行った。RUPCのほぼすべての参加者が2日目の懇親会に来ていた。

@kenkoooo さんと同じ机だったので、RCOの話を聞いていた。あとKaggleの話も面白かったです。

懇親会後

先輩たちが泊まっている部屋に遊びに行った。そして例によって例のごとくコンテスト。

AVCでバチャコンします！
コドフェス2015 あさぷろ Easy+KUPC2015
23:30-25:00https://t.co/Cidx3NTYMI
— 素数うさぎりかさん (@wk1080id) 2017年3月23日

コンテスト後は解法を教えてもらったり、蟻本やTwitterの話をしたりと、だいぶ長い間居座っていた。いろいろな話ができたので嬉しかったけど、寝る時間を削ってしまって申し訳なかったなあと思ってます。

Day3 : 北海道大学セット

コンテスト前

目覚ましをつけるとちゃんと起きられるタイプなので、 7時半くらいには起きた。それから荷物をまとめてチェックアウトして、ゆっくり会場に向かう。

ドリンクがなくなっていて、お菓子も少なかったので、RiPProの先輩たちと学内コンビニに買い出しに行った。

コンテスト

.@s1230151 さんと @chakku_000 さんとチーム「ckr」で出ます！
— 素数うさぎりかさん (@wk1080id) 2017年3月24日

A問題を担当することになったけど、「並び替えて」という言葉を読み飛ばして(誤読して) これ本当にA問題か？と思いながら考えていた。実は前日のバチャコンで文字列から削除する系の問題*2を見ていたために、頭の中で（これもしかしてDPする感じか……？）と思って、B問題を考えていたちゃっくさん(@chakku_000)と代わってもらうことにした。その後、kawabysさん(@s1230151)がA問題、ちゃっくさんがC問題を考えることになって、ちゃっくさんがC問題をAC。

B問題は現在8位のユニットとユニット1の差を見て、いくつ増やせばいいかを求めるのかなと思って実装したら、ユニット1の値を変えると他のユニットの合計得点が変わってしまうと気づいて、誤解法だとわかる。その後私がB問題を考え直している間に、A問題がAC。B問題は、値を変更する数をループで回して、その後に合計得点を計算し、ユニット1が8位以上なら答えとするという方法を思いついたので、それを実装した。

実装したはいいけど、バグが取れなくて、kawabysさんと一緒にデバッグしていた。その間ちゃっくさんはE問題を考察。残り30分くらいでB問題をACした。

そしてEが解けないままコンテストが終わる。

お疲れ様でした。
チームとしては4完、私はB問題に2時間ちかくかけた戦犯です
— 素数うさぎりかさん (@wk1080id) 2017年3月24日

A問題を誤読してB問題をひたすらバグらせる害悪でした。

コンテスト後

解説が(アニメネタとかがあって)とても面白かった。

解説後は立命館の成績返却とガイダンスに行かなければならなかったので、すぐに会場を去った。もう少しお話ししていたかった。

全体を通して

Twitterで見かける人や初めて知った人などたくさんの人と交流できてよかった！

次のオンサイトは会津合宿かな？(オンサイトは楽しいのでHUPCやQUPCやNJPCなどのオンサイトがあればぜひ行きたいです！！)

#RUPC2017 お疲れ様でした！
チームで問題を解くのも楽しかったし、懇親会でたくさんの人とお喋りできたのも楽しかった！！
RCOさんありがとうございました！！#ありがとうRCO
— 素数うさぎりかさん (@wk1080id) 2017年3月24日

RCOさん、ありがとうございました！！！！！！！！！！

余談

Day1のK問題について。

ところでRUPC2017Day1のK問題なのですが、明後日に成績発表を控えた立命勢にとって、単位が取れるかどうかという非常にタイムリーな話題でした。
— 素数うさぎりかさん (@wk1080id) 2017年3月22日

K問題原案ですが、大学の定期考査期間中(1月末)に、テスト勉強したくない気持ちが強くなってきて、来期は期末考査がなくレポートだけで成績が決まる講義をたくさん受けたい！！！！と思っていたら降ってきました。やったね。

なお、原案は

レポートの数
友達の数
AORイカちゃんが自力でレポートを仕上げる最低回数
AORイカちゃんと友達のそれぞれのレポートの点数

が与えられて、合計得点の最大値を求める問題(難易度はBくらい)だったのですが、先輩による改変を経て化けました。びっくりしました。

*1:京都大阪方面から滋賀に向かうJRには琵琶湖線と湖西線があり、南草津に来るには琵琶湖線に乗らないといけないのですが、京都や滋賀に住んでいる人でも間違えることがあります

f:id:wk1080id:20170325010402j:plain

*2:D: ヘイホー君と削除 - CODE FESTIVAL 2015 あさぷろ Easy | AtCoder

2017-03-14

gitあれこれ

競技プログラミング

作問につかった。忘れそうなのでメモ。

githubのレポジトリの「Clone or download」からurlを取得
f:id:wk1080id:20170314123412p:plain

作りたい場所に移動してから「git clone 取得したurl」を入力

$ git clone https://github.com/~

既存の(誰かの)フォルダをコピーして、自分の名前に変える。

フォルダに入って、main.ccを編集して自分の回答にする。

テストしてみる。

$ rime test

OKがでたら良い。

「git add フォルダ名」で自分のフォルダを追加して、「git commit -m "コメント"」でgitにcommitする。

$ git add rika
$ git commit -m "rikaの回答を追加"

終わり。

2017-03-09

ABC 006 C スフィンクスのなぞなぞ

競技プログラミング AtCoder

数式が出てきたのでメモ。

C: スフィンクスのなぞなぞ - AtCoder Beginner Contest 006 | AtCoder

問題概要

大人、老人、赤ちゃんの足の数をそれぞれ2本、3本、4本とする。
街の人数Nと足の数Mが与えられるので大人、老人、赤ちゃんの人数の組み合わせを1つ答えよ。存在しない場合はすべて-1で答えよ。

制約
$1 \le N \le 10^5$
$1 \le M \le 10^5$

部分点あるけどここでは割愛

解法

連立方程式を解くだけ。

大人の人数をa、老人の人数をe、赤ちゃんの人数をbとする。
ただし、人数なのでそれぞれ非負整数である。

このとき、街の人口については

$a + e + b = N$ 　…(1)

足の本数について

$2a + 3e + 4b = M$ 　…(2)

という2つの方程式を立てることができる。

よって連立させて式を変形させることで、変数を1つに減らすことができる*1。

まず(1)式をeについての式に変形する

$e = N - a - b$ 　…(3)

そして(3)式を(2)式に代入して、aについて解く

$2a + 3( N - a - b ) + 4b = M$

$3N - a + b = M$

$a = b + 3N - M$ 　…(4)

また、(4)式を(1)式に代入して、eについて解くと

$( b + 3N - M ) + e + b = N$

$2b + e + 2N - M = 0$

$e = M - 2N - 2b$ 　…(5)

以上のように、(1)(2)の連立方程式から(4)(5)の式が得られた。(4)(5)の2式は人口についてと足の本数についての制約を満たすので、あとは3つの変数a、e、bが非負整数であれば、答えとなる。

変数bが決まればaとeは確定するので、bがとりうる値(0からNまで)をループで回してやれば、全通り試せる。
よって、計算量は $O(N)$ 。

Submission #1152289 - AtCoder Beginner Contest 006 | AtCoder

感想

数学は楽しい(これは真理)。

実は私のソースコードだと $a = e = 0$ の場合も答えとなってしまう(サンプル1だと「 0 3 0 」を出力する)けど、実際問題、街に大人と老人がいなくて赤ちゃんだけ存在するというのはおかしいなあ大丈夫かなあと思いながらsubmitしたらACしてしまったので拍子抜けした。

*1:連立方程式は連立した式の数だけ変数を減らすことができる。変数が3つで式が2つなので、変数は2つ減らせる

2017-03-08

ABC017 C ハイスコア

競技プログラミング AtCoder

自力で満点解法思いついたの嬉しかったのでその記念。

C: ハイスコア - AtCoder Beginner Contest 017 | AtCoder

問題概要

$N$ 個の遺跡があり、遺跡を探索すると宝石と得点が得られる。
$i$ 番目の遺跡を探索したときに、得点 $s_i$ 点を獲得し、 $M$ 種類ある宝石のうち $l_i$ 番目から $r_i$ 番目までの宝石を得られる。
すべての種類の宝石を1つ以上獲得すると魔王が復活してしまうので、魔王が復活しないように遺跡を探索したときの得点の合計の最大値を求める。

制約

$1 \le N \le 10^5$
$1 \le M \le 10^5$
$1 \le l_i \le r_i \le M$
$1 \le s_i \le 5000$

部分点

30点…… $N \le 8$ , $M \le 8$ を満たすテストケース
100点…… $N \le 5000$ , $M \le 5000$ を満たすテストケース
101点……すべてのテストケース

TLE解法

100点解法*1。
魔王が復活しないとき、少なくともどれか1つの宝石は獲得していない。獲得してはいけない宝石を1つ決めると、各遺跡について、その宝石を獲得できるかどうかで、その遺跡で得点を獲得できるかがわかる(最大の得点について考えているので、獲得してはいけない宝石をその遺跡で取ることができないならば、その遺跡を探索して得点を得た方がよい)。
つまり、獲得してはいけない宝石を1つ決めたとき、そのときに取りうる最大の得点は一意に決まる。

獲得してはいけない宝石を順番に試すのに $O(M)$ 。獲得してはいけない宝石を決めた後、各遺跡でその宝石を獲得できるかを調べるのに $O(N)$ かかる。よって、全体の計算量は $O(NM)$ 。

Submission #948966 - AtCoder Beginner Contest 017 | AtCoder

満点解法

(私が解法を考えていたときの脳内をだいぶ忠実に再現してみる)

「すべての宝石を獲得してはいけない」というのが最大の制約なので、獲得してはいけない宝石を一つ定めるという方針はそのままでよさそう。……TLE解法のとおり、獲得してはいけない宝石を決めたときに、その宝石を獲得してしまう遺跡の得点は得られない。……「得られない」ということは、「獲得してはいけない宝石を決めたときに、各遺跡で何点得られないか」というふうに全体からの引き算で考えることができる。もちろん、得られない点数が一番小さくなる宝石を、獲得してはいけない宝石として選べば良い。

試しに、サンプル1を表に書いてみる。

f:id:wk1080id:20170308022800p:plain

はじめに各遺跡について、獲得してはいけない宝石の欄にその遺跡で得られる得点をマイナス表記する。
その後、獲得してはいけない宝石を1つ決めると、その宝石の列さえ見れば最終的な得点が求まることがわかる。
そこまでわかって、いもす法*2を使えばこの表を圧縮して、計算量も落とすことができる！と気付いた。やったね！たえちゃ(ry

いもす法を使うことで、獲得してはいけない宝石を1つ決めると、そのときの最大の得点は $O(1)$ で求まる。
よって計算量は、いもす法の前処理(記録＋シミュレート)に $O(N+M)$ 、各宝石を獲得しない場合について計算するのに $O(M)$ かかるので、全体で $O(max(N,M))$ 。

Submission #1150134 - AtCoder Beginner Contest 017 | AtCoder

ソースコードでは、さっきの表と違い、各遺跡で取ることができない点数を負数ではなく正数で計算している(ので最後に総得点から引き算している)。あと、宝石のindexに注意する。

感想

得点が0点の状態から考えて何点獲得できるか、ではなく、得点がMAXのときから考えて何点獲得できないか、に思考をシフトさせるのが面白かった。
例示は理解の試金石*3だ！！！！と再確認させられた。サンプル試すの大事。

いもすの入力の際に+=じゃなくて=にしていたせいで30分くらい溶かした
— りか (@wk1080id) 2017年3月7日

↑悲しい……

あと、いもす法は好きです(なら間違えるな

*1:30点解法は考えてないので知らない。たぶんすべての遺跡について、探索するかしないかを全探するんじゃないかな。……と思ったけど、制約が8だしnext_permutationを使ってシミュレートするのか。

*2:いもす法知らない人はこちらを参照してください->いもす法 - いもす研 (imos laboratory)

*3:数学ガールの主人公「僕」がよく言う台詞

2017-02-23

ABC054 D Mixing Experiment

競技プログラミング AtCoder

頑張って実装したので記事にするぞ。最近更新頻度高いし競プロ頑張ってる感がある*1。

D: Mixing Experiment - AtCoder Beginner Contest 054 | AtCoder

問題概要

N種類の薬品のうちいくつかの薬品を購入する。薬品iにはタイプAの物質を $a_i$ グラム、タイプBの物質を $b_i$ グラム含んでおり、価格 $c_i$ 円で売られている。
タイプAの物質とタイプBの物質の混合比が $M_a : M_b$ となるのに必要な最小予算を求めよ。

制約

$1 \le N \le 40$
$1 \le a_i, b_i \le 10$
$1 \le c_i \le 100$
$1 \le M_a, M_b \le 10$

DP解法1

求めるものは「物質の重さの比が $M_a : M_b$ となるのに必要な最小予算」なので、購入するそれぞれの物質の重さが最終的にわかればよい。よって、

dp[i][j][k]:=薬品 i まで見たときに、購入するタイプAの物質が合計 j グラム、タイプBの物質が合計 k グラムとなる最小費用

という配列をつくる。
j : k = $M_a : M_b$ となるdp[n][j][k]の最小値が求める最小費用。

計算量は $O(N^3 (max( a_i, b_i ))^2 )$ 。

Submission #1123367 - AtCoder Beginner Contest 054 | AtCoder

DP解法2

さっきのDP解法よりさらに計算量を落とすことができる。

(タイプAの物質の合計の重さ)：(タイプBの物質の合計の重さ)＝ $M_a$ ： $M_b$

となれば良いので、

(タイプAの物質の合計の重さ) * $M_b$ - (タイプBの物質の合計の重さ) * $M_a$ = 0

となる最小費用をもとめればよい。よって、

dp[i][j]:=薬品 i まで見たときに、「購入するタイプAの物質の合計の重さと $M_b$ の積」と「購入するタイプBの物質の合計の重さと $M_a$ の積」の差が j のときの最小費用

という配列を作り、dp[n][0]が答えとなる(ただし、このままだとjは負の値をとることがあるので、jの値はずらす必要がある)。

計算量は $O(N^2 max( a_i , b_i ) max( M_a, M_b ))$ *2。

Submission #1121081 - AtCoder Beginner Contest 054 | AtCoder

DP解法3

もう一つ別の解法があるのを見つけたので紹介だけ(参考サイト：ABC054-D「Mixing Experiment」 | クリエイティヴなヴログ)。
計算量はさっきのDP解法2と変わらないけど、やりかたが違う。

各薬品 i について、

d[i]:= $a_i$ * $M_b$ - $b_i$ * $M_a$

を最初に求めておく。そのあと、

①d[i]=0となる $c_i$ の最小値を求める
②d[i]<0となるものとd[i]>0となるものをいくつか選び、和が0になるものの最小予算を求める(ここでDPを使う)

①と②のうち小さいほうが答えとなる(詳しい解き方はリンク先をみてください)。

半分全列挙

半分全列挙は昔に一度だけやったことがあるけど*3、復習しないので覚えてなかった(ので昔のコードを見ながら思い出しつつやった)。

半分全列挙は、まず半分にわけて、それぞれでありえる組み合わせを全列挙して、うまくmergeして答えを求める方法。名前そのまま。
計算量は、半分にわけて全列挙するところが $O( 2^{ \frac{N}{2}} )$ で、mergeするところが $O( \frac{N}{2})$ なので全体で $O( \frac{N}{2} \times 2^{ \frac{N}{2}})$ *4。

Submission #1128677 - AtCoder Beginner Contest 054 | AtCoder

感想

コンテスト中に通したかった……(そもそも全探でしようとしてたのでダメ)

ひとつの問題でいろいろな解き方ができるのは本当におもしろいし楽しいなあ。

同じ問題をずっと解いてるからsolvedが増えない><
でもいろいろな解法で考察することで実力がつくと信じてる！
— リサさんになりたいbot (@wk1080id) 2017年2月19日

*1:と書き始めた当初は思っていたが、記事が完成するのに1週間近くかかったのでダメ

*2:配列の大きさで考えると $O(N^2 max( a_i , b_i ) ( M_a + M_b ) )$ になる

*3:C: 無駄なものが嫌いな人 - AtCoder Regular Contest 017 | AtCoder

*4:この書き方だと某警察につかまりそう。 $O(N \times 2^{ \frac{N}{2} })$ が正しいのだと思うけど、それでは $N=40$ でうまくいくことがわからないし…。

2017-02-19

ABC054 C One-stroke Path

競技プログラミング AtCoder

頑張って実装したやつは記事にしようという試み。

C: One-stroke Path - AtCoder Beginner Contest 054 | AtCoder

問題概要

自己ループと二重辺を含まないN頂点M辺の重み無し無向グラフが与えられるので、頂点1を始点として、全ての頂点を1度だけ訪れるパスは何通りあるかを求める。

制約

$2 \le N \le 8$
$0 \le M \le \frac{N(N-1)}{2}$

再帰を使った解法

コンテスト中に解いた解法はこれ。とりあえずDFSで探索して、行った頂点を記憶しておく。頂点1からN-1回移動したときにすべての頂点に行っていれば、一つの経路として数える。「DFSで行ったところを記憶する」のがとても面倒だった(引き返すときにマイナスしないといけないので)。

Submission #1105966 - AtCoder Beginner Contest 054 | AtCoder

next_permutationを使った解法

すべての頂点を1回しか通らないなら、1からNまでの数字からなる数列の並ぶ順番と頂点をたどる経路を同一視して考えられるよね。ってとこまでわかったけど、N桁の数列の並び替えとかがわからなかった。
next_permutationという関数があるらしいので(知らなかった)、調べて実装してみた~~(ニコニコ動画とかに実装してみたとかいうジャンルありそう)~~。
next_permutationは、受け取った配列を、辞書順で次の並べ方に並べ替える関数。最初は配列を昇順になるようにしておかないと、うまく全部まわってくれないので注意が必要。次の順列が存在する場合はtrueを返し、存在しない場合はfalseを返す。

配列の要素をi番目にいる頂点とすると、毎回頂点iと頂点i+1の間に辺が張られているかを調べ、辺がすべて張られている並べ方の数を出力する。
N頂点の並べ替えと隣り合う頂点間に辺が張られているかそれぞれ調べるので、計算量は $O(N! \times N)$ 。Nが小さいから間に合う。

Submission #1113580 - AtCoder Beginner Contest 054 | AtCoder

next_permutation関数は辞書順で次の並べ方を表示するので、配列のはじめの要素が1以上のときにnext_permutation関数に配列を渡しても、配列のはじめの要素が0になることはない。よって、配列のはじめの要素が0でなくなったときには今後始点が0になることがないのでdo-while文を抜けても大丈夫。

感想

next_permutaion関数すごすぎる。なにこの便利な関数。
実はコンテスト中は、Cの実装&&バグ取りに50分くらいかけてて(コンテストの前にsetとか使ってたせいで余計なことを考えてた)、next_permutationの解法書くのに10分くらいしかかかってないから、コンテストで使えてたらもっと順位が良かったのになと思った。まあレートには関係ないけど。
りんごさんが解説放送で余裕があればnext_permutationを自作してみてね！と言っていたけど私には無理だった。

2017-02-16

ABC013 C 節制

競技プログラミング AtCoder

先日 AtCoder Virtual Contest でやっていたABCのC埋めに出てきて、コンテスト中には解けなかったのでゆっくり解いていたが、満点解法がわからなかった&&時間がかかったので書く。

C: 節制 - AtCoder Beginner Contest 013 | AtCoder

問題概要

N日間の食事を次の3つから選ぶ。

・普通の食事 ( 出費A円、満腹度 +B )
・質素な食事 ( 出費C円、満腹度 +D )
・食事抜き　 ( 出費なし、満腹度 -E )

最初の満腹度がHで、一度も満腹度が0以下にならないとき、最低何円でN日間乗り切れるか。

制約
$1 \le N \le 5 \times 10^5$
$1 \le H \le 10^9$
$1 \le C < A \le 10^6$
$1 \le D < B \le 10^6$
$1 \le E \le 10^6$

部分点

10点…… $N \le 10$ を満たすテストケース
40点…… $N \le 50, H \le 50, B \le 50, D \le 50$ を満たすテストケース
100点…… $N \le 10^3$ を満たすテストケース
101点…… すべてのテストケース

部分点解法その1

$N \le 50 , H \le 50 , B \le 50 , D \le 50$ の解法。問題を見た時にまずこれが浮かんだ。

日にちと満足度が決まればそのときの最小の食費は一意に定まるので、
dp[i][j]:=i日目に満足度がjであるときにかかる最小の食費
という配列をもつDPで解ける。
満足度の上限はH+NBより
計算量は $O(N(H+NB))$ つまり $O(BN^2)$ 。

部分点解法その2

$N \le 10^3$ の解法。DPが思いついたあと、100点解法では満足度の上限がないため、満足度を使わずに食費が一意に定まるものは他にないかと考えて、「それぞれの食事をした回数が決まれば、満足度も食費も求めることができる！」と気づいた。
普通の食事の日数と質素な食事の日数が決まれば、食事抜きの日は「 n - (普通の食事の日数) - (質素な食事の日数) 」に決まるから、計算量は $O(N^2)$ 。

Submission #1111965 - AtCoder Beginner Contest 013 | AtCoder

普通の食事の日数をi日、質素な食事の日数をj日とすると、食事を抜く日数はn-i-j日である。
このとき、n日目の満足度は「 $H + Bi + Dj - E(n-i-j)$ 」であるから、これが0より大きければ満足度が一度も0以下になることがないような食事の順番が存在する*1。よって、このときの合計の食費「 $Ai+Cj$ 」が今までの暫定の最小の食費よりも小さければ暫定値を更新する。

満点解法

$N \le 5 \times 10^5$ の解法。思いつかなかったので解説を見たら頭が良かった(それはそう)。

制約より、満腹度が大きくなるほど合計の食費も大きくなるので、合計の食費をできるだけ小さくするには満腹度が(一度も0以下にならないという制約を満たしつつ)できるだけ小さくなるようにすればいい。

つまり、普通の食事の日数をi日、質素な食事の日数をj日、食事を抜く日数はn-i-j日としたとき、 $H + Bi + Dj - E(n-i-j) > 0$ を満たすようなiとjのうち、iとjが最小になるものを考える。

2変数であるから、計算しやすいように片方の変数iを固定して考える*2。
iを固定したとき

$H + Bi + Dj - E(n-i-j) > 0$

$H + Bi + (D+E)j - E(n-i) > 0$

$j > \frac{E(n-i)-H-Bi}{D+E}$

となる最小の整数jは $O(1)$ で求まる。
これを $0 \le i \le n$ についてそれぞれ調べるので、全体の計算量は $O(N)$ 。

Submission #1112041 - AtCoder Beginner Contest 013 | AtCoder

普通の食事の日数がi日のとき、質素な食事の日数が0日かそうでないかで場合分けをする*3。
$H + (B+E)i - En > 0$ のときは質素な食事の日数が0日で良いため、合計の食費は $Ai$ となる。
$H + (B+E)i - En \ge 0$ のときは、最小となるjを求めて、 $i+j \le n$ のとき(普通の食事の日数と質素な食事の日数の合計がn日以下のとき)は、合計の食費は $Ai+Cj$ となる。 ~~合計がn日より大きい場合は、なかったことにする。~~