裏紙

ほぼ競プロ、たまに日記

CS Academy #38 - Tree Antichain (Hard)

CS Academy programming

問題

CS Academy

問題概要

頂点数nの木が与えられる。長さnの順列aを考え、それを頂点に対応させる時、a_iとa_{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

Codeforces programming

問題

Problem - F - Codeforces

問題概要

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

l_iとr_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 ] について、必ずyとxを含むことから、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を右に動かしながら、そのたびにjをrから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++)

続きを読む