GCJ2012 Round 1A Problem C. 問題紹介

Google Code Jam 2012 Round 1A
Problem C. Cruise Control 問題紹介

自動車を一定速度で走らせてくれるクルーズコントロールの問題です。

2車線の一方通行の道路を N台の車（各車は長さ5m）がクルーズコントロールを使って一定の速度で走っています。各車、隣に車がいてぶつかる状況でなければ車線変更ができます。
このとき、いずれかの車が前走車にぶつかりそうになってクルーズコントロールを解除するまでの最長時間を求めます。

• 車線変更は一瞬で行われるものとして車線変更にかかる時間は無視できますが、隣同士の車が同時に入れ替わることはできません。
• ぶつからずに全ての車がずっと走り続けられるケースもあります。

入力データ:
最初の行は問題数 T。以降 T問の問題データが続きます。
問題データの1行目は車の台数 N。その後N行、各車の最初の場所と速度の情報がスペース区切りで与えられます。

左車線“L” または 右車線“R” を示す Ci、速度(秒速) Si（m/sec）、開始時にいる場所（基点からの距離） Pi（m）。

データ制限:

• 1 ≤ T ≤ 30 （問題数は30問）
• Small input の場合：1 ≤ N ≤ 6 （最大6台の車）
  Large input の場合：1 ≤ N ≤ 50 （最大50台の車）
• Ci = “L” or “R” （左車線“L” または 右車線“R”）
• 1 ≤ Si ≤ 1000 （秒速1m〜1000m）
• 0 ≤ Pi ≤ 10000 （最初の位置、基準から何mか）
• 最初の位置の時点で車が衝突していることはありません。同じ車線にいる車の最初の位置は必ず5m以上離れています。