Hatena::Grouptopcoder

Hiro180の日記

 | 

2016-06-12最近解いた問題

たまには競技プログラミングのブログも書こうと思います。

面白かったのとか教育的なのとかをまとめる。

Yandex 2016 round2 D 23:48

<問題概要>

Ax+By = Cを満たす非負整数x,y全てに対して C(x+y,x)の総和を求めよ (A,B<=100 C<=10^18)

<解法>

要するに「総和がCになるようにA,Bを並べ替える方法は何通りあるか」を求めればよい。行列累乗するだけ。

csacademy beta round 7 Array Coloring 23:48

<問題概要>

N個の無色のセルをM回異なる色で区間を塗った結果が与えられる。考えられる色の順番すべてに対して、「色を塗られた回数」の最大値が最大になるとき、その回数を求めよ (N,M<=100000)

<解法>

色ごとに(左端、右端)を求め、ある色と色に対し、「片方の(左端、右端)を含む最小の(左端、右端)がもう片方の(左端、右端)」であるとき、対応する頂点間に有向辺を結ぶことを考えると、森になる。ダミーの根を作り木にして、木DPをする。

「間に根の色を挟まないような子の集合に対し、1つはdpの値を、その他は1を加えた値」の最大値が今考えてる部分木に対するDP値。

SRM691 Div1 Med 23:48

<問題概要>

仕事がN個あり、経験値と係数が決められている。得られる収入は(これまでの経験値の総和)*(その仕事の係数)である。

ただし、Nは偶数で、N/2個仕事をした時点で研修に参加し経験値がX増えるものとする。

収入を最大化せよ。 (N<=50,経験値,X<=100000,係数<=10)

<解法>

X=0の場合を考える。

(経験値、係数) = (ex1,co1),(ex2,co2)の2つの仕事を考える。これまでの経験値をexpとすると、収入は

・前者->後者: (exp+ex1)*co1 + (exp+ex1+ex2)*co2

・後者->前者: (exp+ex2)*co2 + (exp+ex1+ex2)*co1

となるので、(前後はどちらも同じ。)

実質ex1*co2とex2*co1の比較であり、それはつまりex1/co1 と ex2/co2の比較である。

以上より、(exp/coef)が大きい方からやるのが良いと分かった。 (こういう問題、150問に1問くらいのペースで見るイメージがある)

X>0の時にはこれではうまくいかない。しかし、Xの前後ではそれぞれこの順番で並べるのが良いので、

順に振り分けていくDPを考える。

ここで、収入の計算方法を

(exp1+exp2+.....+expE) * coEを毎回加えるのではなく、(coE+co(E+1)....+coN) * expEを毎回加えるという発想をすると、

研修の前にやった仕事に対する係数の総和を決め打ちすると(tmpCoとする)

前に振り分けたときは(sum(co)-sum(振り分け済みの前のco)) * exp

後ろに振り分けたときは(sum(co)-tmpCo-sum(振り分け済みの後ろのco)) * exp

を毎回加えればOK。

計算量は50 * 25 * 250のDPを25*10回くらいするのでまぁ通る。 良問。

SRM692 Div1 Med 23:48

<問題概要>

長さSの文字列が与えられる。(length(S)<=100)

以下の条件を満たす文字列は何通りあるか.

・non-intersectなSの個数の最大値はK個 (K<=10^9)

・長さはK*length(S)以上K*length(S)+N以下 (N<=1000)

・文字はすべて英小文字

<解法>

貪欲に取っていったときの出現箇所を考える。

1つ目の出現箇所までに無駄な部分がi文字になるような場合の数は、愚直なDPで計算できる。

一つ前の出現箇所から無駄な部分がi文字になるような場合の数も、愚直なDPで計算できる。

ここで、dp[i][j] = 2^i個文字列が出現するときに無駄な部分がj文字になるような場合の数

とすると、O(N*N*log K)くらいで計算できる。

最後の出現箇所から無駄な部分がi文字あるような場合の数も、愚直なDPで計算できる。

以上で求めた値を掛け合わせて足せば答が出る。

SRM692 Div1 Hard 23:48

<問題概要>

根付き木が与えられる (頂点数<=300000)

全ての部分木に対し、(ある頂点からすべての頂点へのパスの重みの総和)の最小値のXORを求めよ。

<解法>

重心が最小化する頂点なのはまあそれはそうっていう感じで

部分木に対し、重心が求まればパスの重みは求まるので、重心を求めることを考える。(地味に256MB制限が厳しいのでsegtreeに逃げることはできません)

ところで、ある部分木(根をVとする)に対し

すべての部分木サイズがもとの部分木サイズの半分以下ならVが重心になり、そうでないときは

部分木サイズが最大の子(V2とする)の重心の祖先のどれかが重心になることが示せる。

(前者は自明、後者はV2の祖先以外が重心になるとすると、その頂点の部分木サイズは明らかに小さすぎるから矛盾)

よって、(自分から子へのパス重みの総和、重心)を返しつつDFSをすればOK.コスト計算はDoublingでできる。

(重心を求めるフェーズがやばくならないのは、「系列」が変わらない限りO(N)で済むことと、「系列」が変わるときには部分木サイズが倍以上になるからまとめてO(N log N)的な感じだと思います)

 |