読者です 読者をやめる 読者になる 読者になる

らての精進日記

修行をします

Educational Codeforces Round 3

codeforces.com

解いた。うける。

A. USB Flash Drives

配列{ \displaystyle 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)回処理をして、それぞれの処理にOO(N+MlogM)くらいかかるので)。解説読んだ感じだとこれよりも若干速いオーダーで解けそう?(logMを消せるくらい)
http://codeforces.com/contest/609/submission/15727986

E. Minimum spanning tree for each edge

Kruskal法の要領でやる。まず最少全域木をKruskal法で求め、木を構成する。最少全域木のコストをSとおく。次に、もう一度Kruskal法を行う。このとき、今見ている辺をeeの両端の頂点を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

F. Frogs and mosquitoes

主に次の2つの処理をいい感じにすればいいと分かります。
(i) 新しく蚊を追加するときに、その蚊を食べる蛙を探す(どの蛙もその蚊を食べられない場合もある)
(ii) (i)で食べられなかった蚊をいい感じに格納して、今後強い蛙が現れたときに検索する。

(ii)の機能は二分探索木でいいです(std::setにpairをいれた)。
(i)の機能は、区間更新ができ、区間の最小値を求めることができる遅延セグ木でやりました。
http://codeforces.com/contest/609/submission/15733503

まとめ

特に記事を書く意味がなかった。この記事を作成するのに1時間以上かかり虚しさしかない。