Robot In The Field (1101)

概要

  • [−N..N]² の領域がある.
  • ロボットは初期座標 (0,0) から最初は (1,0) の方向にむかって進む.
  • 領域には fork と呼ばれる物体の存在する場所があり,そこではある論理式の値にしたがって,ロボットは右(論理式の値が真のとき),あるいは左(偽のとき)に曲がる.
  • また領域には register inverting points という場所もある.そこでは特定のレジスタの値が反転する.
  • 論理式,fork の座標,register inverting points の座標とレジスタの組は,いずれも入力として与えられる.
    • 論理式は 2 値レジスタ A〜Z および論理演算子などからなる.レジスタの初期値は偽(FALSE).参考までに Sample Input の例を改めて記しておく.
      NOT((A OR NOT B) AND (A OR B)) OR NOT (A AND NOT B OR TRUE)
  • ロボットの動作をシミュレートせよ.

解法

シミュレート自体はいたって単純であるため,構文解析が主体となる.論理式の扱いは各人の好みによるが,おそらく次のいずれかになるだろう.

  1. 毎回文字列から解析する.
  2. 字句解析だけ済ませておく.たとえば次のようなリストを作成する.
  3. より容易に解析できる文字列に変形する.
  4. RPN(逆ポーランド記法)に変換する.
  5. Command パターンを適用する.

2. 〜 4. に対するデータ構造の例を記す.

2. [ NOT, (, (, A, ..., B, OR, TRUE, ) ]
3. !((A|!B)&(A|B))|!(A&!B|1)
4. AB!|AB|&!AB!&1|!| あるいは [ A, B, NOT, OR, ... ]

実際のコンテストの場では 2. あるいは 3. の方針をとるのが妥当.ほかでもきちんと実装できれば問題ないが,さすがに 5. をコンテストの場で実践するのはおすすめできない.

わな

NOT NOT A のような論理式がうまく扱えないと TEST #6 でこける.


Last-modified: 2009-11-06 (金) 13:25:51 (4088d)