はじめに

こんにちは，この記事ではABC394のA問題から，D問題までを><>で解くときの解法を解説します．

ちなみに私はABC394で，コンテスト中にA問とC問を><>で提出できました．
今回のように><>にとって解きやすい問題でないと，コンテスト中に><>で問題を提出するのは，私にとってなかなか難しいです．もっと精進したいところですね．

A問題

↓問題リンク

与えられた文字列$S$から，「2」以外の文字を削除して出力する問題です．
><>的には入力を受けとって，

-1(EOF) だったら終了
2 だったら出力
それ以外だったら無視

するだけなので，非常に簡単です．

A問題

i:0(?;"2"=?2l?n

実行時間 : 1ms

i:0(?;は入力を受けとり，それを複製して0未満であるか確認し，そうであったら終了する処理．
"2"=?2l?nはスタックに残った値が"2"であれば出力する処理です．

B問題

↓問題リンク

文字列が$N$個当たられるので，長さが昇順になるように並べ，結合して出力する問題です．
変数を一つのスタックで処理することしかできない><>としては，文字列のソートはかなりハードです．
そこで今回の問題の制約が，「文字列の長さは全て異なる」「文字列の長さは50以下」「$2 < N < 50$」であることを利用して解いていきます．

まず，文字列とその長さをスタックに格納します．例えば入力が「3 tc oder a」ならば，スタックが「t c 2 o d e r 4 a 1」となるように追加していきます．

次に，1~50までの数字について，スタック内に一致するものがあるか走査し，存在していれば[命令で文字列を丸ごと新しいスタックにコピーして出力します．

以下のコードでは出力した文字列を適宜消去することで，プログラムの終了条件が「スタックが空になった時l0=?;」となるようにしています．

B問題

0& ia=?v 20.
       > 02.
> i : 0(?v : a=?v
         >04.   > ~ l &-l& 02.
 ~ &~ 1& 05.
 l0=?; l> :0=?v $ : &:& =?v } 1-                         v
        ^     > ~ &1+& v  > $ ~ [ r > l0=?v o          v v
        ^              > 05.        ^     > ] &1+& 05. v v
        ^                           ^                  < v
        ^                                                <

実行時間 : 34ms

今回は最大でも$N=50$程度なので十分実時間内に処理出来ましたが，かなり遅い処理を使っているので，もう少し$N$が大きい場合は考える必要がありそうです．

C問題

↓問題リンク

与えられた文字列$S$から，WAをACに置換する問題です．
ただし，例えばWWAのような文字列はWWA→WAC→ACCのように置換されるので，文字列の先頭から愚直に置換するだけではうまくいきません．しかし，><>的には先頭から愚直に置換していきたいところです．

そこで，iでWを受けとった場合，その数をカウントしておき，続けてAを入力で受け取った場合に，カウントした数分のCを出力すれば，文字列を遡ることなく置換できます．
WWWCなどは置換されないため，A以外の入力を受けとった場合，カウントした数分Wを出力します．

以下のプログラムでは，Wの数をレジスタに記録しています．

C問題

 0& 01.
 i :0(?v :"W"=?v :"A"=?v 07.
       > 09.   > 03.   > 05.
> ~ &1+& 01.

> ~ "A"o & >    :?v ~ 0& 01.
           ^o"C"-1<
> & >    :?v ~ 0& o 01.
    ^o"W"-1<
 ~ & >    :?v ;
     ^o"W"-1<

実行時間 : 129ms

$S$の長さが$3 \times 10 ^ 5$の割には早く解けているので，><>適性の高い問題でした．

D問題

↓問題リンク

()，[]，<>で構成された文字列が，問題文で定義されるところの「カラフル括弧列」であるかを確かめる問題です．
スタックを利用して解く問題なので，><>にとっては非常に解きやすい問題です．(コンテスト中に提出できませんでしたが...)

D問題

 i :a=?v :")"=?v :"]"=?v :">"=?v
       >02.    >04.    >06.    >08.
 ~ l?v "seY"ooo;
     > "oN"oo;
 ~ l?!v "("=?!v 00.
      >       > "oN"oo;
 ~ l?!v "["=?!v 00.
      >       > "oN"oo;
 ~ l?!v "<"=?!v 00.
      >       > "oN"oo;

実行時間 : 63ms

結構簡単だったので，コンテスト中に出せなかったことが悔やまれます．

終わりに

私事ではありますが，最近多忙だったため，あまりAtCoderのコンテストに参加できていませんでした．今回，久しぶりに><>を使ってプログラムができたので大変満足しました．
今回のように長い文字列を先頭から処理していく問題は><>的に解きやすいので，また似たような問題があれば解説記事を書きたいと思います．