10/9 PKU - Algorithmer’s note

3613 Cow Relays

重み付き無向グラフが与えられる。グラフ上のある2点をとったとき、その2点を結ぶちょうどN個の辺を経由するような経路のうち、最も重みの総和の小さいものを答えよ。

まず入力の形が迷惑なのでidentifyする。
次に、辺が高々100本ということと、各頂点少なくとも2辺に接続していることから、頂点が高々100個しか存在しないことがわかる。
そうした上で、最初に各頂点間の辺数1の最短距離の表を作成する。辺数Aの表と辺数Bの表があれば、辺数A+Bの表が作成できるので、あとは行列の累乗みたいなことをやる。頂点数をVとして、O(V^3 log N)だが通る。

2458 Rigging the Bovine Election

5*5のグリッドで、7マスの連結部分を選んで、その中にJが4個以上含まれるように剃る方法は何通りあるか。

ただの全探査。同じものを2回以上数えないようにすると後始末がなくて楽。

2568 Decode the Tree

木について、次の操作をした列が与えられる。
「木の葉で、最も番号の小さいものを選び、それを記録して、取り除く。最終的に根だけになるまで繰り返す。」
木を復元せよ。

入力して、やるだけ

3612 Telephone Wire

N本のポールがあり、高さがまちまちである。ポールの間にワイヤーを張る。ワイヤーを張るコストは、ポールの高さの差×Cである。あるいは、ポールを伸ばすことができる。X伸ばすにはX^2のコストがかかる。コストを最小化せよ。

Cを最大の高さとして、O(N×C)のDPでも遅いが通る。O(N×C^2)だと多分通らない。

3066 Maximum

x₁, x₂, …, x_mを、次の条件を満たすように定める。
-1/√a <= x_i <= √a (i=1,2,…,m)
x₁ + x₂ + … + x_m = b * √a
このとき、x₁^p + … + x_m^p を最大化した値を求めよ。pは偶数である。

a'=1/√aとして、x'_i=x_i/aとすると、
-1 <= x'_i <= a となって見通しがよくなる。
pが偶数で2以上なので、思いっきり偏らせたほうが大きくなるので、-1のものをできるだけ使って、あとはたくさん偏らせると、適当にやっても答えが出る。