4完だった。ぐぬぬ。
各辺につき、迂回路があるかどうか、という問題。
5 ①-②を結ぶ重み5の辺があるが、 ①----② その他の辺を使って①→②に距離5でたどり着けるので、 2\ /3 この辺は不要 ③
なので、「必ず2本以上の辺を使う場合の全頂点間最短距離 Dist(u,v)」を計算してやって、
各辺につき、Dist(Ai,Bi)≤Ci なら、その辺は不要と判断できる。
Dist(u,v) は、普通にFloyd-Warshallで(1本の辺だけでもよい)全頂点最短距離 d(u,v) を求めた後、
必要な (u,v) について、minw≠u,v(d(u,w)+d(w,v)) を求めればよい。
①-②の辺は、①-③、③-②が残るなら確かに不要そうだけど、これらの辺も削除されちゃうかもしれないし、 全体的にはやっぱり①-②は必要だった、ということにはならないの?
ならない。
この方針に従う限り、たとえば①-③の辺が削除できるなら、
①-③間をそれ以下のコストで代替できる迂回路が存在するので、①-②の迂回路の一部としてもそっちを使えばよい。
きちんとした証明としては、公式解説の通り、
ちょうど M 種類、というのはややこしくても、M 種類以下、というのはまだ求めやすい。
これをまず求めて、そこから包除原理かなんかでちょうどでないものを除く、 というのがよくある解法なので、この問題もそれで考える。
全 Wi の総和を S=N∑i=1Wi とする。
ある m 個の選び方を固定(mj)し、その Wi の和を Pmj と表すとする。
m=3 で m1={1,3,4} という選び方を固定すると、Pm1 = W1 + W3 + W4 同じ m 個でも、違う選び方 m2,m3,... でそれぞれ Pm2,Pm3,... は異なる
すると、「くじ K 回を通して m1 の中のどれかしか当たらない確率」は、(Pm1S)K である。
ここで、全ての項に 1SK は共通なので最後にまとめてかければよく、分子のみを考えることにする。
まずは、m=M の全選び方 M1,M2,... に対して、 f(m)=∑jPKmj(つまり、全 Pmj の K 乗の総和)を求めたい。
DPで、Wi を順番に加えていくことを考える。
f(M)=DP[N][M][K] である。
DP[i−1][m][k]=Pkm1+Pkm2+... が求まっているとして、ここに新たに Wi を加えた選び方を考慮する。
これを展開整理すると、(長くなるので、DP[i−1][m][k]=dk とおくと)
なので、これまでに求めた成果から、1回の遷移あたり O(k) で求められる。
全部で O(NMK2) で、このDPを埋められる。
f(M)=DP[N][M][K] には、ちょうど M 種類でないものも含まれる。
ここから重複を除いた、「ちょうど」M 種類である求めるべき答えを g(M) とする。
たとえば N=5,M=4 での選び方に対し、
1 2 3 4 5 M1 o o o o M2 o o o o M3 o o o o M4 o o o o M5 o o o o
このように「余分な状態が、しかも重複して」数えられている。
ただし、それぞれいくつ重複しているかは、集合のサイズごとに固定 ({1,2,3} も {2,3,4} も重複している個数は一緒)なので、まとめて除くことが可能である。
M−i 種類しか選ばれない状態が f(M) において重複している回数は、 残りの i 種類を、選ばれていない N−(M−i) 個から選ぶ N−(M−i)Ci である。
よって、i=1~M−1 に対し、f(M)−=N−(M−i)Cig(M−i) をすればよい。最終的に残るのが g(M) である。
途中に出てくる g(m) については、m が小さい方から順に求めていけばよい。O(M2) で計算可能。
繰返し回数がとんでもない数だが、末尾が 1 になったら以降、1 を繰り返すしかないし、 10100 回までには絶対 1 になるので、「1 になったら終了」と考えてよい。
以下、簡単のため √x だけで床関数適用済みの floor(√x) を表すとする。
X=x の答えを f(x) とする。
たとえば x=30 だったら、その直後には 5~1 を置けるので、f(5)+f(4)+f(3)+f(2)+f(1) が答えとなる。
一般化すると、f(x)=f(1)+f(2)+...+f(√x) である。
f(1)=1 からはじめて f(2),f(3),... と1つずつ求めていけば求まるのは求まるが、 X が馬鹿でかいので、平方根を取ったとしても最大 f(3×109) を求めなければならない。時間的に無理。
x を順番に書き出すと、かなり同じ値が連続することがわかる。
x 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 .. f(x) 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 5 5 ..
変曲点は、√x が変化する点、つまり x が平方数になったときにあるので、そこを中心にまとめると、
x 1 .... 4 ..... 9 ..... 16 ..... 25 ...... 36 .... 49 .. 64 .. 81 .. 100 .. f(x) 1 .. 1 2 ... 2 3 .. 3 5 ... 5 7 .... 7 9 .... 11 .. 13 .. 16 .. 19 .. acc 1 .. 3 5 .. 13 16 .. 34 39 .. 79 86 .. 156 165 ..
accは、f(x) の累積和であり、f(x)=acc(√x) となる。つまりは acc(√X) を求めたい。
とりあえず、f(x) が同じ区分ごとにまとめなおそう。
添字 i に対応する f(x) を g(i) とする。
cntはその区分の長さで、隣接する平方数の差なので要は奇数列となる。
x 1 .... 4 ..... 9 ..... 16 ..... 25 ...... 36 .... 49 .. 64 .. 81 .. 100 .. f(x) 1 .. 1 2 ... 2 3 .. 3 5 ... 5 7 .... 7 9 .... 11 .. 13 .. 16 .. 19 .. acc 1 .. 3 5 .. 13 16 .. 34 39 .. 79 86 .. 156 165 .. i (0) 1 2 3 4 5 6 7 8 9 g(i) 1 2 3 5 7 9 11 13 16 cnt 3 5 7 9 11 13 15 17 19 acc末尾 0 3 13 34 79 156 273 438 658 963
こうすると、添字 i=√x を表すことになり、
i に対して求めるべき範囲は最初から比べると 4√X まで減少する。
これなら1つずつ求めても間に合う。
g(i) を求めるとき、j=√i、端数を k とする(i=j2+k となる)と、
acc末尾で直前 j−1 までの累積和を求めて、そこから k+1 進んだ数、という感じで計算できる。
g(i),acc末尾[i] の2つを i=105 くらいまで求めておけば、クエリに対して O(1) で計算できる。
4乗根 j=√√X、端数 k=√X−j2 とすると、以下が答えとなる。
Pythonだと、制約上限から1小さい数 x=8999999999999999999
の平方根を int(x ** 0.5)
で求めると、3000000000
になってしまった。
整数から浮動小数にする段階で53bitの精度になるので、64bit型の上限付近だと狂いが生じるので注意。