こんにちは、ぱるまです。 最近 AtCoder で出た期待値DP/確率DPの問題を整理してみました。具体的には以下の3問を整理してみました。 ABC326 E - Revenge of "The Salary of AtCoder Inc." ABC333 F - Bomb Game 2 ARC174 C - Catastrophic Roulette 共通の…

ARC174 A - A Multiply で最大区間和を求める問題が出てきました。 コンテスト後、最大区間和を求める方法がいくつかあるのを知りました。 この記事では最大区間和を求める方法を4つ紹介します。 以下、長さ n の整数配列 xs の最大区間和を求める問題を考え…

MathJax = { tex: { inlineMath: [['$', '$'], ['\\(', '\\)']] } }; はじめに こんにちは、ぱるまです。ABC334 B がなかなか難しかったのですが、いろいろ学びが得られたので、備忘録として記事を書きます。 この記事では、競プロでよく現れそうないくつか…

タイトルの通りです。 A 問題 各皿にトーストを2枚以下乗せて、各皿にのっているトーストの美味しさの総和の二乗を各皿ごとに計算してその総和を最小化する問題です。（ARC167 A の問題文へのリンク） キーワード: 貪欲法 / 並べ替え不等式 / 0埋め 並べ替え…

最近RustでAtCoderを始めました。始めるにあたってVSCodeでのRustの開発環境の構築をしたので、そのメモを書いていきます。 注意: この記事は2021年9月に書かれたもので、とても古いです！ （AtCoder での Rust のバージョンが 1.42.0 だった時代に書かれた…