日経ソフトウェアに載っていたパソコン甲子園の問題を解く

（パソコン甲子園２００６年本選・３０点　正答率２４％）

ある世界には，文字だけでできた不思議なヘビが住んでいます．このヘビにはＡ種とＢ種の２種類が確認されていますが，それ以外の種類がいる可能性があります．Ａ種は ">'" の後に１個以上の "=" が並んだ後， "#" が来て，さらに前と同じ個数の "=" が続き，"~"（半角チルダ）で終わります．Ｂ種は ">^"の後に "Q=" が１個以上並んだ後， "~~"（半角チルダ２個）で終わります．

　Ａ種の例：>'====#====~ >'==#==~
　Ｂ種の例：>^Q=Q=Q=~~ >^Q=Q=~~

ヘビを文字列データとして受け取り，それがどんな種類か判別して，Ａ種の場合はＡ，Ｂ種の場合はＢ，Ａ種でもＢ種でもない場合はNAを出力して終了するプログラムを作成してください（下図参照）．１匹のヘビは，１００文字以下の，空白を含まない１行の文字列として入力されるものとします．

懐かしい有限状態オートマトンで解くことにする．
あれ，このＡ種って#挟んで同じ数の=を持っているはずだから，括弧の対応すなわち文脈自由文法（プッシュダウンオートマトン）
じゃなきゃ受理できないんじゃね？という（しばしばしったかと呼ばれる）馬鹿な勘違いをする．

別に===#===の大外同士，真中同士，内側同士の対応を見るわけではないので，文脈自由文法は必要ない．
有限状態なので正規文法で受理できます．

ヘビの長さは有限なので，それだけ状態数を増やしてあげればいいだけのこと．
前半と後半を，「行き」「帰り」と考えて状態名をつけてあげると楽にコーディングできる
以下，状態遷移図（丸の中は状態名）

あとはコーディングスキルの問題
ファイルから入力を読み込むというところに一番時間がかかって２時間程度
本番の制限時間を知らないけれど，１時間とかそんなものでしょう

高校生ってすごいなぁ．．．
普段使っている正規表現の中身にちょっとだけ触れた一日