AtCoder Beginner Contest 243 E,F,G問題メモ
4完だった。ぐぬぬ。
E - Edge Deletion
問題
- N 頂点 M 辺の重み付き単純無向連結グラフが与えられる
- Ai,Bi,Ci: Ai と Bi を相互に結ぶ辺の重みは Ci
- 「削除してもどの2頂点の最短距離も変化しない」辺を最大何本削除できるか、求めよ
- 2≤N≤300
解法
各辺につき、迂回路があるかどうか、という問題。
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)) を求めればよい。
疑問とその解消
①-②の辺は、①-③、③-②が残るなら確かに不要そうだけど、これらの辺も削除されちゃうかもしれないし、 全体的にはやっぱり①-②は必要だった、ということにはならないの?
ならない。
この方針に従う限り、たとえば①-③の辺が削除できるなら、
①-③間をそれ以下のコストで代替できる迂回路が存在するので、①-②の迂回路の一部としてもそっちを使えばよい。
きちんとした証明としては、公式解説の通り、
- その1本だけの削除であっても、削除したら絶対に最短距離が変わる頂点がある辺、という条件を整理する
- その辺以外を全て削除すると考える(答えの上界)
- 削除後のグラフで、最短距離が変化していない(上界が達成できる)ことを、削除条件などから証明する
F - Lottery
問題
- N 種類の景品が当たるくじがある
- 当選の重み W1,W2,...,WN が決まっており、k 番目の景品の抽選率は WkWiの総和
- くじを K 回引いたとき(抽選率は毎回独立)、ちょうど M 種類の景品を得る確率を 998244353 の有理数modで求めよ
- 1≤M≤N≤50
- 1≤K≤50
- 1≤Wi<998244353、Wi の総和もmodの値未満
解法
ちょうど 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 乗の総和)を求めたい。
f(m) の求め方
DPで、Wi を順番に加えていくことを考える。
- DP[i][m][k]=Wi までを考慮し、そのうち m 個の要素からなる全選び方に対し、Pkmj の総和
f(M)=DP[N][M][K] である。
DP[i−1][m][k]=Pkm1+Pkm2+... が求まっているとして、ここに新たに Wi を加えた選び方を考慮する。
- DP[i][m+1][k]+=(Pm1+Wi)k+(Pm2+Wi)k+...
これを展開整理すると、(長くなるので、DP[i−1][m][k]=dk とおくと)
- DP[i][m+1][k]+=dk+kC1dk−1Wi+kC2dk−2W2i+...+kCk−1d1Wk−1i+Wki
なので、これまでに求めた成果から、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} などの M−1 個の選び方は、M1 と M2 で2回分
- {1,2} などの M−2 個の選び方は3回分
- {1} のような M−3 個の選び方は4回分
このように「余分な状態が、しかも重複して」数えられている。
ただし、それぞれいくつ重複しているかは、集合のサイズごとに固定 ({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) で計算可能。
G - Sqrt
問題
- はじめ、1項だけの整数列 A=[X] がある
- A の末尾の項を x として、1~floor(√x) の整数を好きに選び追加することを 10100 回繰り返す
- 最終的にできうる整数列は何通りあるか求めよ
- T ケース与えられるので、それぞれについて求めよ
- 1≤T≤20
- 1≤X≤9×1018
解法
繰返し回数がとんでもない数だが、末尾が 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) を求めたい。
-
- accはこの数列になるが、一般項を求める式はさすがに無さそう
とりあえず、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 となる)と、
- g(i)=acc末尾[j−1]+(k+1)g(j)
- acc末尾[i]=acc末尾[i−1]+g(i)cnt[i]
acc末尾で直前 j−1 までの累積和を求めて、そこから k+1 進んだ数、という感じで計算できる。
g(i),acc末尾[i] の2つを i=105 くらいまで求めておけば、クエリに対して O(1) で計算できる。
4乗根 j=√√X、端数 k=√X−j2 とすると、以下が答えとなる。
- acc末尾[j−1]+(k+1)g(j)
Pythonだと、制約上限から1小さい数 x=8999999999999999999
の平方根を int(x ** 0.5)
で求めると、3000000000
になってしまった。
整数から浮動小数にする段階で53bitの精度になるので、64bit型の上限付近だと狂いが生じるので注意。