AOJ1336 The Last Ant - 足跡-sokuseki-

問題概要

長さ $l$ cmのトンネルに蟻が $n$ 匹いる。最初、蟻 $i$ はトンネルの左端から $p_i$ cmの場所に向き $d_i$ の状態でいる。トンネルは広い場所と狭い場所があり、狭い場所はトンネルの端から1cmおきのところにある。トンネルのある場所で蟻と蟻が逆向きに歩いて来るとき、その場所が広い場所だと2匹の蟻はすれ違うことができるが、狭い場所だと2匹の蟻はすれ違うことはできず、衝突して今までと逆を向くことになる。

与えられた状態から同時に蟻が動き出すとき、トンネルを最後に出る蟻の番号と、その蟻がトンネルを出るまでにかかる時間を答えよ。

制約

$1 \le n \le 20$
$n + 1 \le l \le 100$
$d_i$ は"L"(左向き)または"R"(右向き)
$1 \le p_1 < p_2 < ... < p_n \le l - 1$

解法

蟻本の最初に載っているAntsという問題を知っていると、どの蟻についても、トンネルから出る時間がトンネルの長さより大きくなることはないということがわかります。
よって、1秒後から $l$ 秒後までのすべての時間について、各蟻がどの場所でどの方向を向いているのかをシミュレーションしてあげると良いです。
計算量は $O(l^2)$ となります。

AIZU ONLINE JUDGE: Code Review