2023-06-18
やること宣言
gaaamii.icon
勉強中メモ
gaaamii.icon
2023/6/17 21:00〜のABC306に参加した
ABCはできたけどDがわからずだった
D問題
どのレベルでわからなかったというと、文意はわかったけど解法が全く出てこなかった。
美味しいものをなるべくたくさん食べたときの美味しさの総和を求める
毒入り（健康なときに食べると腹痛になる、腹痛のとき食べると死ぬ）と解毒剤入（腹痛のとき食べると回復する）の2種類で
美味しさは-200だったり0だったり100だったり。まずいものがあるので負の数もあり得るという感じ。
つまりまずいもの、毒入りは食べたくないけど、まずくても解毒剤はほしい、あるいは毒入りでも美味しいから食べたい、というケースがある。
なので、総和が大きくなるようにアルゴリズムを考えられたら正解が出せるぽい。けどわからなかった
解説を見てみる
https://www.youtube.com/watch?v=Xk2ypalibo8&list=PLLeJZg4opYKbBSz6tR14WsrD-RiRlJlwB
単純に考えると全探索だが、その場合2のN乗の計算量になる（Nは3*10の5乗）
今回の場合、毒状態かどうかがわかれば、残りをどう食べるべきかがわかる
iをindex、pを毒状態かどうか(0か1)としたとき、２つの方法がある
f(i,p)というメモ化再帰関数
dp[i][p]のDPテーブルをつくる
解説動画わかりやすく説明してもらってるけどC++だからすこし理解がしにくい
vectorってどういうデータだ
配列か。vector(N, 初期値)みたいに書けるっぽい
解説動画だと-INFで初期化している
Rubyで書いている方もいたのでこちらの方が読みやすい
DPがいまいち理解できない
この問題が例にあげられている
こっちのほうは一次元の配列なので理解しやすい
文章読んで理解できた気がするけど、念のため自分でもRubyで書いてみる
書いてみた
code:ruby
n = gets.chomp.to_i
$heights = gets.chomp.split(" ").map(&:to_i)
def get_cost(i, j)
($heightsi - $heightsj).abs end
$heights.each_with_index do |h, i|
next if i.zero?
if i == 1
next
end
no_skip_cost = dpi - 1 + get_cost(i, i - 1) with_skip_cost = dpi - 2 + get_cost(i, i - 2) end
こういう構造（この例だと、Nまでの最短経路を達成するには、その途中でも最短経路を通ってきている必要がある）を部分構造最適性っていうのか やったこと
gaaamii.icon