Educational Codeforces Round 3 - らての精進日記

解いた。うける。

A. USB Flash Drives

配列 $a$ を降順にソートして、条件を満たすまで先頭から足す。
http://codeforces.com/contest/609/submission/15727347

B. The Best Gift

(ジャンルが異なるように2つ取り出す方法の数)=(全ての取り出し方の総数)-(ジャンルが被るように2つ取り出す方法の数)
という感じでやります。求める取り出し方は、 $c_i=\sum_{k=1}^{n} (a_k==i)$ とすれば、 $ans=\frac{n*(n+1)}{2}-\sum_{k=1}^{m} \frac{c_i*(c_i+1)}{2}$ みたいな。数式が強そうでかっこいいけど、つまりはやるだけ。
http://codeforces.com/contest/609/submission/15727410

C. Load Balancing

書くのがめんどくさくなってきた。
全ての値の平均値(切り捨て)を求め、すべての値を平均値に持っていく。ただし、平均値を $h$ とすると、一部の値は $h+1$ にしなければならない感じ。
http://codeforces.com/contest/609/submission/15727571

D. Gadgets for dollars and pounds

日数について二分探索する。ドル、ポンドの両方とも、最も得をする日に両替して一気に買うのが最適。部品を安い方から $K$ 個購入して、必要なコストが $S$ 以下ならOK、そうでなければNG。あとは、適当に $-1$ を出力するなり、解を出力するなりする。 $O((N+MlogM)*logN)$ とかじゃないですかね(二分探索で $O(logN)$ 回処理をして、それぞれの処理にO $O(N+MlogM)$ くらいかかるので)。解説読んだ感じだとこれよりも若干速いオーダーで解けそう？( $logM$ を消せるくらい)
http://codeforces.com/contest/609/submission/15727986

E. Minimum spanning tree for each edge

Kruskal法の要領でやる。まず最少全域木をKruskal法で求め、木を構成する。最少全域木のコストを $S$ とおく。次に、もう一度Kruskal法を行う。このとき、今見ている辺を $e$ 、 $e$ の両端の頂点を $u,v$ とすると、 $e$ が最少全域木に含まれる(union find木内で $u,v$ が同じ集合に属していない)場合は、 $e$ についての解の値は最少全域木のコストに一致する。(つまり、 $ans(e)=S$ )そうでない場合、最少全域木内の $u,v$ 間のパスに含まれる辺のうち、最もコストが大きいものを取り除いて $e$ を追加するのが最適。このとき、取り除いた辺を $d$ とし、 $cost(e)$ で $e$ のコストを表すことにすると、 $ans(e)=S-cost(d)+cost(e)$ となる。
ここで、 $cost(d)$ を高速で見つける必要がある。これはダブリングを用いて、 $2^k$ 個先の頂点の番号と、 $2^k$ 先の頂点とのパスに含まれる辺の中で最大の辺の重みをそれぞれ計算しておけば求めることができる。一回当たり $O(logN)$ で求まるので、全体として $O(NlogN)$ で解ける。
http://codeforces.com/contest/609/submission/15728942