のんびり座りたい 〜 横へな 2013.2.2

問題

いくつかの椅子がある。そこにひとりずつ人が現れ、あるいは立ち去る。
椅子は一列に並んでいる。
人が座る席は以下のルールで決まる:

  1. どちら側の隣にも人が座っていない席を選ぶ。
  2. それが無理なら、片側にしか人が座っていない席を選ぶ。
  3. それも無理なら、両側に人が座っている席を選ぶ。
  4. 上記の条件で一つに決まらない場合は、候補のうち最も左にある席を選ぶ。
  5. 一度座ったら立ち去るまでその場を動かない。
指定された順序で人が来たり立ち去ったりした結果、それぞれの椅子に誰が座っているのかを出力せよ。

入力

入力は 6:NABEbBZn のような形式になっている。
: 」の前(上記の例では 6 ) は椅子の数を示す。
: 」の後(上記の例では NABEbBZn ) は人の出入りを示す。A〜Z は、それぞれの人の到着を意味し、a〜z は、対応する大文字の人が立ち去ったことを意味する。

出力

出力は、席に座っている人を左から順に並べる。誰も座っていない席は - で示す。
入力が 6:NABEbBZn の場合、

記号 説明 席の状態
初期状態
------
N N があらわれた
N-----
A A があらわれた
N-A---
B B があらわれた
N-A-B-
E E があらわれた
N-A-BE
b B が立ち去った
N-A--E
B B があらわれた
N-AB-E
Z Z があらわれた
NZAB-E
n N が立ち去った
-ZAB-E
となるので、文字列 -ZAB-E を出力すれば良い。

補足

実装ができた方は Qiitaの記事 のコメント欄からリンクを張っていただくと見つけやすくて助かります。

サンプルデータ

# 入力 期待
1 6:NABEbBZn -ZAB-E
2 1:A A
3 1:Aa -
4 2:AB AB
5 2:AaB B-
6 2:AZa -Z
7 2:AZz A-
8 3:ABC ACB
9 3:ABCa -CB
10 4:ABCD ADBC
11 4:ABCbBD ABDC
12 4:ABCDabcA -D-A
13 5:NEXUS NUESX
14 5:ZYQMyqY ZM-Y-
15 5:ABCDbdXYc AYX--
16 6:FUTSAL FAULTS
17 6:ABCDEbcBC AECB-D
18 7:FMTOWNS FWMNTSO
19 7:ABCDEFGabcdfXYZ YE-X-GZ
20 10:ABCDEFGHIJ AGBHCIDJEF

C/C++/Java 用のテストデータ