phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

GCJ18 Round1B B. Mysterious Road Signs

問題

西から東に向かって無限に長い直線道路のある場所にSignfieldという町がある。
この町から東に向かってS個の道路標識がある。
i個目の道路標識はD_iキロメートル地点にあり、西側から見て表側がA_i、裏側がB_iという整数が書かれている。
この整数は、それぞれの方向に向かうドライバーのための「目的地までの距離」を表すと考えられているが、そうなっていない場合がある。
それを確かめるため、以下の条件を満たす標識集合の最大数、および、その最大数となる標識集合の数を答えよ。

  • 標識集合は、連続する部分集合になっている
  • その標識集合内のすべての標識において、「D_i + A_i = M」または「D_i - B_i = N」のどちらか片方を満たすM,Nが存在する

Case#3の場合、1~3番目の標識はM=4、4~5番目の標識はN=2を満たすので、すべての標識が条件を満たし、サイズが5の標識集合はこれ一つなので、答えは「5 1」になる。

# 形式
# S
# D_i A_i B_i
5
1 3 3
2 2 2
3 1 1
4 2 2
5 3 3

制約

  • 1 <= テストケース数 <= 60
  • 1 <= S <= 10^5
  • 1 <= D_i <= 10^6
  • 1 <= A_i, B_i <= 10^6

解法1

平方分割の古典的な適用例。O(SlogS)解。


標識を順に並べた列を考えた時、その列の真ん中の標識xを「含む」か「含まないか」を考える。
「含む」場合は、標識xの左右に条件を満たすだけ範囲を広げて最大数を見つければ良い。
「含まない」場合は、「0〜x-1までの範囲」か「x+1〜S-1までの範囲」に答えがある可能性があるので、狭めた範囲で同様に含む場合と含まない場合を再帰的に計算する。
f:id:phyllo_algo:20180520025507p:plain

平方分割(再帰関数)の計算量は、Master theorem(分類定理)で求められるらしく、O(SlogS)。
分類定理(master theorem) - LifeTimeException@hrk623

解法2

線形解。
標識を順番に処理していくことを考えて、i番目までの処理結果を使ってi+1番目を高速に処理できないか?を考える。


各標識について、西側から候補地M,Nそれぞれの位置を求めて、並べる。
f:id:phyllo_algo:20180520025752p:plain
これを順番に処理することを考える。


まず、一番左の「M=6, N=-1」があった場合に、次の「M=8, N=-1」を考える。
M側は違うMなので、連続する範囲としたいならば、Nで条件が満たされているようにしなければならない。したがって、"M=8, N=-1で連続する"という条件であれば標識数を2とできる。
N側を見ると、一つ前も同じNなので、"M=*, N=-1で連続する"という条件であれば標識数を2とできる。


続けて「M=7, N=0」を考える。
M側は一つ前で"M=8, N=-1で連続する"なら長さ2であることがわかっていて、Mが異なるので、N側の"M=*, N=-1で連続する"なら長さ2の方から繋ぐ必要がある。
なので、M側は"M=7, N=-1で連続する"なら長さ3とできる。
N側は、一つ前がN=-1で異なるので、M側から繋ぐ必要がある。
一つ前のM側は"M=8, N=-1で連続する"なら長さ3で、Nは0ではないので、N=-1になっていた(一番右側の)地点より右側から連続しはじめた、と求める必要がある、。
ここでは最後の-1の地点はi=0のところなので、i=1から連続したとして、条件を"M=8, N=0で連続する"なら長さ2、と更新できる。


これを繰り返していけばよく、保持しておく必要があるのは、M側、N側それぞれで、

  • M側はどの位置(数値)で連続しているか?その値
  • N側はどの位置(数値)で連続しているか?その値
  • 連続している始まりのインデクスstart
  • 今見ている側だけで今何個連続しているか?(その開始位置xstart)

f:id:phyllo_algo:20180520032849p:plain
を持っておけば、順番に高速に計算できる。


M, Nそれぞれの側で上の情報を保持しておき、i番目からi+1番目を求める時O(1)で、標識数だけ処理するので、計算量全体でO(S)でも求められる。

部分点解法

  • S <= 100の場合
    • 愚直に、連続する部分集合を決めて条件を満たすかどうかをチェックしてあげればよい。計算量はO(N^3)