SRM683 Round1 Div.2

無事に全完。

Easy-EqualSubstrings2

問題概要

You are given a string s. Compute and return the number of ways in which we can choose two identical non-overlapping substrings of s.
(The two substrings must be non-empty. Each substring must be contiguous.)

文字列sが与えられるので、重ならない同一の部分文字列の組の総数を求めよ。

解説

これは色々解き方はありそうですが、|S|≦50なので全探索で十分です。

自分は部分文字列a,bの左端をループで指定し、一致するまで文字数を増やしながら答えに加算していくO(N^3)を使いました。

https://github.com/HyogaGlacier/TopCoder/blob/master/683/Div2/Easy.cpp

Med-MoveStonesEasy

問題概要

There are n piles of stones arranged in a line. The piles are numbered 0 through n-1, in order. In other words, for each valid i, piles i and i+1 are adjacent.
You are given two vector s a and b, each with n elements. For each i, a[i] is the current number of stones in pile i, and b[i] is the desired number of stones for this pile. You want to move some stones to create the desired configuration. In each step you can take any single stone from any pile and move the stone to any adjacent pile. Find and return the smallest number of steps needed to create the desired configuration, or -1 if the desired distribution of stones cannot be reached.

石の集まりがn、1列に並んでいます。要素nの配列a,bが与えられます。現在、塊iにはa[i]個の石がありますが、b[i]にしたいです。石を隣り合った塊に1つずつ移していくとき、最小何回石を動かせばよいか求めよ。

解説

yukicoderに似た問題が有った気がします…

例として{5,0,0,0,0}→{1,1,1,1,1}を考えます。左端から石を4個1つ右に動かし、うち3個を右に動かし、2個、1個と移動させるので答えは10。

この考え方を、今度は{0,0,0,0,5}→{1,1,1,1,1}に適用します。左端から-1個石を1つ右に動かし、そこから-2個を右に動かし、-3個、-4個動かすので、合計-10→10回石を動かしたことになります。

流石に違和感を覚えそう（自分自身覚えました）なのでもう1例。
{1,0,0,4,0}→{1,1,1,1,1}は、左端から0個、-1個、-2個、1個動かします。それぞれ正に変えた上で足して答えは1+2+1=4。

こんな感じで左から見ていけばOKです。O(N)。

https://github.com/HyogaGlacier/TopCoder/blob/master/683/Div2/Med.cpp

Hard-SubtreesCounting

問題概要

You are given an undirected tree T. (The input format is specified below.) The vertices of the tree are numbered 0 through n-1.
A subtree of T is any subgraph of T that is connected. The size of a subtree is the number of vertices it contains. Two subtrees are considered different if one of them contains a vertex the other doesn't. Let X be the sum of sizes of all subtrees of T. As X can be large, compute and return the value (X modulo 1,000,000,007).

n頂点からなる1つの無向木Tが与えられます。Tの部分木Aの大きさは「Aに所属する頂点の数」とします。全部分木の大きさXを1,000,000,007で求めてください。
なお、辺は線形乱数っぽいアルゴリズムで生成されます。(余談です)

解説

適当に根を決めて、DFSします。この時に、「その頂点をルートとした時に、この後通る頂点を使ったX」が求まれば良さそうです。

cnt[i]:頂点iをルートとした時のルートを使った部分木の大きさの総和

kind[i]:cnt[i]に入っている木の数

ある状態の木のルートiに新しく部分木(ルートはj)を付けることを考えます。

この時、出来る木のcnt[i]には元の木のどのパターンもkind[j]+1回(新しい木を一切含まない場合あり)出ていて、加える部分木のどのパターンもkind[i]回出現することから、cnt[i]=cnt[i]*(kind[j]+1)+cnt[j]*kind[i]で更新できます。

また、kind[i]も同様にkind[i]=kind[i]*(kind[j]+1)で更新できます。

後は、各頂点のcntを全て足せばOKです。適宜modを取ってください。O(N)。

https://github.com/HyogaGlacier/TopCoder/blob/master/683/Div2/Hard.cpp

感想

1159->1296(Highest)。やっと青になれました。Div1になりますが、事故って緑に戻らないように気を付けたいです。