ここで、あるx, yについてのクエリを考える。
まず、Union-Find で頂点 x と y が同じ集合にない場合は -1 を返す。
それ以外の場合、まず先程作った木の上で LCA *1 を行うと、下の図のようにオレンジの頂点を求めることができる*2。
知りたいのは、下の図の緑の頂点が何回目の操作でオレンジの頂点と繋がったかである。

f:id:n_knuu:20171210211028p:plain

ここで、木の頂点vの深さをdepth[v]とする*3。
緑の頂点は、x から (depth[オレンジの頂点] - depth[x] - 1) 回親を辿った頂点(これを頂点 u とする)か、もしくは y から (depth[オレンジの頂点] - depth[y] - 1) 回親を辿った頂点(これを頂点 v とする)のいずれかである。
ただ、u, v のどちらが緑の頂点になるかが問題である。ここで、u, v のうち、緑の頂点ではない方の頂点を赤の頂点とする(下図参照)。

f:id:n_knuu:20171210211020p:plain

赤の頂点がオレンジの頂点と繋がる操作は、緑の頂点がオレンジの頂点と繋がる操作よりも必ず先に行われているという性質を考えると、頂点 u, v の両方求めておいて、それらがオレンジの頂点と何回目の操作で繋がったかについて求めて、その大きい方を答えればよい。
これはUnion-Findで木を作る途中で記憶してあるので、容易に答えられる。(ただし、u, v のいずれかがオレンジの頂点に一致する場合は、そのための処理が必要なので注意)

計算量

O(Mα(N) + (N + Q) log(N))

コード

感想

Union-Find + LCAという解法自体は割とすぐに求まったけど、LCAのライブラリがバグっており、散々だった。
ライブラリをちゃんと整備しておくことは大事。
おそらく人生最後のこどふぇす*4でパーカーを逃したため、非常に辛かった。

最後に

明日は ferin_tech15 さんで「何か書く」です。
一体何が書かれるのか楽しみですね。

*1:第二版 p.293 あたりに載っている。蟻本を読もう！

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

作者: 秋葉拓哉,岩田陽一,北川宜稔
出版社/メーカー: マイナビ
発売日: 2012/01/28
メディア: 単行本（ソフトカバー）
購入: 25人クリック: 473回
この商品を含むブログ (35件) を見る

*2:全ての操作を終えた後にできるのは森であるが、適当な根 r を設定し、ある頂点の属する木の根が自分自身である場合に頂点 r と繋ぐと森を一つの根付き木にすることができるので、その上で LCA の前処理をダブリングで行っておく

*3:LCAをダブリングで求めた場合、これは既に求まっている

*4:社会人Dとかに行けば出られるが、そこまでAtCoderが存在しているのかとか、こどふぇす自体がなくなってないかとかが考えられる

2017-08-03

AtCoder Regular Contest 075 E. Meaningful Mean

AtCoder Fenwick Tree

以下のことを考えて、やっぱり解説を書くことにした

復習のときに思いつかなかったので、ちゃんと記憶に残すために書いておくべき
- 自分用のメモは残したりしているけど、人に読んでもらうために文章を考えることは、記憶に残す上でも文章を書く練習上でも重要だと思う
どうせnim-langで解いているからコード貼ってもわからないでしょ、みたいなのが解説を書かない言い訳になっている状況は良くない

最小費用流の問題が欲しくて探していたら、以前別解で解いた問題があったので、解き直した

問題

D: マーブル - AtCoder Beginner Contest 004 | AtCoder

2016-10-28

DISCO presents ディスカバリーチャンネルプログラミングコンテスト2016 予選 C. アメージングな文字列は、きみが作る！

Suffix Array AtCoder

最大フロー AOJ

Mobile Network | Aizu Online Judge

問題

無向フローが与えられるので頂点1からNへの最大フローを求めよ。
ただし、枝の重みがxの多項式で与えられるものとする。

制約

2 <= 頂点数 <= 50
0 <= 枝数 <= 500
多項式の次数 <= 50
0 <= 係数 <= 100 (ただし係数が0の項は与えられる多項式に含まれない)

2016-10-15

yukicoder No.177 制作進行の宮森あおいです！

