ぱーぽーの競プロ記

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

動的計画法

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種類の座席の選び方のどちらかによって座る座席を選ぶ。 「とにかく座りたい気分」:空席の中で最も番号が小さいものを選ぶ。 「余裕があ…

ABC #018 C 菱型カウント

概要※問題文の内容を少し変更しています。RxCのグリッドがあり、各マスにはoまたはxの印がついている。そこに、「あるマスからユークリッド距離でK-1以内のマスの印を全て変えることのできるスタンプ」を1回押すことができる。例えばK=2のときは、 □■□ ■■■ …

TopCoder SRM 648 Div1 Easy : AB

概要以下の条件を満たす文字列が存在するか求めよ。・N文字 ・文字列sは'A'と'B'の2種類からなる ・s[i]=='A'かつs[j]=='B'となるペア(i,j)がK組ある (0 解法[2015/2/3:別解(動的計画法)を追加]== 貪欲 == 'A'と'B'のそれぞれの個数の積がK以上になるもの…

ABC #015 D 高橋くんの苦悩

概要幅がA[i]で重要度がB[i]のスクリーンショットがN枚ある。幅の合計がW以内に収まるようにK枚まで選ぶことができる。 そのときの重要度の合計を最大化する問題。http://abc015.contest.atcoder.jp/tasks/abc015_4解法動的計画法で解くことができる。DPは以…

TopCoder SRM 626 Div2 Hard : NegativeGraphDiv2

概要 N個のノードとE本のエッジからなる有向グラフがある。各ノード間の移動にはコストがかかる時、ノード1からNに到達するための最短コストを求めよ。ただし、以下の操作をcharges回行うことができる。 ・ノード間のコストweightをweight*(-1)にする解法 (…

TopCoder SRM 627 Div2 Hard : BubbleSortWithReversals

概要 数列Aが与えられる。 同じ要素が被らないように連続する要素をK回まで反転することができる。例えば、 A = {3, 2, 1, 5, 4}, K = 2のとき、 {3, 2, 1}と{5, 4}を選んで反転させると{1, 2, 3}と{4, 5}となり、数列Aは、A = {1, 2, 3, 4, 5}となる。この…

KUPC 2014 F テレパシー

概要 問題文はこちら http://kupc2014.contest.atcoder.jp/tasks/kupc2014_fキツネを強化するゲーム。解法 木DPで解くことができ、 dp[i][j] := i番目のキツネの力がj以上のときの最小コスト となる。(しめじ先生の記事や他の方の解答をチラ見して木DPがど…