CodeChef May Challenge 2018: Rubber Band
CodeChefのMay Challenge 2018の問題: Rubber Band (Code: RUBBER)
問題: https://www.codechef.com/MAY18A/problems/RUBBER
コンテスト中解けなかった問題。解法メモ。
問題概要
ボード上に個のnailが固定されている。そこに、個の線分で輪っかが構成された1つのrubber bandが存在している。
rubber bandをnailと交差しないように自由に形を変形することで、個のnailとrubber bandを完全に分離(つまり、rubber bandの輪の中にnailが存在しない状態を実現)できるかを判定せよ。
制約
1つのテストケースに含まれるケース数:
任意のnailとrubber bandの任意の点(線分上含む)の間の距離は少なくとも以上ある。
解法
コンテスト中は、こういう問題を扱う数学の分野があったような...と思ったけどよくわからず詰んだ。
解法はCodeforcesのページのコメントで紹介されていたpdfを参考にした。ざっくりと読んで書いているので間違ってたら申し訳ない。
この問題はHomotopyで考えられる。
個のholeである頂点を持つpolygonにおいて、個の線分によって構成されるloopがcontractibleである(loop内部にholeがない状態で一点につぶせる)かを判定する問題である。この判定アルゴリズムは上pdfのTheorem 3.22を利用して解ける。
今回はTheorem 3.22に沿って解法を説明する。
今回の判定は大雑把に以下の流れで行う。
- nailの個の頂点をソート
- rubber bandの個の線分で構成されるloopに沿って、個のnail頂点との関係を見ることでcrossing sequenceを計算
- 計算したcrossing sequenceをstackを用いながらreduce
- reduced crossing sequenceが空文字列となった場合は"YES"、そうでない場合は"NO"を出力
解法の説明のために、以下の例を考える (青い点がnail, 黒い線がrubber bandの線分, 頂点の黒い番号が頂点番号)
まず、nailの頂点をx座標でソートする。
次に、rubber bandを構成する線分とnailの頂点との関係を見ることで、crossing sequenceを計算する。
crossing sequenceは、holeに従って分割した空間の各境界とpathやloopがどのように交差するのかを表す系列である。具体的には、分割した境界に記号を付加した上で、loopに沿って線分との交差を見ていき、交差した順に境界に付加された記号を並べた系列である。
今回は、各nailの頂点を通るy軸に水平な直線で空間を分割する。そして、境界である番目のnailを通る直線について、nailの頂点より上部を通る半直線に数字、下部を通る半直線に数字を付加する。(この時、同じx座標のnailが存在する場合は、y座標が小さい方をより座標が小さい頂点と考えることで対応できる)
今回の例では、以下の図の赤い線で境界を分割し、各番目の直線において、nailの上部と下部にそれぞれ記号が付加される。(赤文字が半直線に付加された記号)
そして、始点(例では頂点番号0)からrubber bandの辺を進んでいき、交差した半直線に付加されている記号を順番にsequenceに追加する。
図中の紫の点が+iの記号、緑の点が-iの記号を示している。
例において、頂点番号0,1,2,3,4,5,6,0の順番でloopと半直線の交差関係を見た時に得られるcrossing sequenceはとなる。
この系列は、で計算できる。
次にこのcrossing sequenceをreduceする。reduce操作では、隣接する同じ記号のペアを消す操作を、消せなくなるまで繰り返す。
例えば、得られたcrossing sequenceにおいて、隣接している2つの-2を消すことができ、へ変形できる。この操作を繰り返すことで、最終的にが得られる。
(loopのreduceであるため、正確には循環する系列としてreduceする必要があるが、contractibleな場合は循環的にreduceしなくても空列になるため、今回は必要ない)
このreduce操作はstackを用いることで、系列の長さの線形オーダー(つまり)で計算できる。
最後に、このreduced crossing sequenceが空列であればcontractibleであるため"YES"を出力、そうでなければ"NO"を出力する。この例では、reduced crossing sequenceが空列でないことから答えとして"NO"を出力する。
実装
1ケースの計算量は
今回の実装は、crossing sequenceの生成とreduceを同時に行っている。
Python3だとTLEした
提出コード(Python3): https://www.codechef.com/viewsolution/18676676
PyPy2だと通った
提出コード(PyPy2): https://www.codechef.com/viewsolution/18676708
T = int(raw_input()) for _ in xrange(T): N = int(raw_input()) A = [map(float, raw_input().split()) for i in xrange(N)] M = int(raw_input()) R = [map(float, raw_input().split()) for i in xrange(M)] A.sort() # j: 今見ているnailの頂点番号 j = 0 r0 = R[0] while j < N and A[j][0] < r0[0]: j += 1 st = [] for i in xrange(M): x0, y0 = R[i]; x1, y1 = R[i+1-M] if x0 == x1: continue # x0とx1の間に存在するnailについてx0 -> x1の流れで見ていく if x0 < x1: while j < N and A[j][0] < x1: # x0 -> x1 u0, v0 = A[j] k = j+1 if (y1 - y0)*(u0 - x0) > (x1 - x0)*(v0 - y0): # nail jの上部の半直線を通過 (記号はk) if st and st[-1] == k: # 同じ記号のペアは消す st.pop() else: # 同じ記号のペアが存在しないためsequenceに足す st.append(k) else: # nail jの下部の半直線を通過 (記号は-k) if st and st[-1] == -k: st.pop() else: st.append(-k) j += 1 else: while j > 0 and x1 <= A[j-1][0]: # x1 <- x0 j -= 1 u0, v0 = A[j] k = j+1 if (y1 - y0)*(u0 - x0) < (x1 - x0)*(v0 - y0): # nailの上部の半直線を通過 (記号はk) if st and st[-1] == k: st.pop() else: st.append(k) else: # nailの下部の半直線を通過 (記号は-k) if st and st[-1] == -k: st.pop() else: st.append(-k) if not st: # reduced crossing sequenceが空列 -> contractibleである print("YES") else: print("NO")