最大フロー yukicoder

8月後半〜9月末まではインターンとかで忙しくて中々書けなかったが、そろそろCodeFestival2016本戦に向けて再開していきたい。

問題

No.177 制作進行の宮森あおいです！ - yukicoder

2016-08-12

SRM696 div.1 300 Gperm

bitDP topcoder

寝坊したので出れなかった。

問題

50個の頂点とM個の枝を持つグラフ(単純グラフとは限らない)が与えられる。初め、各頂点は全て塗りつぶされていないとする。毎回、どこか1つの頂点を塗りつぶした後に、枝の両端の頂点がともに塗りつぶされている枝の数だけコストを支払う。支払うコストの合計が最小になるような順番で頂点を塗りつぶしたときのコストを求めよ。

制約

1 <= M <= 20

2016-08-12

Codeforces Round #367 (div. 2)

二分探索 codeforces

Codeforces Round #367 (div. 2)に参加した。
officialだと230位くらいでレートが下がりそうな順位だった。

A. Beru-taxi

問題

タクシーiが(x_i, y_i)にいて、速度v_i(1 <= i <= N)で走ることができる。(a, b)に向かってまっすぐ走ったとき、(a, b)に最も速く着くタクシーの着く時間を求めよ。

解法

距離/速度を計算するだけ

計算量

O(N)

コード

B. Interesting drink

問題

N個の商品が与えられ、その値段がx_1, x_2, ..., x_Nであるとする。これに対して、Q個の金額m_1, ..., m_Qが与えられるので、各m_iで買える商品の種類数を答えよ。

解法

数列をソートすると、m_i で upper bound を取ったときのインデックスが答えとなる。

計算量

O((N+Q)logN)

コード

C. Hard problem

問題

N個の文字列が与えられ、各文字列を逆順にするためのコストc_iが与えられる。幾つかの文字列を逆順にして、文字列を先頭から辞書順になるようにするとき、逆順にするコストの合計を最小化せよ。どのように逆順にしても辞書順にならない場合は-1を出力せよ。

制約

2 <= N <= 10^5
0 <= c_i <= 10^9
文字列の長さの合計 <= 10^5

解法

DP。dp[i][j] := (i-1番目までを辞書順にして、i番目が(j=0→逆順にしない/j=1→逆順にする)場合の最小のコスト)とおくと、
dp[i+1][0] = min(dp[i][0], dp[i][1]) (if (i番目の文字列) < (i+1の文字列) かつ (i番目の逆順の文字列) < (i+1番目の文字列))
dp[i+1][1] = min(dp[i][0], dp[i][1]) + 逆順にするコスト (if (i番目の文字列) < (i+1の逆順の文字列) かつ (i番目の逆順の文字列) < (i+1番目の逆順の文字列))
とする(片方しか逆順になっていない場合はそちらだけで更新する。詳しくはコードを参照)

計算量

O(N+sum(文字列の長さ))

コード

D. Vasiliy's Multiset

問題

初め、multisetには0が1つ入っている。これに対して、1. xをmultisetに追加する、2. xをmultisetから削除する、3. xとmultisetの要素yの中で、x^yが最大になるものを出力する、という3種類のクエリがQ個与えられるので処理せよ。

解法

xとXORを取ったときに、上位bitを立てるようなものがmultisetに入っている場合は、下位ビットがどうなろうとそれを取った方がいいということが分かる。
よって、上位からビットを立てるか決めていく二分探索を行う。

0. left = 0, right = INFとする
1. for i in 30 to 0 do
1.1 multisetに対して、mid=left + 2^iのlower boundを求める
1.2 xのiビットが0の場合、mid以上の値がmultisetにある場合は、iビット目を立てることができるので、left = midとする。もしない場合は、right = midとする。
1.3 xのiビットが1の場合、midより小さくなる値がmultisetにある場合は、iビット目を立てることができるので、right = midとする。もしない場合はleft = midとする。
2 答えをx xor leftとする

制約

1 <= Q <= 2×10^5
1 <= x <= 10^9

計算量

O(QlogQlogx)

コード

感想

Dはもっと複雑なことをしないといけないと思って詰まっていたのがダメだった。
想定解はTrieを使うらしい。