裏紙

ほぼ競プロ、たまに日記

CF 733 F - Drivers Dissatisfaction

問題

Problem - F - Codeforces

問題概要

n個の町と、それらを双方向に結ぶ道がm本ある。それぞれの道に対して、ドライバーの不満度w_iがある。

この不満度を1下げるために、その道に対してコストがc_iかかる(つまり、ある道の不満度をkだけ低下させるためにはk * c_iだけかかるわけである)。そして、この不満度は0や負にもなりうる。

さて、このm本の道の中からn-1本を選んで、main roadsとすることにした。このmain roadsの選び方として、「どの町から他のどの町にも移動可能」でなければならない。

今、予算がSある。この予算を使って(使い切る必要はない)、不満度を下げてからmain roadsとしてn-1本の道を選ぶことを考える。そのときに選んだn-1本の道の合計の不満度を最小にしたい。

その最小値と、main roadとしてどの道を選んだかと、不満度を下げた後のその道の不満度を答えよ。

  •  2 \le n \le 200000
  •  n-1 \le m \le 200000
  •  1 \le w_i \le 10^9
  •  1 \le c_i \le 10^9
  •  0 \le S \le 10^9

イデア

まず、main roadsの定義からこれによって構成されるものは木であるということなのでMSTを構成したいということが分かる。そして、不満度は負でもかまわないということから、予算の使い方としてはn-1本の道が決まってしまえばその中でcが最小の道に全ての予算をかけるのが最適なのが分かる。

この考察から、予算をつぎ込む辺を全探索することを考える。そして、それで減らしきった後に毎回MSTを初めから構成しているのではO(m^2 logn)かかってしまうので間に合わない。

そこで、とりあえずcを無視し、Kruskal法を使って、wを基準にしたMSTを構成しておく。そして、予算をつぎ込む辺を全探索するにあたって、このMSTに新たに辺を1つ追加するような感じになる。すると、MSTに閉路ができるので、その閉路の中で最大のwを持つ辺を取り除ければ良いことになる。それは、新たに追加しようとしている辺がabを結ぶならそのLCAまでの間で最大のwを持つ辺を見つけられればいいことになる。それはLCAを構成するのと同じ要領で、O(logn)でその辺を見つけられる。

実装大変すぎる...こどふぉって実装重めの問題が多い気がする。LCAのいい練習になった。

実装(C++)

続きを読む

2016/12 solved(1)

12/1

往復したりなんだりでなんだかややこしそうに見えるが、結局シャトルランを続ける時間は2つの電車が出会うまでなので、その時間は簡単に求められる。その時間が求まれば総移動距離も簡単に分かる。

まず、点が与えられたら同じ座標同士にあるものを順に線分としてつないでしまってよい(polygonができるならそのような結び方しかありえない)。その際に頂点に番号を振ってどの点同士を繋いだかをメモしておく。そして、辺を辿ってN回移動した時に自分に戻って来て更に全ての頂点に訪問済みなら1つ目の条件クリア、もう1つは線分同士の交差があるかどうかをx座標方向にsetを使ってy座標管理しながら走査していくことで判定できる。

*が全ての操作列に入っていたとしてもinfected cheeseは最大でも2M個になる。いま、感染したチーズの個数がC個だったなら、この1つずつに個別に操作をすることでC回での除染が実現可能なのは明らか。問題はどのようにして*を利用するかということになる。例えば、001011は1つの操作でまとめて0*1で実現できる。このように、1回の操作で2つのチーズを一気に除染できるような頂点間に辺を張ると、それはビットの立っている個数の偶奇によって二部グラフとなる。よって、C-(最大マッチング)が答えになる。

12/2

