【><>】AtCoderに登録したら解くべき精選過去問 10 問を難解言語 Fish ><> で解いてみた② Practice～第3問編

Last updated at 2024-10-30Posted at 2024-10-27

前回の記事を読まれていない方は，先に前回を読むことを推奨します．
① ><>とは何か編
次回はこちらです．
③ 第4問～第7問編

はじめに

こんにちは，><>でAtCoder Beginning Sectionを解いていく記事その2です．

今回はAtCoder Beginning SectionのPracticeA ~ 第3問 Shift only までの解説を行います．
第4問以降はまた次の記事で解説していこうと思います．

解く順番は，第2問 -> 第1問 -> PracticeA -> 第3問とします．><>的に簡単な問題から解いていきます．

第2問 ABC081A - Placing Marbles

><>で一番簡単に解ける問題です．

a.fish

i"0"- i"0"- i"0"- ++n;

最長実行時間 : 9ms
提出したコードはこちら．

0と1からなる長さ3の文字列を受け取り，1の数を出力する問題です．

iで入力を受け取った後"0"で引くことで，文字ではなく数値としてスタックに追加します．そして３つの数を足し合わせてnします．

可読性のために空白を入れておりますが，空白はなくとも問題ありません．以下のようにするとより短く書けます．

ans.fish

i"0"-i"0"-i"0"-++n;

><>においてはコードの短さ（正確にはコードボックスの大きさ）が実行速度と密接にかかわるので，なるべくコードは短く書くべきです．（厳密には少し違うのですが，詳しい話は次回以降に解説したいと思います．）

しかし，今回は解説のためTLEとならない程度に空白をいれて可読性を上げていこうと思います．

第1問 ABC086A Product

次に簡単な問題は第１問です．なかなかPracticeA Welcome to AtCoderにいけませんね...

$a \quad b$を受け取って積が偶数か奇数かを返す問題です．

この問題の難しいところは$a \quad b$をスタックに追加するところです．「iを2回呼ぶだけじゃない？」と思っている人はまだまだ><>脳ではありません．

例えば3と4が入力される場合，><>的には51(3) 32(SPC) 52(4) 10(LF)の4つを受け取ることになります．（AtCoderの入力は必ず最後に改行LFが挿入されます．）

「じゃあiを4回呼んで，空白と改行を削除すればいいんだ！」というわけでもありません．

なぜならば33と34が入力される場合，><>的には51(3) 51(3) 32(SPC) 51(3) 52(4) 10(LF)の6つを受け取ることになってしまうためです．

そのため入力を数値として受け取ってスタックに追加する場合は以下のようなアルゴリズムを用いる必要があります．iは入力がない場合，-1をスタックへと追加することに留意してください．

スタックに0を追加する0
入力を受け取るi
スタックの先頭を複製し-1と比較する: 01- = ?　もし等しいならば，スタックから2つ削除して終了
スタックの先頭を複製し改行・空白と比較する: a=? : " "=?　もし等しいならば，スタックの先頭を削除してから1に戻る
数字を"0"で引く
1つ前と入れ替えて10倍した後，足し合わせ，2に戻る $a*+

以上を実装したのが以下のコードです．ジャンプ命令.を使っているので，コードの一番上に置かないと動作しません．

 0i :01-=?v :a=?v :" "=?v "0"-$a*+ 10.
          >~~;  >       > ~ 00.

実際の実行の様子がこちらです．うまいこと入力をスタックに追加できていることが分かるかと思います．

正直長いうえあまり効率もよくないアルゴリズムであると思いますが，参考にできるコードがほとんどないうえ，他に良い方法も思いつかないので，ひとまずこの方法で問題を解いていきます．

ans.fish

 0i :01-=?v :a=?v :" "=?v "0"-$a*+ 10.
v      ~~ <     >       > ~ 00.
> * 2% ?v "Even" r oooo;
        > "Odd"  r ooo;

最長実行時間 : 8ms
提出したコードはこちら．

さて前置きが長くなってしまいましたが，以上が提出したコードになります．
入力さえ受け取れてしまったら，あとはかけて*，2の余りをとって2%，最後に?するだけなので簡単です．

今回のように文字列を順番通り追加してrして出力するためには，スタックに文字列以外存在しない状態でなければならないことに注意してください．

PracticeA Welcome to AtCoder

というわけでようやくPracticeAです．

a (LF) b (SPC) c (LF) s (LF)が入力されるので，$a+b+c$の結果と文字列$s$を出力する問題です．

ここまでやってきた人ならばこの問題がいままでの問題の中で，一番難しい理由がわかるでしょう．><>で文字列と数字を区別することは困難です．

そこで先ほどの入力を受け取るコードを改造して，改行と空白の数をカウントして処理を切り替えるようにしてみます．
改行・空白を3回受け取るまでは前述のアルゴリズムでスタックに数字を追加し，3回目になった時点でスタックの数字を全て足して出力n．$a+b+c$の結果と文字列$s$の間に空白を挿入する必要があるため空白を出力し" "o，以降はLFを受け取るまでiしてoするのを繰り返せばよさそうです．
数をカウントする方法はいくつかありますが，一番簡単なg命令とp命令を用いてプログラム中に直接数値を書き込む方法を用いてみます．

ans.fish

>0i :a=?v :" "=?v "0"-$a*+ 10.
^       >       >~ 05g 1+ :3=?v 05p
~++ n " "o  >i :a=?;o v       > 
            ^         <

最長実行時間 : 7ms
提出したコードはこちら．

><>らしいコードになってきました．プログラムがどのような順番で動くか大変分かりにくいですね．
カウンタ代わりに使っているマスは$(0,5)$でコードボックスの範囲外のマスです．><>では範囲外のマスは0が入力されている扱いになるので，初期化の必要がありません．

第3問 ABC081B Shift only

この記事で解説する最後の問題です．

N (LF) A1 (SPC) A2 (SPC) ... AN (LF)が入力されるので，各Aについて2で何回割ることができるか調べ，その最小値を出力せよという問題です．

先ほどの入力を受けとるプログラムを改造して，数値を1つ受け取るごとに何回2で割れるかを調べ，最小値を更新していき，入力が受け取れなくなったら最小値を出力するという方針で解いていきます．
今回は最小値をレジスタに保存してみます．

プロセスが多いので，ジャンプ命令を駆使してなるべく左から右へ処理されるように書いてみました．

b.fish

 ia=?v 00.
     > 02.
 a a* & 03.
 0i :01-=?v :a=?v :" "=?v "0"-$a*$+ 13.
          > 05. >       >~06.
 &n;
 0$ : 2% ?v 2, $1+$ 36.
          > ~ :&:@ (?$ &~ 03.