反省
問題を読んでおらず、必要な実装(解法2)に対して、明らかに重い実装(解法1)をしてしまったので自戒。
題意
問題はとてもシンプルだが、まとめると以下の通り。
n階建ての建物があり、すべての階にはレストランがある。
あなたのオフィスはs階にある。
ところが、k個の階でレストランが工事中である。
一番近い回転中のレストランとは何フロア離れているか？
※1: k <= 1000
In/Outの例を見ると、
n,s,k = 100 76 8
kの配列 76 75 36 67 41 74 10 77
100階建ての建物があり、オフィスは76階であり、工事中の階は(sortして) 10 36 41 67 74 75 76(オフィス) 77 。
オフィスの上の階で一番近いのは78階、下で近いのは73階になるので、78階に向かえばよく、2が答えになる。
解法1: ソート済みの配列を前後に探索
単純に上記で述べた実装をする。以下の図がイメージ。
1. kの配列をソートし、sの位置を知る。
尚、sが存在しない場合、答えは`0`(移動しなくていい)である。)
2. 配列を左方向に見る。差が1である限り左に進んでいく。
3. 差が1よりも大きい場合、その間のレストランはすべて開いているので、一番sに近い階が下に降りた場合に最も近いレストランである。
（図では76から下り、74の次は67であるため、68-73階のレストランは空いている）
4. 2,3において、下に降りても開いているレストランが存在しないことがある。
(例えば、2階にオフィスがあり、1,2階のレストランが閉まっている場合、下に答えはない)
5. 上記を同様に右方向（上側）にも探索する
6. 上にも下にも候補となるレストランがあるならminをとり、片方がしか候補がないならそれを答えとする
これを実装したものが以下。
q = int(input())
for qq in range(q):
res = -1
n, s, k = map(int, input().split())
dat = list(map(int, input().split()))
dat = list(set(dat)) # 題意的にある階がリストに複数回含まれる時の対策 [2,2,3]等
dat.sort()
if s not in dat: # もし、sがリストにないなら、sの階のレストランは開いている
print(0)
continue
ind = dat.index(s) # sの入っているインデックスを取得
r = l = -1 # 下方向(l)も上方向(r)も見つかっていないことにする
# 上方向の探索
for i in range(ind + 1, len(dat)): # sの一つ上のインデックスから最上階まで探索
if (dat[i] - dat[i - 1]) != 1: # もし、差が1出ないなら
r = dat[i - 1] + 1 # 上向きはその区間の一番低い階が候補
break
if r == -1 and dat[-1] != n: # もし、連続した階しかなく、しかし、リストの最後が最上階でないなら
r = dat[-1] + 1 # リストの一番上の階の上が候補となる
# 同様の処理を下方向にも行う
for i in range(ind - 1, -1, -1):
if (dat[i + 1] - dat[i]) != 1:
l = dat[i + 1] - 1
break
if l == -1 and dat[0] != 1:
l = dat[0] - 1
if r == l == -1: # 題意より開いているレストランがないことはない()
print("ERROR")
elif r == -1: # 上方向に候補がないなら
print(s - l) # 答えは下方向
elif l == -1: # 下方向に候補がないなら
print(r - s)
else: # 上も下も候補があるなら差が小さいほう
print(min(s - l, r - s))
解法2: ソートもせずに単にリストを探索する
この問題の説明に書いたが、そもそもこの問題でレストランが閉じているリストの最大値は1000である(※1の通り)。
このため、sを中心に500階分リストに存在するか確認すればよい。
1000要素のリストに対する500回程度の探索なので、ソート＆二分探索もいらない。ということで、以下でAC。
q = int(input())
for qq in range(q):
n, s, k = map(int, input().split())
dat = list(map(int, input().split()))
res = 0 # オフィスの位置からのdelta
while True:
if (s + res) not in dat and (s + res) <= n: break # 上方向
if (s - res) not in dat and (s - res) >= 1: break # 下方向
res += 1
print(res)