CF 701 E - Connecting Universities
問題
問題概要
頂点数の木があり、頂点には
から
の番号が振られている(グラフの情報は、各辺がどの頂点を繋いでいるかが与えられる)。このうち、
個の頂点番号が指定される。それらを
とする。これら
個の頂点から、
個のペアを作る。そのペアの木における距離の総和を最大化するようにペアを作った時、その総和の値を求めよ。
アイデア
頂点を根として考える。すると、DFSによって次の値を各頂点に対して求めることが出来る：
: 頂点iを根とした部分木以下にある指定されている頂点の個数(自分も含む)
最適なペアを取ることの出来る状況を考えてみる。
そこで、頂点とその親の間にある辺を考えてみると、その辺は
個のペアのパス上にあることになると言える。これはなぜかというと、まず、これ以上のペアのパス上になることは、この辺を挟んだ位置にあるそれぞれの頂点の個数を考えてみると、物理的に有り得ない。逆にこれ未満である状況を考えると、
を根とする部分木の中にある頂点同士
と
がペアになっており、その部分木には含まれない頂点同士
と
がペアになっているということになる。そして、木の性質上、このペアを
と
、
と
に変えることで
から
へのパス上の辺と
から
へのパス上の辺を全てカバーでき、かつパスを長くすることが出来る組み合わせなのでこのような組み合わせは最適ではないことが分かり、上記のことは正しいということが分かった。
ということで、結論はということになる。
そのようなマッチングを求めることもそんなに改変しなくてもできるよって書いてあるけど、パッとは思いつけない…
実装(C++)
続きを読むARC 068 E - Snuke Line
問題
E: Snuke Line - AtCoder Regular Contest 068 | AtCoder
問題概要
個の駅があり、駅に対して
から
までの番号が振られている。列車は駅
から
駅ごとに停車する。また、
種類の名産品があり、
番目の名産品は駅
から駅
の区間で売られており、その駅に停まると名産品が買える。
の時に買える名産品の個数をそれぞれ求めよ。
アイデア
まず間隔を固定して考えてみる。すると、区間の幅(
)が
よりも大きい時は、その区間のどこかしらに必ず訪れることになるので、その名産品を買える。一方で、幅が
以下の時はたかだか1回しか訪れることができないのが分かる。
ここで、幅がより大きい区間については必ず買えるので無視して、幅
以下の区間についてのみ考えると、この区間についてはたかだか1回しか訪れないことがわかっているから区間の累積和を使ってはじめにその位置に含まれる区間の個数を計算してから、
の倍数の位置を調べていけばよいことになる。これで
で実現できる。
問題は、が
から
まで動くので、このままでは間に合わない。ただ、幅
以下の区間は
を増加させるごとにその数は単調増加になっているので、
からはじめて、上で行った処理をBIT上で行うことで高速に処理することが出来る。
