裏紙

ほぼ競プロ、たまに日記

CS Academy #40 - Direct the Graph

問題

CS Academy

問題概要

頂点数nの完全グラフの各辺に対して向きを付ける(トーナメント)。この時、経路長が3である閉路の個数が最大になるように向きを付け、その向きの付け方と、その結果経路長が3である閉路はいくつになるか答えよ。

  •  3 \le n \le 2000

イデア

まず、問題に答える前に、あるトーナメントに対して、経路長3の閉路の個数を数え上げるにはどうすればいいだろうか(コンテスト時間中は、ある辺に対して、他のある頂点と閉路をなすかチェックするO(n^3)しか思いつかなかった)。

逆に満たしていないものの個数を数えて、全体から引くことを考えてみる。全体で\binom{n}{3}通りの3点を選ぶ方法があり、その3点の間にある有向辺が閉路をなしていないもののの個数を数える。すると、閉路をなさない形は下の図のようなパターンのみに帰着する。

f:id:imulan:20170803043532p:plain

それぞれの頂点の(入次数,出次数)に注目すると、それぞれ(0,2)(1,1)(2,0)となっている。

数え上げのためには、このどちらも出ている頂点とどちらも入ってくる部分に注目して、頂点vの入次数をin(v)、出次数をout(v)と表すと、数え上げの重複を考慮して、経路長が3である閉路の個数は

 \displaystyle \binom{n}{3}  - \frac{\sum_{v} \binom{in(v)}{2} + \binom{out(v)}{2} }{2}

となる。

本題に戻ると、この閉路の個数を最大化したい。各頂点に対する辺の個数の制約によって、in(v) + out(v) = n-1であるから、これを最大化するにはin(v)out(v)はできるだけ等しい値にすると良い。そのようなグラフは、各vに対してちょうど半分(またはxx+1)になるように辺の向きを割り当てるのが良い。(実は01を交互に出力をすると今回の出力形式だとそれが実現できる(隣接行列の上三角部分を出すので))。

inとoutが各頂点に均等に分かれるようにすれば良さそうってのは何となくあったけど数え上げができなかった…

実装(C++)

続きを読む

CS Academy #38 - Tree Antichain (Hard)

問題

CS Academy

問題概要

頂点数nの木が与えられる。長さnの順列aを考え、それを頂点に対応させる時、a_ia_{i+1} (1 \le i \le n-1)の間にいずれも辺がないような順列の中で辞書順最小のものを求めよ。

  • テストケース数T : 1 \le T \le 10^4
  •  2 \le n \le 10^5
  • テストケース全体でのnの和は10^5を超えない

イデア

同じラウンドに(Easy)というのも存在していたが、そちらは辞書順最小という条件がはずれたもの。このときはグラフがスターでなければ構成可能。適当に根を決めて根からの距離の偶奇で二部グラフになるので、偶数側を並べて奇数側をならべればよい(変わり目だけは辺がないように気をつける)。

この中でも辞書順最小のものが知りたい、と言う話になってくる。グラフがスターだと構成できないという話があったが、これをもう少し広げると、ある順列a_1 , a_2 , \ldots , a_nという順列を考えたときに、前から順番にa_1の頂点から順に削除をしていくという操作を考えると、この操作の過程で、一度もグラフがスターになることがなければこの順列はvalidなものであるということが言える。以下でこれを確認する:

まず、木を二部グラフと見なす(適当な根からの頂点の偶奇とかで簡単に色分けできる)。黒と白に色分けすることにしよう。

上で書いていたことを少し言い換えて、今、a_1 , a_2, \ldots , a_kという順列があるような状況を考える。このk個の頂点を取り除いたグラフがスターになっていなければその順列はそれ以降、n番目まで妥当なものを構築できることを示す。

今、a_kの頂点は白、つまり a_kと接続している頂点は全部黒であるとする。残っているグラフが非連結ならば、a_k以降は白い頂点を全部並べて、その後に黒い頂点を並べればそれは問題なく構築できる。もし、残っているグラフが連結ならば(スターではない)、白い頂点を全部並べて、その後に黒い頂点を並べるのだが、白から黒への切り替わるタイミングで辺があるような2頂点を選ばないように気をつければ良い(そしてスターでなければこのようなペアは必ずある)(証明終)。

