日々drdrする人のメモ

今日もdrdr、明日もdrdr

CodeChef May Challenge 2018: Rubber Band

CodeChefのMay Challenge 2018の問題: Rubber Band (Code: RUBBER)
問題: https://www.codechef.com/MAY18A/problems/RUBBER

コンテスト中解けなかった問題。解法メモ。

問題概要

ボード上に {N}個のnailが固定されている。そこに、 {M}個の線分で輪っかが構成された1つのrubber bandが存在している。
rubber bandをnailと交差しないように自由に形を変形することで、 {N}個のnailとrubber bandを完全に分離(つまり、rubber bandの輪の中にnailが存在しない状態を実現)できるかを判定せよ。


f:id:smijake3:20180527232933p:plain

制約

1つのテストケースに含まれるケース数:  {1 \le T \le 100}
 {1 \le N \le 1000}
 {3 \le M \le 3000}
 {|x|, |y| \le 100}
任意のnailとrubber bandの任意の点(線分上含む)の間の距離は少なくとも {10^{-4}}以上ある。

解法

コンテスト中は、こういう問題を扱う数学の分野があったような...と思ったけどよくわからず詰んだ。

解法はCodeforcesのページのコメントで紹介されていたpdfを参考にした。ざっくりと読んで書いているので間違ってたら申し訳ない。


この問題はHomotopyで考えられる。
 {N}個のholeである頂点を持つpolygonにおいて、 {M}個の線分によって構成されるloopがcontractibleである(loop内部にholeがない状態で一点につぶせる)かを判定する問題である。この判定アルゴリズムは上pdfのTheorem 3.22を利用して解ける。

今回はTheorem 3.22に沿って解法を説明する。


今回の判定は大雑把に以下の流れで行う。

  1. nailの {N}個の頂点をソート
  2. rubber bandの {M}個の線分で構成されるloopに沿って、 {N}個のnail頂点との関係を見ることでcrossing sequenceを計算
  3. 計算したcrossing sequenceをstackを用いながらreduce
  4. reduced crossing sequenceが空文字列となった場合は"YES"、そうでない場合は"NO"を出力


解法の説明のために、以下の例を考える (青い点がnail, 黒い線がrubber bandの線分, 頂点の黒い番号が頂点番号)
f:id:smijake3:20180527200417p:plain

まず、nailの頂点をx座標でソートする。


次に、rubber bandを構成する線分とnailの頂点との関係を見ることで、crossing sequenceを計算する。
crossing sequenceは、holeに従って分割した空間の各境界とpathやloopがどのように交差するのかを表す系列である。具体的には、分割した境界に記号を付加した上で、loopに沿って線分との交差を見ていき、交差した順に境界に付加された記号を並べた系列である。

今回は、各nailの頂点を通るy軸に水平な直線で空間を分割する。そして、境界である {i}番目のnailを通る直線について、nailの頂点より上部を通る半直線に数字 {i}、下部を通る半直線に数字 {-i}を付加する。(この時、同じx座標のnailが存在する場合は、y座標が小さい方をより座標が小さい頂点と考えることで対応できる)
今回の例では、以下の図の赤い線で境界を分割し、各 {i}番目の直線において、nailの上部と下部にそれぞれ記号が付加される。(赤文字が半直線に付加された記号)
f:id:smijake3:20180527200754p:plain

そして、始点(例では頂点番号0)からrubber bandの辺を進んでいき、交差した半直線に付加されている記号を順番にsequenceに追加する。
f:id:smijake3:20180527215756p:plain
図中の紫の点が+iの記号、緑の点が-iの記号を示している。
例において、頂点番号0,1,2,3,4,5,6,0の順番でloopと半直線の交差関係を見た時に得られるcrossing sequenceは {(1, 2, 3, -3, -2, -2, -3, 4, -5, 5, 4, 3, -2, 1)}となる。

この系列は、 {O(NM)}で計算できる。


次にこのcrossing sequenceをreduceする。reduce操作では、隣接する同じ記号のペアを消す操作を、消せなくなるまで繰り返す。

例えば、得られたcrossing sequenceにおいて、隣接している2つの-2を消すことができ、 {(1, 2, 3, -3, -3, 4, -5, 5, 4, 3, -2, 1)}へ変形できる。この操作を繰り返すことで、最終的に {(1, 2, 3, 4, -5, 5, 4, 3, -2, 1)}が得られる。
(loopのreduceであるため、正確には循環する系列としてreduceする必要があるが、contractibleな場合は循環的にreduceしなくても空列になるため、今回は必要ない)

このreduce操作はstackを用いることで、系列の長さの線形オーダー(つまり {O(NM)})で計算できる。

最後に、このreduced crossing sequenceが空列であればcontractibleであるため"YES"を出力、そうでなければ"NO"を出力する。この例では、reduced crossing sequenceが空列でないことから答えとして"NO"を出力する。

実装

1ケースの計算量は {O(N \log N + NM)}
今回の実装は、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")