Osaki 解説

アルゴリズムの概略

「電車は同時に最大で何本走っているか」を求める問題。

発着状況を時刻順にシミュレートし，現時点で何本走ってるかを記録しておけば解けます。 出発と到着のを全て一つの配列にまとめ（イベント配列），それを時刻順にソートし，先頭から見ていきます。 まず，最初は「現在走っている電車数」は当然0で，電車の出発イベントであれば「現在走っている電車数」を1増やし， 到着イベントであれば「現在走っている電車数」を1減らします。 後はcurrentを見てその都度maxを更新しておけば，それが答えになります。

なお，大崎駅に到着した電車は，その到着と同じ時刻に出発できるので， ソート時には出発よりも到着の方を先に並べておく必要があります。

アルゴリズムの計算量

イベント数を n とすると，全イベントを時刻順にソートするために O(n log n) かかります。 ソートされたイベントを調べて電車数をカウントする処理は O(n) なので， 全体の処理としては O(n log n) になります。

n ≦ 10,000 なので，n log2 n < 10,000 * 14 = 140,000 = 140K 程度の計算量になります。 問題セットが 10,000 くらいまでであれば解けそうですね。

アルゴリズムの実装

ソート条件の指定（実装）をできるだけ何も見ずに書けるように練習しておきましょう。 C++ であれば構造体の < 演算子をオーバーロードすることになるでしょう。

別解

p0105-deq-n2.cpp は O(n2) の計算量のアルゴリズムで解いています。 これは，時刻表の各行を出発時刻でソートしておいて， 上から順に見ていき，（それが未処理であれば）電車を走らせカウントを1増やします。 そして，その電車が戻ってきた時刻と同じかそれより遅い出発時刻の行があれば，その電車を使えるので（カウントを増やさずに）その行を消していきます。 このアルゴリズムはカウントを増やす外側のループと，カウントを増やさない内側のループがあるので，計算量は O(n2) になります。 n = 10,000 とすると n2 = 100,000,000 = 100M なので，問題セットが少なければ解けてしまいます。

また，電車は1日間だけなので，24×60×60 = 86,400 の大きさの配列を用意しておいて，各秒に対する電車の本数を数え上げれば解くことができます。 詳細はOB/OGの会の解説を参照してください。

$Id: index.shtml 1574 2007-06-25 08:30:30Z SYSTEM $