2016-11-14 - TopCoderの学習のお時間

最後の問題までやる時間とれないですねえ…

最小公倍数

F(K) の上界が K/2 であることはすぐにわかって、次のように K/2 になる例が構成できるので F(K) == K/2

4 5 1 2 3
3 4 5 1 2
2 3 4 5 1
1 2 3 4 5
5 1 2 3 4

5 6 7 1 2 3 4
4 5 6 7 1 2 3
3 4 5 6 7 1 2
2 3 4 5 6 7 1
1 2 3 4 5 6 7
7 1 2 3 4 5 6
6 7 1 2 3 4 5

i=k の場合が何通りか == iよりも左の(k-1)個に 1〜N-1のうち何個を割り当てるか == C(N-1,k-1)

なので、 i=1,2,...N の場合を足し上げると C(N-1, 0) + C(N-1,1) + ... + C(N-1,N-1) = (1+1)^(N-1)

なので、求める答えは i=1,N の場合を除いた 2^(N-1)-2

S上のマッチ箇所を列挙してからDP

文字列のマッチはローリングハッシュでやったら、ハッシュ衝突するテストケースが含まれてたみたいでやたら時間かかった…。せっかくSuffixArrayライブラリ持ってるのだからそっち使っとくべきだった

木DPですべてのあり得る経路の合計長を求める

y軸方向のどの座標にhorizontalな辺があるかをBITで持ってx軸方向に平面走査

各辺が交差する回数を出さないといけないのでxy入れ替えて2回やる

なんか重心分解とかでできそうなんだけど、よくわからないので独自なアルゴリズムでがんばっていた。

各ノードにBITを2つ持たせて Weighted Union Heuristics で木DPをする。

2つのBITは、それぞれ次の値を持つ。

そのノードの子孫（自身含む）で始まり、そのノードで終わる経路のうち最後の移動で標高が上がっているもので、経路の中に「上がって下がる」をi箇所含むものが何個あるか
上と同じ経路のうち、最後の移動で標高が上がっていないもの

BITに先頭へのadd（既存の要素は1つずつ後ろへshiftされる）をサポートさせる必要があったので、ただのBITではなくて改造を加えた。

最初はサイズに余裕を持たせておいて配列の途中から使い、先頭へのaddのときは前側に伸ばしていって、いっぱいになったらキャパシティを2倍にしてコピーする、といった実装にした（vectorの伸長みたいな）。

O(N logN^2)

行列累乗で部分点のみ

手つかず

DFSしただけ

34.069点

~~上位のスコアが理論限界超えてる気しかしなくて何かがおかしい（ソースをチラ見したけどわからず…）~~

【追記】自分のコードがバグってるだけでした…