練習メモ2-4 - Handmade Summer

最近木の問題をよく見る。
CodeForces 397div1 and div2
http://codeforces.com/contest/765
D Artsem and Saunders
頑張って式変形すると
・hの値域についてfは恒等関数になる
・fの値域とhの値域は一致する
がわかる。
hを先に決めて、gは二分探索で引っ張ってくればいい。

Rust Playgroundからgistを生成してみた。

E Tree Folding
ある根から出ている長さが同じパスを選んで、片方消す（このとき、木の連結性が壊れないようなパスを選ばないといけない）。
この操作を繰り返してパスにした時の最小の長さを求めろ、という問題。

とりあえず根付き木になおして条件を拾っていくと
１．部分木がパスになれる時
部分木の根から葉までの深さが全部同じ
２．根として選んだノードｖを真ん中にするパスが作れるとき
子を全部パスにfoldしたとき、長さが二種類以下
３．部分木の根uを真ん中にするパスが作れる時
子を全部パスにfoldしたパス　＋　自分から親への辺を含むパス　の長さが二種類以下

なのでとりあえず部分木について、
・パスになれるか調べる
・なれるならそれでよし、なれないなら３の条件を試してダメなら終了
とやるDFSをする。２の条件は適当に場合分けする。

方針は悪くなかったんだが、詰めの甘さ＆実装力がなあ。
ところでok(x)とかfail()とやるときにexit(0)してしまうんだけどどうもパターンマッチと相性が悪い。
panic!はどうやってmismatched typeを回避しているんだろうか。

CodeForces 381 div2 d
辺に重さがある根付き木があって、各ノードiに番号aiが割り振られている。
各ノードvについてuがvの部分木に含まれかつdist(u, v) <= auであるようなuの数を数える。

愚直に、各ノード番号と距離をいれたvectorを渡していく再帰関数（↓こんなん）を考える。

これは自明にn ^ 2かかるから速くしよう。
番号でなく、根からの距離d[i] - a[i]をいれてソートしておくと、
vがuのの支配下にある条件は
d[u] - d[v] >= a[u]
⇔
d[u] - a[u] >= d[v]
となりこの値がある程度小さくなるともうダメなので、ループの途中でbreakできそうだ。

この考えをさらに発展させて、vectorのかわりにmaxHeapにd[i] - a[i]をいれたものを渡していく再帰を考えると、マージテク（常に小さい方を大きい方にマージするやつ）でヒープのマージが合計nlog^2n（実際はもう少し速い？）、popする操作も合計nlognなので普通に間に合ってしまう。

RustのBinaryHeap::appendは大きい方にマージする実装になっているので勝手にマージテクしてくれる。
また、パス上の距離の配列をもって二分探索でuがvの支配下におかれるようなvの中で一番上にあるのを見つけてパス上でimos法するという解法もある。

ABC014　D 閉路
AtCoderが昔の問題でもRust使えるようになってしかもRust1.15.0になって完全に神サイトになったのでセグ木のverifyがてら解いた。
解法はLCAするだけ。RMQを使ったLCAは初めて書いたけど、ノード数二倍にすればいい感じに持てるっていうのが面白い気がする。
http://abc014.contest.atcoder.jp/submissions/1111377
ところでこのセグメントツリー、何回か使っているんだけどupdateの部分を一回もverifyしてないのでやや不安である。
AOJでRust使えれば捗るんだけどなあ。
Rustのジェネリクスは全体としてはとても優れていると思うが、どうせ整数か実数しか使わないみたいなところでT: Ord + Eq + Add + AddAssign + ....とやるのはさすがにアホっぽいので、今回のRMQの実装ではtype Int = hoge;というセコいテク使ってみた。