b_i (1 \le i \le n)の式を、全てa_{i+1}の形に書き直すとa_2 = b_1 - a_1 , a_3 = a_2 - b_2 , a_4 = b_3 - a_3 , ...a_{i+1} = (-1)^i (a_i - b_i )(1 \le i \le n)の形になっていることに気づいた。つまり、a_1が決まるとこれらの式に従ってa_2以降は全て一意に決まる。そして、式の形から、a_{i+1} = s_{i+1} - a_1またはa_{i+1} = s_{i+1} + a_1のどちらかの形になる。各iについてどちらかの形になるかは、iが小さい方からシミュレーションしていれば2つおきにa_1の正負が切り替わることが分かる。そして、条件を満たすような数列aが構成できるかどうかを考えたい時にはまずs_iの絶対値は2 * 10^{18}以下じゃないといけないので、構成している途中でそれを超えてしまえばa_1が範囲に収まらないので構成不可能になる。 あとは、1 \le a_{i+1} \le 10^{18}じゃないといけないというところからa_1の上限と下限を絞り込むことが出来る。上限と下限が妥当なら、その値で構成すれば良い。

12/3

i番目のカードとj番目のカードでともにビンゴが起きてしまうような状況を考える。1つのカードに対して、ビンゴとなりうる数列は縦、横、斜めの合わせて2N+2個になる。よって、i番目のカードのx番目のビンゴ列と、j番目のカードのy番目のビンゴ列に含まれる数字の個数Sを数え、S-1で最小値更新を行っていけばよい。全体でO(M^2 N^3)

12/4

線形計画法。グラフを何個か書いてみたら答え位になりうる点が3通りに絞れたので場合分けしてその値を答えた。

ARC 064に参加

CDEの3完。Eが各頂点間に辺を張ってダイクストラするだけで良かったのに対して、Dの考察にとても時間をかけてしまった。

12/5

1/n^2の最初からN項の和と1/(n+x)^2の最初からN項の和を計算して、公式を利用してその差を足し合わせるという方法を取った(別解として書かれていた)。誤差に対する感覚がそんなになく、最初は式をいじってなんとかなるかと思ってて、とても悩んだ。

imulan.hatenablog.jp

12/6

2つの星の位置を見つけて、それによって場合分けして解ける。2つの星のx座標が同じなら加える星のx座標をずらし、y座標が同じならy座標をずらす。それに当てはまらない時はどちらかの星とx座標を同じにしてy座標を違う位置にすれば必ず三角形を構成できる。

板を縦に敷く場合と横に敷く場合で板の形をそれぞれ割り出し、その番号が対応するような二部グラフをつくると、必要な板はその最小点カバーで求められるので、最大マッチングを求めれば良い。

12/7

N=a*b*cとなるaとbを全探索できる。それで最小値を更新していけば良い。

メモ化再帰で解いた。

12/8

二分探索で出来るのは明らかに分かるが、普通に二分法をやるとTLEする。まず、a=0 ,b=0の時は簡単なので別に処理しておき、それ以外を考える。自分はf(x) = x^a (logx)^b - tとおいて、f(x)=0を解くニュートン法で解いた。ニュートン法にはf'(x)が必要になるが、簡単に求められる。また、ニュートン法は初期値によって収束速度が変わるので、各(a,b)についてt=10の時の値を初期値として選んだ。

それぞれの括弧の組について、顔文字が作れるかをO(1)で判定していく全探索を書いた。判定方法は、まず括弧に一番近い*を選ぶのが最適なので、各位置について最も近い*の位置を保存しておき、^の個数を累積和で取って、その範囲に2個以上あればOKという判定方法で実現した。

優先度付きキューを使って、個数の多い方から貪欲に取っていく。

12/9

小さい素数から到達可能な数に最大個数をdpで更新していく。

中心を何段のピラミッドにするかで全探索する。

勝敗が決定していないところを全探索して順位を計算して更新する。

二部マッチングで解いた。

それぞれ、プラスとマイナスをソートしてもっておいて、2つのindexをもって尺取り的に貪欲に決めていける。

桁dpで求められる。

最短でもいけないときは無理。そうでないときは、偶奇に合わせて1つムダな動きを入れたりして、目的地に行ってから左右に往復させた。原点のときは、t=1だと無理なのに注意する。

フェルマーの小定理を使って、N^M = (N \% p)^{M \% (p-1)}とできる。

12/10

クエリを先読みして、左にあるやつから貪欲に処理していけばいい。必要最低限の個数を計算して、もし1個も無かったらまだ残ってるものの中で1番左のものを選んでおけば大丈夫。

