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


:::note info
前回の記事を読まれていない方は，先に前回を読むことを推奨します．
[① ><>とは何か編](https://qiita.com/ASURA-the-great-robot/items/13c94770c8e3645c5853)
次回はこちらです．
[③ 第4問～第7問編](https://qiita.com/ASURA-the-great-robot/items/ee721cd85d84e3c3d1c6)
:::

# はじめに

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

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

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

# 第2問 [ABC081A - Placing Marbles](https://atcoder.jp/contests/abs/tasks/abc081_a)

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

```fish:a.fish
i"0"- i"0"- i"0"- ++n;
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3632687/1fc0417d-dd41-02fb-bc06-18a3429168ea.png)

最長実行時間 : 9ms
提出したコードは[こちら](https://atcoder.jp/contests/abs/submissions/59137228)．

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

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

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

```fish:ans.fish
i"0"-i"0"-i"0"-++n;
```

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

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

# 第1問 [ABC086A Product](https://atcoder.jp/contests/abs/tasks/abc086_a)

次に簡単な問題は第１問です．なかなか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をスタックへと追加することに留意してください．

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

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

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

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

![input.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3632687/aca0517b-e6d9-0a1f-e9fe-cbbeb5873c11.gif)

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

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3632687/03aa09a2-284e-ad46-7ba7-60fad3af5db2.png)

最長実行時間 : 8ms
提出したコードは[こちら](https://atcoder.jp/contests/abs/submissions/59193071)．

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

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

# PracticeA [Welcome to AtCoder](https://atcoder.jp/contests/abs/tasks/practice_1)

というわけでようやく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`命令を用いてプログラム中に直接数値を書き込む方法を用いてみます．

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3632687/761f33cb-958d-c8db-b878-875a616e72f9.png)

最長実行時間 : 7ms
提出したコードは[こちら](https://atcoder.jp/contests/abs/submissions/59193313)．

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

# 第3問 [ABC081B Shift only](https://atcoder.jp/contests/abs/tasks/abc081_b)

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

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

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

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

```fish: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.
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3632687/85a70eff-4758-ff5e-0c4d-179aad61a01c.png)


最長実行時間 : 8ms
提出したコードは[こちら](https://atcoder.jp/contests/abs/submissions/59202206)．

1,2行目は改行(LF)が入力されるまで入力を受けとる処理です．これによって最初の$N$を無視します．なお，`><>`では`l`でスタックの大きさが取れるので，最初の$N$は不要であることが多いです．終了したら3行目にジャンプします．

3行目は100をレジスタに保存しています．最小値を求める場合，変数を十分大きい値で初期化すると思いますが，要はそういうことです．$1<A_i<10^9$なので$10^9<2^{32}$であることを加味すると100で初期化しておけば十分であるとわかります．終了したら4行目にジャンプします．

4,5行目は数値を取得する処理です．入力がなくなったら6行目，空白か改行を受けとったら7行目にジャンプします．

6行目は結果を出力する処理が書かれています．レジスタの中身を`n`します．

7,8行目はスタックに追加された値を2で何回割れるか調べ，レジスタの値を更新します．

# 結びに

いかがでしたか？すらすらサンプルコードが読めたら，`><>`でAtCoderの過去問を解いてみることをお勧めします．昔のA問題は結構簡単に解けるかと思います．

次回の記事はこちらです．

https://qiita.com/ASURA-the-great-robot/items/ee721cd85d84e3c3d1c6

<details><summary>今回解説したコードはこちら</summary>

- PracticeA - Welcome to AtCoder https://atcoder.jp/contests/abs/submissions/59193313
- ABC086A - Product https://atcoder.jp/contests/abs/submissions/59193071
- ABC081A - Placing Marbles https://atcoder.jp/contests/abs/submissions/59137228
- ABC081B - Shift only https://atcoder.jp/contests/abs/submissions/59202206

</details>

<details><summary>第4問以降のコードはこちら</summary>

- ABC087B - Coins https://atcoder.jp/contests/abs/submissions/59259112
- ABC083B - Some Sums https://atcoder.jp/contests/abs/submissions/59259340
- ABC088B - Card Game for Two https://atcoder.jp/contests/abs/submissions/59260200
- ABC085B - Kagami Mochi https://atcoder.jp/contests/abs/submissions/59260741
- ABC085C - Otoshidama https://atcoder.jp/contests/abs/submissions/59128526
- ABC049C - 白昼夢 https://atcoder.jp/contests/abs/submissions/59094580
- ABC086C - Traveling https://atcoder.jp/contests/abs/submissions/59130970

</details>

# おまけ

Qiitaでは記事にタグをつけることができます．そのため私はこの記事に`><>`のタグをつけようとしたのですが...

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3632687/24f5756c-a14e-af7f-9ffb-2c970bf99814.png)

どうやら`>`や`<`はタグに含めることができないようです．仕方がないので全角で`＞＜＞`をタグに追加しております．

fishというタグをつけようかとも思ったのですが，fishタグはfish-shellの記事が投稿されているタグだったので，検索の邪魔になるかと思い，このようにいたしました．

とはいえ，全角の`＞＜＞`はあまり見栄えが良くありませんし，検索もしづらいので，何かよい方法があればご教授いただけると幸いです．