あるノードを根とした時、aとbの単純パスはa-LCA(a,b)-bである。
※LCAはLowest Common Ancestor すなわちその距離L(a,b)は、
L(a,b) = L(a,LCA(a,b))^L(LCA(a,b),b) ここで、 A^X^X = A
であることを考えると
L(a,b) = L(a,LCA(a,b))^L(LCA(a,b),b)
= L(a,LCA(a,b))^L(LCA(a,b),root)^L(root,LCA(a,b))^L(LCA(a,b),b) ※rootは根
= L(a,root)^L(root,B) である。
つまり、a-root-bと辿った場合に等しい。
したがって、適当なノードを根とし、全探索で距離を求めたあと、a-root-bの距離がXとなる組み合わせを数えればよい。

2016-06-22

AtCoder Regular Contest 048 C - 足の多い高橋君

AtCoder ARC-C ARC 回文競技プログラミング

問題概要

(リンク)http://arc048.contest.atcoder.jp/tasks/arc048_c

高橋君はN本の足がある
N本の足はLi本のパーツに分かれている
Li本の足に0か1を書き込む
任意の2本の足A,Bを選んだ時、Aのつま先-胴体-Bのつま先と辿った時、0、1は回文となっていなければいけない。

解法

公式スライド参照

AtCoder Regular Contest 048 from AtCoder Inc.

2016-06-21

AtCoder Regular Contest 049 C - ぬりまーす

ARC-C 強連結成分分解グラフ SCC AtCoder 競技プログラミング

頂点が有向グラフである意味がない…

問題概要

(リンク)http://arc049.contest.atcoder.jp/tasks/arc049_c

N頂点の有向グラフがある
頂点に色を塗る
その際以下の制約つける
- 頂点xに色をぬるとき、頂点yに色が塗られていなければならない
- 頂点uに色を塗るとき、既に頂点vに色が塗られていてはいけない
適切な順番で色を塗った時、最大いくつ色を塗られるか

解法

制約をグラフで表現する。

ひとつ目の制約はy→xというエッジ
ふたつ目の制約は
- u → vというエッジ
- あるいはuを通行不可 (塗らない) とする

ふたつ目の制約は最大10個しかないので「u → vというエッジ」、「uを通行不可とする」を総当りする。
作成したグラフを強連結成分分解すると、強連結成分として2つ以上のノードがある場合、そのノードには辿りつけない。
例えばu←→vのようなエッジが貼ってあれば、お互いを塗るためにお互いが先に塗られていなければいけないためである。
また、通行不可としたノードから辿り着けるノードは通行不可である。

2016-06-19

AtCoder Beginner Contest 040 D - 道路の老朽化対策について

ABC ABC-D AtCoder Union Find 競技プログラミング

問題概要

(リンク)http://abc040.contest.atcoder.jp/tasks/abc040_d

y_i年に作られた道は都市a_iと都市b_iを結ぶ
住民jはv_jに住んでいてw_j以前に作られた道を通りたくない
全ての住人が移動できる都市の数を求める

解法

UnionFindを使う
- 少し拡張してUnionの個数を数えられるようにする
全ての住人に対して1からUnionFindを使うとTLEとなる
- v_jが降順となるようにクエリを並べ替える
- w_jが降順となるように道を並べ替える
- こうすることで重複した処理を行わずにすむ
O(max(N log N, Q log Q, Q+M log α(N) ) ) ？ (わからん) (間に合うということはわかる)

2016-06-19

AtCoder Beginner Contest 040 B - □□□□□

ABC ABC-B AtCoder やるだけ愚直競技プログラミング

ABCのBなのに、難しいと感じた人が多かった問題。 1回REでWAを出してしまった。

問題概要

(リンク)http://abc040.contest.atcoder.jp/tasks/abc040_b
n枚のタイルを敷き詰めて、長方形を作る。
その時、短辺と長辺の差 + 余ったタイルが最小になるようにする。

解法

愚直に実装する。
短辺と長辺の組み合わせをすべて試す。
O(sqrt(n))
ans = min (ans, abs(短辺-長辺) + n % (短辺×長辺))

なぜ難しい

短辺と長辺の差に着目すると、1辺をnのルートに近づければいいのでO(1)で求められそうな気がする。
その方向で考えをすすめるとハマる。
あと、短辺と長辺を全て考える時、調べる範囲を適当にすると短辺×長辺が0になる時、余りが計算できずREになった。