http://codeforces.com/contest/799
A. Carrot Cakes
T秒でK個ケーキを焼ける装置が1つある。
同じ装置をもう一つだけD秒かけて用意できる。
用意すると、並行してケーキを焼ける。
同じ装置を用意することで、用意しない場合より早くN個のケーキが作れるか
（同時刻にできる場合はNOとする）
B. T-shirt buying
N個のTシャツがあり、i番目の値段はP[i],表がA[i]色,裏がB[i]色となっている。
M人の人が以下のルールでTシャツを買うとき、それぞれいくら払ったか(買わなかったら-1)
- i番目の人の好きな色はC[i]
- 表が裏が好きな色のTシャツの中で値段が最小の物を買う
C. Fountains
N個の噴水と、C枚のコイン、D個のダイアがある。
N個の噴水から丁度2個の噴水を買う。
i番目の噴水はP枚のコインorP個のダイアで買うことができ、美しさはB[i]である。
2つの噴水の美しさの和の最大値は？
D. Field expansion
H×Wの長方形の辺に幾つか数字を書けてA×Bの長方形が完全に乗るようにしたい。
数字はN個あり、最小で何個必要か。
以下、解説
A. Carrot Cakes
http://codeforces.com/contest/799/submission/27017773
シミュレーションしていく。
考えるべき時間は1000000秒までで大丈夫(実装ではもう少しゆとりを持たせてある)。
あとは、T秒後にケーキが焼けて、D秒たった後は、もう一つの装置を動き出すので、そちらでもカウントする。
あとは、個数がN個以上となるかを見ていけば良い。
B. T-shirt buying
http://codeforces.com/contest/799/submission/27019370
色の数が少ないことに注目する。
que[i] := 表か裏の色がi色であるTシャツの{値段,何番目のTシャツか}が値段昇順で入っているキュー
vis[i] := i番目のTシャツがもう売れている
をまず用意する。
M人の人に対し、que[C[i]]の最初を見ていく。
もし、最初のTシャツが既に売れていたら次のシャツを見る…としていき、売れてないTシャツが来れば買うし、買えなければ-1
C. Fountains
http://codeforces.com/contest/799/submission/27045190
この解法はほぼDEGwerさんの解法を参考にしています。
「1. コイン + コイン」「2. ダイア + ダイア」「3. コイン + ダイア」の組合せを試していく。
1.と2.は状況的にはそんなに変わらないので、同じ手法を使う。
3.はコインで買える噴水の美しさ最大とダイアで買える噴水の美しさ最大を足して答えるだけ。
最初の2つの組合せのやり方だが、
v := 噴水の{コスト,美しさ}がpair昇順ソートで入っている
lim := コストの最大限界
x := 今までに出てきた噴水の{コスト, 美しさ}が入っているが、美しさが単調増加している
now := 今までに出てきた噴水の美しさの最大
res := 答え
これを使って計算していくが、i番目の噴水と組み合わせるのに[1, i - 1]番目の中から、コストの和がlim以下で、美しさの和が最大となる物を探していけば良いのだが、配列xには美しさが単調増加で入れてあるので、コストの和がlim以下となるための最大のコストをupper_boundで探せば、その要素によって美しさの和が最大となる。
探索範囲を適切に限定するために配列をもう一つ用意して、追加していく手法。
初めて見た。
D. Field expansion
http://codeforces.com/contest/799/submission/27044755
N個中x個取る時、わざわざ小さい数を利用する必要は特にないので、x個使うとすると、大きい方からx個使えば良い。
あとはdp[i] := 縦がiの時の横の最大値(i < 最大値が必ず成り立つ)として、dpをしていくが、愚直にやるとdp[10^5][10^5]くらいになりそう。
しかし今回はdpの中身が疎になりそうな感じがあるので、map
あとは、結構枝刈りできる部分があるので、iの上限をA,最大値の上限をBとして枝刈りをした。
細かい努力をすると通る。
