CF 733 F - Drivers Dissatisfaction
問題
問題概要
個の町と、それらを双方向に結ぶ道が本ある。それぞれの道に対して、ドライバーの不満度がある。
この不満度を下げるために、その道に対してコストがかかる(つまり、ある道の不満度をだけ低下させるためにはだけかかるわけである)。そして、この不満度は0や負にもなりうる。
さて、この本の道の中から本を選んで、main roads
とすることにした。このmain roads
の選び方として、「どの町から他のどの町にも移動可能」でなければならない。
今、予算がある。この予算を使って(使い切る必要はない)、不満度を下げてからmain roads
として本の道を選ぶことを考える。そのときに選んだ本の道の合計の不満度を最小にしたい。
その最小値と、main road
としてどの道を選んだかと、不満度を下げた後のその道の不満度を答えよ。
アイデア
まず、main roads
の定義からこれによって構成されるものは木であるということなのでMSTを構成したいということが分かる。そして、不満度は負でもかまわないということから、予算の使い方としては本の道が決まってしまえばその中でが最小の道に全ての予算をかけるのが最適なのが分かる。
この考察から、予算をつぎ込む辺を全探索することを考える。そして、それで減らしきった後に毎回MSTを初めから構成しているのではかかってしまうので間に合わない。
そこで、とりあえずを無視し、Kruskal法を使って、を基準にしたMSTを構成しておく。そして、予算をつぎ込む辺を全探索するにあたって、このMSTに新たに辺を1つ追加するような感じになる。すると、MSTに閉路ができるので、その閉路の中で最大のを持つ辺を取り除ければ良いことになる。それは、新たに追加しようとしている辺がとを結ぶならそのLCAまでの間で最大のを持つ辺を見つけられればいいことになる。それはLCAを構成するのと同じ要領で、でその辺を見つけられる。
実装大変すぎる...こどふぉって実装重めの問題が多い気がする。LCAのいい練習になった。
実装(C++)
続きを読む2016/12 solved(1)
12/1
往復したりなんだりでなんだかややこしそうに見えるが、結局シャトルランを続ける時間は2つの電車が出会うまでなので、その時間は簡単に求められる。その時間が求まれば総移動距離も簡単に分かる。
まず、点が与えられたら同じ座標同士にあるものを順に線分としてつないでしまってよい(polygonができるならそのような結び方しかありえない)。その際に頂点に番号を振ってどの点同士を繋いだかをメモしておく。そして、辺を辿ってN回移動した時に自分に戻って来て更に全ての頂点に訪問済みなら1つ目の条件クリア、もう1つは線分同士の交差があるかどうかをx座標方向にsetを使ってy座標管理しながら走査していくことで判定できる。
*
が全ての操作列に入っていたとしてもinfected cheeseは最大でも個になる。いま、感染したチーズの個数が個だったなら、この1つずつに個別に操作をすることで回での除染が実現可能なのは明らか。問題はどのようにして*
を利用するかということになる。例えば、001
と011
は1つの操作でまとめて0*1
で実現できる。このように、1回の操作で2つのチーズを一気に除染できるような頂点間に辺を張ると、それはビットの立っている個数の偶奇によって二部グラフとなる。よって、C-(最大マッチング)
が答えになる。
12/2
の式を、全ての形に書き直すととの形になっていることに気づいた。つまり、が決まるとこれらの式に従って以降は全て一意に決まる。そして、式の形から、またはのどちらかの形になる。各についてどちらかの形になるかは、が小さい方からシミュレーションしていれば2つおきにの正負が切り替わることが分かる。そして、条件を満たすような数列が構成できるかどうかを考えたい時にはまずの絶対値は以下じゃないといけないので、構成している途中でそれを超えてしまえばが範囲に収まらないので構成不可能になる。 あとは、じゃないといけないというところからの上限と下限を絞り込むことが出来る。上限と下限が妥当なら、その値で構成すれば良い。
12/3
番目のカードと番目のカードでともにビンゴが起きてしまうような状況を考える。1つのカードに対して、ビンゴとなりうる数列は縦、横、斜めの合わせて個になる。よって、番目のカードの番目のビンゴ列と、番目のカードの番目のビンゴ列に含まれる数字の個数を数え、で最小値更新を行っていけばよい。全体で。
12/4
線形計画法。グラフを何個か書いてみたら答え位になりうる点が3通りに絞れたので場合分けしてその値を答えた。
ARC 064に参加
CDEの3完。Eが各頂点間に辺を張ってダイクストラするだけで良かったのに対して、Dの考察にとても時間をかけてしまった。
12/5
の最初から項の和との最初から項の和を計算して、公式を利用してその差を足し合わせるという方法を取った(別解として書かれていた)。誤差に対する感覚がそんなになく、最初は式をいじってなんとかなるかと思ってて、とても悩んだ。
12/6
2つの星の位置を見つけて、それによって場合分けして解ける。2つの星のx座標が同じなら加える星のx座標をずらし、y座標が同じならy座標をずらす。それに当てはまらない時はどちらかの星とx座標を同じにしてy座標を違う位置にすれば必ず三角形を構成できる。
板を縦に敷く場合と横に敷く場合で板の形をそれぞれ割り出し、その番号が対応するような二部グラフをつくると、必要な板はその最小点カバーで求められるので、最大マッチングを求めれば良い。
12/7
N=a*b*cとなるaとbを全探索できる。それで最小値を更新していけば良い。
メモ化再帰で解いた。
12/8
二分探索で出来るのは明らかに分かるが、普通に二分法をやるとTLEする。まず、の時は簡単なので別に処理しておき、それ以外を考える。自分はとおいて、を解くニュートン法で解いた。ニュートン法にはが必要になるが、簡単に求められる。また、ニュートン法は初期値によって収束速度が変わるので、各についての時の値を初期値として選んだ。
それぞれの括弧の組について、顔文字が作れるかをで判定していく全探索を書いた。判定方法は、まず括弧に一番近い*を選ぶのが最適なので、各位置について最も近い*の位置を保存しておき、^の個数を累積和で取って、その範囲に2個以上あればOKという判定方法で実現した。
優先度付きキューを使って、個数の多い方から貪欲に取っていく。
12/9
小さい素数から到達可能な数に最大個数をdpで更新していく。
中心を何段のピラミッドにするかで全探索する。
勝敗が決定していないところを全探索して順位を計算して更新する。
二部マッチングで解いた。
それぞれ、プラスとマイナスをソートしてもっておいて、2つのindexをもって尺取り的に貪欲に決めていける。
桁dpで求められる。
最短でもいけないときは無理。そうでないときは、偶奇に合わせて1つムダな動きを入れたりして、目的地に行ってから左右に往復させた。原点のときは、t=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行目,2列目から順に左上のマスの状況からそのマスを反転させるべきかを貪欲に決定していくことが出来る。そして、全部が0にできた時には反転回数の最小値を更新していけば良い。
12/12
3つの辺にそれぞれ平行な辺を選んで三角形を作れるか判定していくのでは、計算が間に合わない。そこで、2つに対して辺を全探索して、のこりの1辺に関しては作れる辺の範囲を二分探索出来る。
12/13
ビットは立っている個数の方向に増えていくので、N+1個の列はビットの立っている個数が0,1,2,..,N+1となる。まず同じぶんだけビットの立ってるやつが複数あるとそれらはどちらかしか経由できないのでムリ。そして、立っている個数順でソートしておくと、その順番に遷移させていくことになるが、前の時点で立っているビットが次に遷移したときに立っていないのも不可能なのでそういうのもムリになる。それ以外は、その遷移間でビットの立て方の順番だけあり得るので階乗をかけ合わせていく。
まず、重さ順でソートしておく。
それから、i番目の友達は選ばないかつそれ未満の友達は全部連れて行くときにi+1番目以降の友達の選び方が何通りあるかをdpで計算すると、そのときにあり得るのはW-w[i]+1 ~ Wの間に収まっている組み合わせしか選べないことになる。
12/14
dp[i][j] = i番目のうさぎが位置jにいる組み合わせ
でDP。
各授業時間にそれぞれ何人ずつ生徒と教師が入れるのかをチェックして、どちらか最小の方を足し合わせていけば良い。
頂点数は多いが、郵便物の個数kがとても少ない。スタート地点も合わせて、たかだか13回のダイクストラを回して、それぞれの頂点からの最短経路を計算しておく。あとは、bitDPでどの順に回っていくのが最適かを考える巡回セールスマン問題的なものに変わる。
12/15
先頭を反転するかしないかを決めると、その後をどうするかを貪欲に決めていくことが出来る。
平均値最大化の二分探索。
テストの点でソートしておき、中央値をどこにするかを全探索する。中央値を決めると、それより大きいところからN/2個、小さいところからN/2個選ばなければいけない。つまり、その範囲でコストが小さい方からN/2個を選び取りたい。それを大きい方は個数が増加していくので大きいのを取り出して注目している値と比較して更新していくpriority_queueで、もう片方は要素数が減っていくので、個数を保存するBITと二分探索で実現した。
12/16
i文字目からj文字目までの部分文字列が回文になっているかを事前に判定しておいて、P1とP3を全探索し、そのときのP2とAとしてあり得るものを累積和を利用してで計算する。
3種類(C<A かつ C<B, C==A かつ C==B, C==A または C==B)に分けて構築した。
左上の座標、右上の座標を引数にして切り分け方を全部試していくメモ化再帰で解いた。。