半分全列挙して、そのときにペアを用意してvectorも保存しておいた。

dp[i][j] = x_iまで決めたときにf(X)=jのときのx_1~x_iまでの和の最小値を更新していく。

母音が6つ、子音が5つある。まず、子音の直後には必ず母音が来なければいけないので、母音をx、子音をyとするとxyxyxyxyxyとなる。そして、余った1つの母音が入りうる位置はそれぞれの子音の1つ前と最後の6通りあり得る。よって、列挙される文字列の個数は5! * 5! * 6 * 6 = 518400通りになる(実際にはaやuがダブってるのでこんなに多くはないが)。与えられたn個の文字列をsetに入れておいて、その都度チェックすれば間に合う。

事前にクリアすべきステージからそのステージへの有向辺を張っておいて、強連結成分分解をすると、そのトポロジカル順序にステージをクリアしていけば良いことになる。強連結成分の中で一番最初にやるべきなものは、難易度が一番低いものを選んでおけば良い(submission)。

12/11

まず、各マスを2回以上反転させるのはムダなので、各マスともに反転させるのは0回か1回だけになる。1行目と1列目を反転させるかどうかを全探索する(2^{N+M-1}通り)。さて、そうすると2行目,2列目から順に左上のマスの状況からそのマスを反転させるべきかを貪欲に決定していくことが出来る。そして、全部が0にできた時には反転回数の最小値を更新していけば良い。

12/12

3つの辺にそれぞれ平行な辺を選んで三角形を作れるか判定していくのでは、計算が間に合わない。そこで、2つに対して辺を全探索して、のこりの1辺に関しては作れる辺の範囲を二分探索出来る。

12/13

ビットは立っている個数の方向に増えていくので、N+1個の列はビットの立っている個数が0,1,2,..,N+1となる。まず同じぶんだけビットの立ってるやつが複数あるとそれらはどちらかしか経由できないのでムリ。そして、立っている個数順でソートしておくと、その順番に遷移させていくことになるが、前の時点で立っているビットが次に遷移したときに立っていないのも不可能なのでそういうのもムリになる。それ以外は、その遷移間でビットの立て方の順番だけあり得るので階乗をかけ合わせていく。

imulan.hatenablog.jp

まず、重さ順でソートしておく。

それから、i番目の友達は選ばないかつそれ未満の友達は全部連れて行くときにi+1番目以降の友達の選び方が何通りあるかをdpで計算すると、そのときにあり得るのはW-w[i]+1 ~ Wの間に収まっている組み合わせしか選べないことになる。

12/14

dp[i][j] = i番目のうさぎが位置jにいる組み合わせでDP。

各授業時間にそれぞれ何人ずつ生徒と教師が入れるのかをチェックして、どちらか最小の方を足し合わせていけば良い。

頂点数は多いが、郵便物の個数kがとても少ない。スタート地点も合わせて、たかだか13回のダイクストラを回して、それぞれの頂点からの最短経路を計算しておく。あとは、bitDPでどの順に回っていくのが最適かを考える巡回セールスマン問題的なものに変わる。

12/15

imulan.hatenablog.jp

先頭を反転するかしないかを決めると、その後をどうするかを貪欲に決めていくことが出来る。

平均値最大化の二分探索。

テストの点でソートしておき、中央値をどこにするかを全探索する。中央値を決めると、それより大きいところからN/2個、小さいところからN/2個選ばなければいけない。つまり、その範囲でコストが小さい方からN/2個を選び取りたい。それを大きい方は個数が増加していくので大きいのを取り出して注目している値と比較して更新していくpriority_queueで、もう片方は要素数が減っていくので、個数を保存するBITと二分探索で実現した。

12/16

i文字目からj文字目までの部分文字列が回文になっているかを事前に判定しておいて、P1とP3を全探索し、そのときのP2とAとしてあり得るものを累積和を利用してO(1)で計算する。

3種類(C<A かつ C<B, C==A かつ C==B, C==A または C==B)に分けて構築した。

左上の座標、右上の座標を引数にして切り分け方を全部試していくメモ化再帰で解いた。O(h^2 w^2 (h+w))