スレ立てるまでもない質問はここで 166匹目 (122ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞

---

11(1): デフォルトの名無しさん [sage] 2024/12/16(月) 15:36:56.21 ID:5AL+G6v+(1) AAS
(重さ,価値)のリストを受け取る関数で以下のようなhaskellコードがあったのですが理解できません
何をやっているんでしょうか

sieve :: [(Int, Int)] -> [(Int, Int)]
sieve lis = map snd . filter (\((w1, v1), (w2, v2)) -> v1 < v2) $ adj
where
slis = sort lis
adj = zip (scanl (\(w, v) (w', v') -> (w', max v v')) (0, 0) slis) slis

例えばテストケースに以下のリストを渡すとadjの内容はコメントしたように(3,3)という存在しないデータが出てきます
一応上のフィルタで消えるのですが、常にこれは成り立つ？
[(1,1),(2,3),(3,2),(4,5)] -- [((0,0),(1,1)),((1,1),(2,3)),((2,3),(3,2)),((3,3),(4,5))]
最終的な結果は
[(1,1),(2,3),(4,5)]

---

18(1): デフォルトの名無しさん [sage] 2024/12/16(月) 23:23:08.71 ID:pEIdxfnL(1) AAS
>>11
重さ(w)があるのに価値(v)がないものを取り除いている
Rustで書くとこんな感じ
軽い順で入力が入ってくる状況で
scanで今まで来た価値(v)の最大値を求めていて
filterでその自分より前の最大値より価値(v)が大きいものだけを取り出している

fn sieve(sorted_input: impl IntoIterator<Item = (u32, u32)>) -> impl Iterator<Item = (u32, u32)> {
sorted_input
.into_iter()
.scan(0, |v_max, (w, v)| {
let pre_v_max = *v_max;
*v_max = v.max(pre_v_max);
Some((w, v, pre_v_max))
})
.filter_map(|(w, v, pre_v_max)| {
(v > pre_v_max)
.then_some((w, v))
})
}

---

上下前次1-新書関写板覧索設栞歴

---

ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

ぬこの手 ぬこTOP 0.558s*