ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

確率

yukicoder No.23 : 技の選択

概要体力Hの敵にダメージを与えて倒すことを考える。こちらには2種類の攻撃方法がある。 通常攻撃: 1回の攻撃でAダメージ与える。必中技。 必殺技: 1回の攻撃でDダメージ与える。2/3の確率で命中。1/3の確率で攻撃を外す。 この2種類の攻撃を使って敵…

CODE THANKS FESTIVAL 2014 A日程 G : 通勤電車と気分

概要電車には1~Kの番号が付けられたK個の座席が一列に並んでおり、N人がこれらの座席に座ることを考える。人は以下の2種類の座席の選び方のどちらかによって座る座席を選ぶ。 「とにかく座りたい気分」:空席の中で最も番号が小さいものを選ぶ。 「余裕があ…

TopCoder SRM 626 Div1 Easy : FixedDiceGameDiv1

問題概要 1~bの値が書いてあるb面サイコロをa個持っているAさんと、1~dの値が書いてあるd面サイコロをc個持っているBさんがいる。二人がそれぞれ持っているサイコロを全て振って出た目の合計を比べるとき、AさんがBさんより大きい値になる期待値を求める問題…

KUPC 2014 D ハミング

概要 問題文はこちら http://kupc2014.contest.atcoder.jp/tasks/kupc2014_d解法 数学できないマンだったので、しめじたんの記事を参考にさせていただきました。(分かりやすい、神) http://d.hatena.ne.jp/simezi_tan/20140710/1404932438文字列s1とs2が与え…

ABC #011 D 大ジャンプ

概要 問題文はこちら http://abc011.contest.atcoder.jp/tasks/abc011_4解法 本番で解けなかったやつ、2パターンのやり方で解き直した。まず共通する前処理として、どう頑張っても目的地に辿りつけない場合はそこで終了。 そして上下左右同じ距離を進むので…

ARC #023 C タコヤ木

概要 問題文はこちら http://arc023.contest.atcoder.jp/tasks/arc023_3解法 (他の記事を参考にしながら解いた。説明に間違いがあるかもしれない)例えば入力で 1 -1 -1 3 が与えられた場合、単調増加な数列になるのは ・1 1 1 3 ・1 1 2 3 ・1 1 3 3 ・1 2…