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

問題

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

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

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

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

[制約]
🔹1≦N≦200000
🔹1≦A1<A2<…<AN<L≦109

解き方・ソースコード

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

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

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

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

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

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

[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秒後 であることが確認できました。