けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

価格に関する問題

新着順 人気順

JOI 本選 2016 A - オレンジの出荷 (AOJ 0625) (2Q, 難易度 6)

区間を分割していくタイプの DP。とても教育的な典型問題という感じですね。 問題へのリンク editorial 類題は超多数!!! 問題概要 正の整数 と、 個の正の整数 が一列に並んでいる。これを左から順に何個かのグループに分けていく。ただし、各グループに…

AtCoder ABC 164 E - Two Currencies (1D, 青色, 500 点)

これ、頂点を倍加してダイクストラする系。 問題へのリンク 問題概要 頂点 辺の連結な無向グラフが与えられる。各辺 には 通行に要する料金 円 (所持金が 以上でなければ通行できない) 通行に要する所要時間 秒 という属性がある。また、各頂点 では所持金を…

Codeforces Round #625 (Div. 1) C. World of Darkraft: Battle for Azathoth (R2000)

セグ木を使って差分更新していく系、解けるけど実装が苦手すぎるので、こういうのをスパッと書けるようになりたい! 問題へのリンク 問題概要 個の武器と、 個の盾を持って、 体の敵に立ち向かう。あたなは武器の中から 1 個、盾の中から 1 個を選ぶ (初期状…

AtCoder ABC 141 D - Powerful Discount Tickets (2Q, 緑色, 400 点)

問題を読み替えつつ Greedy!!! 問題へのリンク 問題概要 個の品物があって、それぞれ 円で売られている。今 枚の魔法の割引券があって、品物を買う際に割引券を好きな枚数使うことができる。 円の品物を買う際に 枚の割引券を使った場合、その品物を 円で…

AtCoder ABC 121 C - Energy Drink Collector (5Q, 灰色, 300 点)

これでひとまず ABC 100 以降の CD 問題は全部書けた 問題へのリンク 問題概要 個のお店があって、各店 では 1 本 円のエナジードリンクを 本まで買うことができる。 全部で 本のドリンクを買いたい。最小で何円で実現できるか? 制約 考えたこと 基本的に安…

Codeforces 552 DIV3 F. Shovels Shop (R2300)

問題概要 個の品物があって、それぞれ価格は である。ここから 個の品物を何回かに買いたい。ここで一回の買い物につき一回ずつ使えるクーポン券が 個あって (使わなくても良い)、各クーポンは ちょうど 個の品物を買ったならば、そのうちの安い順に 個の品…

AtCoder ABC 124 A - Buttons (8Q, 灰色, 100 点)

たったこれだけの問題でも、学ぶべきことがすごくあるイメージ!!! 問題へのリンク 問題概要 2 つのボタンがあってそれぞれ大きさが である。 大きさ のボタンを押すとコインが 円もらえて、ボタンの大きさが 1 減って になる。 2 回だけ好きなボタンを押…

JOI 予選 2015 F - 財宝 (AOJ 0613) (2D, 難易度 9)

スライド最小値の練習 問題へのリンク 類題とか drken1215.hatenablog.com 問題概要 個のアイテムがって、それぞれ市場価値 と貴重度 が与えられる。 今、A さんと B さんがそれぞれアイテムのうちの何個かをとる。このとき、A さんと B さんは同じアイテム…

AtCoder ARC 098 F - Donation (赤色, 1000 点)

本番中に解きたかった... ARC 098 F Donation 問題概要 N 頂点 M 辺の連結な単純無向グラフがあります。 頂点 i には二つの整数 Ai, Bi が定められています。 このグラフ上で次のようなゲームをします。 初めに、W 円を持った状態で好きな頂点に立つ。 ただ…