問題を言い換える（トンネル）

March 2, 2023

問題

全長 $L$ メートルのトンネルには、 $N$ 人の人がいます。

人 $i$ はトンネルの西端から $A_{i}$ メートルの位置にいて、方向 $B_{i}$ （東または西）へ歩いています。

トンネルの幅は狭いため、２人が同じ位置にきたらお互い移動方向を変えます。

全員が秒速１メートルで歩くとき、最後の人がトンネルの外に出るのは何秒後になるでしょうか。

[制約]
🔹 $1 ≦ N ≦ 200000$
🔹 $1 ≦ A_{1} < A_{2} < \dots < A_{N} < L ≦ 10^{9}$

解き方・ソースコード

まずこの問題を解くために思いつくのは人の動きをシミュレーションすることですが、ケースによっては衝突回数が $N^{2} / 4$ 程度になりとても時間がかかってしまいます。

そこで人同士を区別しないで考えてみると、２人が衝突して向きを変えることと２人がすれ違うことは同じことであるが分かります。

したがってこの問題は、以下のように言い換えることができます。

トンネルの幅は十分広いため、２人が同じ位置に来ても、すれ違ってそのまま進みます。

最後の人がトンネルの外に出るのは何秒後になるでしょうか。

言い換えた問題を考えると、人 $i$ がトンネルの外に出るまでの時間は、移動方向が東の場合 $L - A_{i}$ 秒、移動方向が西の場合 $A_{i}$ 秒となりますので、その最大値を出力すればよいことになります。

[Google Colaboratory]

#--------- 入力例1 ---------
N = 3                   # 人数
L = 100                 # トンネルの長さ（メートル）
A = [20, 50, 70]        # トンネルの西端からみた人の位置（メートル）
B = ['東', '東', '西']  # 向いている方向
#---------------------------
Answer = 0
for i in range(N):
    if B[i] == '東':
        Answer = max(Answer, L - A[i])
    if B[i] == '西':
        Answer = max(Answer, A[i])

print('解：', Answer)

[実行結果（入力例１）]

解： 80

最後の人がトンネルから出るのは 80秒後 であることが確認できました。