裏紙

ほぼ競プロ、たまに日記

SRM 643 Div1 Easy - TheKingsFactorization

問題

TopCoder Statistics - Problem Statement

問題概要

自然数N素因数分解を求めよ。ただし、Nの素因数の小さい方から順に奇数番目だけ素因数が何であるかのヒントが与えられる。

例えば、N=60であるとき、素因数分解60 = 2 * 2 * 3 * 5であるから、小さい方から数えて奇数番目の2 , 3がヒントとして与えられる。

  •  2 \le N \le 10^{18}

イデア

普通に素因数分解するのでは、O(\sqrt{N})かかってしまうので、間に合わない。そこで、ヒントを利用する。

まず、ヒントとして与えられる素因数の個数で、全体の素因数が何個あるかの見当を付けることが出来る。例えば、ヒントが2個なら、答えには3個か4個の素因数があるはずである。

ヒントの個数が1個なら、答えに含まれる素因数の個数は1個か2個ということになる。これはヒントをみればどちらになるか簡単に判断できて、その1個がNと一致するなら素因数は1個で、そうでないならNをそのヒントで割った値も素因数になっていることが確定する。

以下、ヒントの個数が2個以上である状況を考える。まず、Nを既にわかっている素因数で割っておく。

まず、素因数分解の素朴な方法として、最初に述べた計算量からも推測がつく通りNに対する素因数分解2から\sqrt{N}までのそれぞれで割れるかどうかを試すという方法がある。それぞれの数で順番にNを割っていき、終わった時点でNが1よりも大きければその数も(\sqrt{N}より大きい)素因数であるといえる。

これだけだと間に合わないが、ここでヒントを利用する。ヒントの中で一番大きい数pに注目する。すると、ヒントの与えられ方の性質から、p以上の素因数は多くとも1つしかないことが分かる。よって、Nを試し割りするのはこのp以下で十分である事がわかる。

pがとても大きい数だったらこの制約は意味がないじゃないかと思うかもしれないが、直感的にはpが大きいような状況では、既にNpで割られているので\sqrt{N}が十分小さくなるというイメージで計算が間に合う。

最悪の状況を考えてみると、実際に素因数が3個である状況を考え、与えられるヒントが2とpだったとする。この時に、2つの制約\sqrt{N}pがちょうど拮抗する状況を考えても、N \le 10^{18}であるから試し割りの範囲は最悪でも10^6くらいに収まることが分かる。

とても面白い問題だった。

実装(C++)

続きを読む

CF 701 F - Break Up

問題

Problem - F - Codeforces

問題概要

n頂点m辺の無向グラフがある。グラフが連結である保証はない。

いま、ある辺を削除して頂点sから頂点tへの移動をできなくなるようにすることを考える。しかし、辺の削除の上限は2本である。辺にはそれぞれ削除のコストがついている(w_iとする)ので、削除のコストが最小になるように削除した時の、そのコストと、その時に削除する辺はどれになるかを答えよ。ただし、不可能な場合には-1とだけ答えよ。

  •  2 \le n \le 1000
  •  0 \le m \le 30000
  •  1 \le w_i \le 10^9

イデア

まず、もとのグラフでstがもともと繋がっていなければ答えは0になる。以下、つながっている場合を考える。

もし、1つの辺の削除によってstを連結でなくすることが可能なら、その辺はsからtへのあらゆるパスに含まれることになる。よって、二重辺連結成分分解によって橋をみつけて、sからtへのある1つのパス上を眺めてそのパス上にある橋のコストをみていけば良い。

2つの辺を削除してstの連結を切ることを考えるとき、削除する辺のうちの1つは見つかった1つのパス上になければならない(でないとそのパスを使うことが出来るから)。パス上のある辺eを削除したと考えると、この1つの辺を削除したグラフに対して橋を見つけて、あるパス上の橋を削除すべきということになる。

このいずれでも不可能な時は-1と答えることになる。

実装(C++)

続きを読む

CF 701 E - Connecting Universities

問題

Problem - E - Codeforces

問題概要

頂点数nの木があり、頂点には1からnの番号が振られている(グラフの情報は、各辺がどの頂点を繋いでいるかが与えられる)。このうち、2k個の頂点番号が指定される。それらをu_1 , u_2 , \cdots , u_{2k}とする。これら2k個の頂点から、k個のペアを作る。そのペアの木における距離の総和を最大化するようにペアを作った時、その総和の値を求めよ。

  •  2 \le n \le 200000
  •  1 \le k \le n/2
  •  1 \le u_i \le n

イデア

頂点1を根として考える。すると、DFSによって次の値を各頂点に対して求めることが出来る:

  •  s_i : 頂点iを根とした部分木以下にある指定されている頂点の個数(自分も含む)

最適なペアを取ることの出来る状況を考えてみる。

そこで、頂点vとその親の間にある辺を考えてみると、その辺は min(s_v , 2k - s_v)個のペアのパス上にあることになると言える。これはなぜかというと、まず、これ以上のペアのパス上になることは、この辺を挟んだ位置にあるそれぞれの頂点の個数を考えてみると、物理的に有り得ない。逆にこれ未満である状況を考えると、vを根とする部分木の中にある頂点同士abがペアになっており、その部分木には含まれない頂点同士cdがペアになっているということになる。そして、木の性質上、このペアをacbdに変えることでaからbへのパス上の辺とcからdへのパス上の辺を全てカバーでき、かつパスを長くすることが出来る組み合わせなのでこのような組み合わせは最適ではないことが分かり、上記のことは正しいということが分かった。

ということで、結論は\sum_{i=1}^{n} min(s_i , 2k-s_i )ということになる。

そのようなマッチングを求めることもそんなに改変しなくてもできるよって書いてあるけど、パッとは思いつけない…

実装(C++)

続きを読む