この事実が正しいということがわかると、このn個の順列は前から順番に決定していくことができるようになる。

i番目の頂点をどれにするかを決める段階を考えると、まだ使われていない頂点をsetで管理しながら、頂点番号が小さい順に追加してよいかをチェックしていく。チェックすべきことは、a_{i-1}と接続していないこと、もしその頂点を選んだ後に残るグラフがスターになっていないこと(これは、残っている頂点の次数をmultisetで管理することでチェックできる)の2つになる。

これをチェックしながら貪欲にやっていくことで構築できる。コードを書いてみるとO(n^2)になっているように見えるがそうではない。失敗するパターンとしては、隣接してるときとスターになってしまう時がありえるが、まず隣接していて失敗するというのは全部を構築する過程でO(n)回しか起こらない。またスターになって失敗する状況というのは、グラフから1点を取り除くとスターになるようなグラフについて、そのような取り除くと残るグラフがスターになるような頂点はi番目のステップにおいてたかだか2点しかないということを考えると、setなどの操作を考慮して全体でO(n \log n)で処理ができる。

実装(C++)

続きを読む

CF 765 F - Souvenirs

問題

Problem - F - Codeforces

問題概要

長さnの数列aが与えられる。

l_ir_iが与えられ、 |a_s - a_t | (l_i \le s \lt t \le r_i) の最小値 を答えよというクエリがm個与えられるので、それらに答えよ。

  •  2 \le n \le 100000
  •  0 \le a_i \le 10^9
  •  1 \le m \le 300000
  •  1 \le l_i \lt r_i \le n

イデア

まず、絶対値を考えるのはややこしい。数列をreverseしてindexもreverseして同じクエリに対して答えれば題意の条件を満たすことが出来るので、a_s \ge a_t (s \lt t)という条件の部分についての最小値を考えることにする。

クエリの先読みを考えよう。rの昇順でクエリを処理していくことにする。今、rを固定した状況に対して、ans[i] = 左端がiの時のクエリの答えとしてrを右に動かしながら配列を更新し、クエリに答えていく。

さて、今rが右に動いてx( = a_r)に注目しているという状況で、ansはどのように更新されるか考えてみる。いま、a_s \ge a_t (s \lt t)という条件の部分についてのみ考えるという条件があるので、j = rからスタートしてjを少しずつ減少させていき、初めてa_j \ge xになるような位置jをまずは見つける(a_j = yとする)。

まず、このようなjを見つける事ができれば、k \in [ 0,j ] について、必ずyxを含むことから、ans[k]はy-x以下であることは分かるので、最小値を更新出来る。ここで、ansという配列を遅延segment tree上で管理すれば、区間のupdateなどはO( \log n)で処理出来る。今回は区間のupdateの左端が0で固定なので、普通のsegment treeで良さそう。

その次にこのupdate処理を入れるべき箇所としては、更にjを左に動かしていき、 x \le a_{j'} = y' \lt yとなるような箇所j'である。y'の方がyよりもxに近い値を取ることから、k \in [ 0,j' ] について、ans[k]はy' -xで最小値を更新出来る。

よって、rを右に動かしながら、そのたびにjrから0に動かしてsegtreeを更新していけばO(n^2 \log n)で出来るように見えるけど、これでは不十分なので、更に高速化することを考える。

さて、yから次のy'を見つける部分について考えてみる。このとき、y' -xという値で最小値が更新される条件を考えてみると、y'xを含む区間というのは必ずyも含んでいることは、先の操作を考えると明らかであるので、最小値が更新される条件として、y' - x \lt y - y'となる必要がある。これを式変形するとy' \lt \frac{x+y}{2}となる。このy'の制約によって、1つの固定されたrに対して先のようなupdateの処理は高々 \log 10^9回となる。これは、十分に速く動作する。この問題を解くためにはこの考察がなければ解けない。言われてみると当たり前のことだが、このように条件を見て式変形することで実際に計算量を落とすことが出来るとても面白い問題だった。

実装(C++)

続きを読む