最近解いた問題
たまには競技プログラミングのブログも書こうと思います。
面白かったのとか教育的なのとかをまとめる。
■ Yandex 2016 round2 D
<問題概要>
Ax+By = Cを満たす非負整数x,y全てに対して C(x+y,x)の総和を求めよ (A,B<=100 C<=10^18)
<解法>
要するに「総和がCになるようにA,Bを並べ替える方法は何通りあるか」を求めればよい。行列累乗するだけ。
■ csacademy beta round 7 Array Coloring
<問題概要>
N個の無色のセルをM回異なる色で区間を塗った結果が与えられる。考えられる色の順番すべてに対して、「色を塗られた回数」の最大値が最大になるとき、その回数を求めよ (N,M<=100000)
<解法>
色ごとに(左端、右端)を求め、ある色と色に対し、「片方の(左端、右端)を含む最小の(左端、右端)がもう片方の(左端、右端)」であるとき、対応する頂点間に有向辺を結ぶことを考えると、森になる。ダミーの根を作り木にして、木DPをする。
「間に根の色を挟まないような子の集合に対し、1つはdpの値を、その他は1を加えた値」の最大値が今考えてる部分木に対するDP値。
■ SRM691 Div1 Med
<問題概要>
仕事が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
<問題概要>
長さ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
<問題概要>
根付き木が与えられる (頂点数<=300000)
全ての部分木に対し、(ある頂点からすべての頂点へのパスの重みの総和)の最小値のXORを求めよ。
<解法>
重心が最小化する頂点なのはまあそれはそうっていう感じで
部分木に対し、重心が求まればパスの重みは求まるので、重心を求めることを考える。(地味に256MB制限が厳しいのでsegtreeに逃げることはできません)
ところで、ある部分木(根をVとする)に対し
すべての部分木サイズがもとの部分木サイズの半分以下ならVが重心になり、そうでないときは
部分木サイズが最大の子(V2とする)の重心の祖先のどれかが重心になることが示せる。
(前者は自明、後者はV2の祖先以外が重心になるとすると、その頂点の部分木サイズは明らかに小さすぎるから矛盾)
よって、(自分から子へのパス重みの総和、重心)を返しつつDFSをすればOK.コスト計算はDoublingでできる。
(重心を求めるフェーズがやばくならないのは、「系列」が変わらない限りO(N)で済むことと、「系列」が変わるときには部分木サイズが倍以上になるからまとめてO(N log N)的な感じだと思います)
