Processing math: 100%

目次

AtCoder Beginner Contest 243 E,F,G問題メモ

AtCoder Beginner Contest 243

4完だった。ぐぬぬ。

E - Edge Deletion

E - Edge Deletion

問題

解法

各辺につき、迂回路があるかどうか、という問題。

    5       ①-②を結ぶ重み5の辺があるが、
①----②    その他の辺を使って①→②に距離5でたどり着けるので、
2\  /3    この辺は不要
   ③

なので、「必ず2本以上の辺を使う場合の全頂点間最短距離 Dist(u,v)」を計算してやって、
各辺につき、Dist(Ai,Bi)Ci なら、その辺は不要と判断できる。

Dist(u,v) は、普通にFloyd-Warshallで(1本の辺だけでもよい)全頂点最短距離 d(u,v) を求めた後、
必要な (u,v) について、minwu,v(d(u,w)+d(w,v)) を求めればよい。

疑問とその解消

①-②の辺は、①-③、③-②が残るなら確かに不要そうだけど、これらの辺も削除されちゃうかもしれないし、 全体的にはやっぱり①-②は必要だった、ということにはならないの?

ならない。
この方針に従う限り、たとえば①-③の辺が削除できるなら、 ①-③間をそれ以下のコストで代替できる迂回路が存在するので、①-②の迂回路の一部としてもそっちを使えばよい。

きちんとした証明としては、公式解説の通り、

Python3

F - Lottery

F - Lottery

問題

解法

ちょうど M 種類、というのはややこしくても、M 種類以下、というのはまだ求めやすい。

これをまず求めて、そこから包除原理かなんかでちょうどでないものを除く、 というのがよくある解法なので、この問題もそれで考える。

Wi の総和を S=Ni=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(つまり、全 PmjK 乗の総和)を求めたい。

f(m) の求め方

DPで、Wi を順番に加えていくことを考える。

f(M)=DP[N][M][K] である。

DP[i1][m][k]=Pkm1+Pkm2+... が求まっているとして、ここに新たに Wi を加えた選び方を考慮する。

これを展開整理すると、(長くなるので、DP[i1][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} も重複している個数は一緒)なので、まとめて除くことが可能である。

Mi 種類しか選ばれない状態が f(M) において重複している回数は、 残りの i 種類を、選ばれていない N(Mi) 個から選ぶ N(Mi)Ci である。

よって、i=1M1 に対し、f(M)=N(Mi)Cig(Mi) をすればよい。最終的に残るのが g(M) である。

途中に出てくる g(m) については、m が小さい方から順に求めていけばよい。O(M2) で計算可能。

Python3

G - Sqrt

G - Sqrt

問題

解法

繰返し回数がとんでもない数だが、末尾が 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 に対して求めるべき範囲は最初から比べると 4X まで減少する。
これなら1つずつ求めても間に合う。

g(i) を求めるとき、j=i、端数を k とする(i=j2+k となる)と、

acc末尾で直前 j1 までの累積和を求めて、そこから k+1 進んだ数、という感じで計算できる。

g(i),acc[i] の2つを i=105 くらいまで求めておけば、クエリに対して O(1) で計算できる。

4乗根 j=X、端数 k=Xj2 とすると、以下が答えとなる。

Pythonだと、制約上限から1小さい数 x=8999999999999999999 の平方根を int(x ** 0.5) で求めると、3000000000 になってしまった。 整数から浮動小数にする段階で53bitの精度になるので、64bit型の上限付近だと狂いが生じるので注意。

Python3