読者です 読者をやめる 読者になる 読者になる

裏紙

ほぼ競プロ、たまに日記

CF 701 F - Break Up

Codeforces programming

問題

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

Codeforces programming

問題

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++)

続きを読む

ARC 068 E - Snuke Line

AtCoder programming

問題

E: Snuke Line - AtCoder Regular Contest 068 | AtCoder

問題概要

M+1個の駅があり、駅に対して0からMまでの番号が振られている。列車は駅0からd駅ごとに停車する。また、N種類の名産品があり、i番目の名産品は駅l_iから駅r_i区間で売られており、その駅に停まると名産品が買える。d=1,2,3, \ldots ,Mの時に買える名産品の個数をそれぞれ求めよ。

  • 1 \le N \le 300000
  • 1 \le M \le 100000
  • 1 \le l_i \le r_i \le M

イデア

まず間隔dを固定して考えてみる。すると、区間の幅(r_i - l_i +1)がdよりも大きい時は、その区間のどこかしらに必ず訪れることになるので、その名産品を買える。一方で、幅がd以下の時はたかだか1回しか訪れることができないのが分かる。

ここで、幅がdより大きい区間については必ず買えるので無視して、幅d以下の区間についてのみ考えると、この区間についてはたかだか1回しか訪れないことがわかっているから区間の累積和を使ってはじめにその位置に含まれる区間の個数を計算してから、dの倍数の位置を調べていけばよいことになる。これでO(N+M)で実現できる。

問題は、d1からMまで動くので、このままでは間に合わない。ただ、幅d以下の区間dを増加させるごとにその数は単調増加になっているので、1からはじめて、上で行った処理をBIT上で行うことで高速に処理することが出来る。

実装(C++)

続きを読む