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

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

価格に関する問題

AtCoder ABC 246 C - Coupon (diff 336, 300 点)

ソートが必要になるところが少し難しいかもしれない。 問題へのリンク 問題概要 個の商品があって、それぞれ 円である。 またクーポンが 枚あって、1 枚のクーポンを使って次のことができる。 商品を 1 つ選ぶ その商品の価格を 円減少させる ただしもとの価…

JOI 本選 2011 B - 古本屋 (AOJ 0561, 難易度 6)

こういうのは DP! ジャッジページ AOJ の問題文 問題概要 冊の古本があって、 番目の本のベース価格は 円である。またこれらの本は 10 種類のジャンルに分かれており、 番目の本のジャンルは で与えられる。 これらの本から 冊を古本屋で売りたい。ただし同…

JOI 春合宿 2008 day2-1 Nile.Com (難易度 6)

いかにも ABC-E にありあそうな DP!! ジャッジへのリンク 問題文へのリンク これとか似てる atcoder.jp 問題概要 個の店がある。 日間にわたって、いずれか 1 つの店で買い物をする。 日目に 番目の店で買い物をしたときの値段は で与えられる (10 の倍数)…

JOI 本選 2014 B - IOI饅頭 (AOJ 0599, 難易度 6)

まさにナップサック問題!!! 問題へのリンク 問題概要 個の饅頭がある。それぞれ 円で売り出そうとしている (全部売るとは限らない)。 饅頭を得るための箱をいくつか購入することにした。箱は 種類あって、 番目の箱は 饅頭を 個まで詰められる 仕入れるの…

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

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

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

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

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

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

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

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

Codeforces 552 DIV3 F. Shovels Shop (R2300)

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

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

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

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

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