codeforces #402 div2 A, B, C, D
問題A
問題概要
n人の生徒が属する2つのグループA, Bがある。各生徒は1から5の5段階の成績がつけられている。グループ間で生徒を交換することでそれぞれのグループで同じ成績の生徒の人数が等しくなるようにしたい。必要な最小の交換回数を求めろ。不可能であれば-1を返せ。
解法
まず、ある成績の生徒の人数が奇数人であればこのようなことは不可能なため-1を出力します。各成績の合計人数の半分の人数がそれぞれのグループにいる状態になれば条件が達成されるため、この人数との過不足から必要な回数を求めます。
成績 1 2 3 4 5 1 2 3 4 5 グループA 2 2 0 0 0 +1 0 -1 0 0 グループB 0 2 2 0 0 -1 0 +1 0 0
上記のような例を考えます。グループAは成績1の生徒が1人多く、成績3の生徒が1人少なく、グループBはその逆です。よってグループAの成績1の生徒とグループBの成績3の生徒を交換すればよく"1"を出力するべきです。このように各グループの過剰分の半分が求める結果になります。
成績 1 2 3 4 5 1 2 3 4 5 グループA 4 2 0 0 0 +2 0 -1 0 0 グループB 0 2 2 0 0 -1 0 +1 0 0
次の例のように過剰分の和が奇数のときどのように交換しても条件を満たすことはありえないため、-1を出力します。
問題B
問題概要
整数n, kが与えられる。nのある桁の数を消去することで、nを10^kで割り切れるようにしたい。条件を満たす最小の消去数を出力せよ。
解法
i(1 <= i < |s|)桁を消去するときのパターンを深さ優先探索で全列挙し、条件を満たした最小の消去数を出力しました。
最初、10*kで割り切れるようにする最小の消去数と勘違いしていたので、全列挙で解きました…後ろから見ていって0の数を数える方が単純に解けそう。
問題C
問題概要
n個の品物が存在し、現在の値段A[i]と一週間後の値段B[i]が与えられる。現在少なくともk個の品物を買う必要があり、残りは一週間後に買う。（現在k個以上の品物を買うことも可能）このとき、品物の購入にかかる最小の費用を求めろ。
解法
現在より一週間後の値段のほうが高い品物がk個以上ある場合、それらの品物を全て買い、一週間後に残りの品物を買うのが最善となる。
値段が上がる品物がk個より少ない場合は、b[i]-a[i]が大きいk個の品物を現在に買い、残りの品物を一週間後に買うのが最善となる。したがって、a[i]-b[i]をキーにソートし最初からk個の品物を現在に買う。
問題D
問題概要
単語tと単語pが与えられる。i回目の消去では単語tからa[i]番目の文字を消去する。単語tに部分文字列として単語pが含まれる最大のiを求めよ。
解法
答えとして求めるのがk回目の消去のとき、1回目からk回目までの全ての消去で条件が成り立っており、k回目以降の消去では条件が成り立っていない。したがって、二分探索を行うことで答えkを求めることができる。消去を行った後の単語tに単語pが含まれているかの判定はO(|t|)、二分探索はO(log|t|)なため、O(|t|log|t|)で答えを求めることができる。
