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

問題

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

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

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

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

[制約]
🔹$ 1 \leqq N \leqq 200000 $
🔹$ 1 \leqq A_1 < A_2 < … < A_N < L \leqq 10^9 $

解き方・ソースコード

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

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

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

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

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

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

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#--------- 入力例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秒後 であることが確認できました。