M-SOLUTIONS プロコンオープン 2020 振り返り
E - M's Solution
N個の集落が効率よく通勤できるように鉄道を敷く．
解法：
愚直に全パターン計算しようとすると，(4**N) * (N**2) ．
事前にコストを計算しておくこと，縦と横を別々に分けることで (3**N) * N になる．
事前にX方向のみ路線を引いた場合，Y方向のみ路線を引いた場合について，各集落のコストを求めておく．計算時間は
(路線を敷く場所) * (各路線から各集落までの距離) = (2**N) * (N**2)
2次元の問題を解く際は，路線の数 = K に対して
2 ** K * nCK 通りの路線の選び方があり，
これは K=0~Nまで足すと 3**N通り．
事前にコストを計算しているため，最小コストはこれにNをかけた時間で求まる．
Submission #15454214 - M-SOLUTIONS Programming Contest 2020
F - Air Safety
飛行機がぶつかるか判断．
ぶつかる場合は最小時刻を求める．
解法：
まずはY方向での正面衝突を考える．Xの順に並べ，同一のXについて衝突までの時間を計算する．
バイナリを使うと効率的に並べ替えられる．
def f(X1, Y1, X2, Y2):
# x1,y1 から y が増える側に移動 vs x2,y2 から y が減る側に移動
ret = 10**18
key1 = (X1 << 32) + Y1
key2 = (X2 << 32) + Y2
ind = key1.argsort()
X1, Y1, key1 = X1[ind], Y1[ind], key1[ind] # X，Yの大きさ順
ind = key2.argsort()
X2, Y2, key2 = X2[ind], Y2[ind], key2[ind]
js = np.searchsorted(key2, key1) # key2にkey1を挿入する場合のインデックス
for i in range(len(key1)):
j = js[i]
if j == len(key2):
continue
if X1[i] != X2[j]:
continue
ret = min(ret, Y2[j] - Y1[i])
return ret
列の終わりに来たり，Xが異なったりしたら次に行く．
飛行機の方向の保存は，
for _ in range(N):
x, y, u = readline().split()
U.append(u)
U = np.array(U, 'S1') # 長さ1のstrを保存
i_u = U == b'U' # [True False False]など該当する部分のみTrueになる
Xu, Yu = X[i_u], Y[i_u] # Upのみ反映される
などで書く方向について書ける．
左右の衝突や90°回転の衝突は変数を変換すればよい．
ans = min(ans, f(Xu, Yu, Xd, Yd)) # 上、下
ans = min(ans, f(Yr, Xr, Yl, Xl)) # 右、左
ans = min(ans, f(Xr + Yr, Xr - Yr, Xu + Yu, Xu - Yu)) # 右、上
ans = min(ans, f(Xu - Yu, Xu + Yu, Xl - Yl, Xl + Yl)) # 上、左
ans = min(ans, f(Xr - Yr, Xr + Yr, Xd - Yd, Xd + Yd)) # 右、下
ans = min(ans, f(Xd + Yd, Xd - Yd, Xl + Yl, Xl - Yl)) # 下、左
