前回の記事を読まれていない方は，先に前回を読むことを推奨します．
① ><>とは何か編
② Practice～第3問編
③ 第4問～第7問編
はじめに
こんにちは，><>で AtCoder Beginning Section を解いていく記事その4です．
今回は AtCoder Beginning Section の第8問 Coins ～ 第10問 Kagami Mochi までの解説を行います．ついに今回で最終回ですね．気合を入れて泳いでいきましょう．
第8問 ABC085C - Otoshidama
第4問のABC087B Coinsに似ている問題です．しかし，今回は10000円と5000円と1000円の枚数a,b,cを素直に全探索するとTLEしてしまいます．本来の回答としては，aとbのみを全探索して，c=N-(a+b)と計算することで計算量を減らすことになるのですが，なんと><>ではこのやり方ですらTLEします．
そこで，AtCoderの模範解答の解き方をまねて，問題を方程式に落とし込み，それを解くことで解を求める方法を用います．
>0i :01-=?v :a=?v:" "=?v "0"-$a*+ 10.
>~~02.> >~00.
aaa** , 11p 01p 03.
5 01g * 11g - :0( ?v : 4 % - 4 , > 05.
> ~ 0 ^
: 11g $ - 5 % + 21p 06.
4 21g * 11g + 5 , 01g - 07.
: 01g $ - 21g - :0 (?v $ n " "o n " "o 21g n;
> "1- 1- 1-" oooo oooo;
最長実行時間 : 8ms
提出したコードはこちら
特にトリッキーなことはしていないので，解説は省略します．
第9問 ABC049C - 白昼夢
文字列$S$がdream dreamer erase eraserの連結でできているか調べる問題です．><>の性質上，後ろから調べるのは簡単なので，結構きれいに解くことができます．
i:01-=?v
v ~~<
> l?!v 04.
>"SEY"ooo;
:"r"=?!v ~"e"=?v 0b.
>07. > :"m"=?v :"s"=?v 0b.
>07. >a9.
:"m"=?!v ~"a"=?!v "e"=?!v "r"=?!v "d"=?!v 02.
>09. > > > > 0b.
:"e"=?!v ~"s"=?!v "a"=?!v "r"=?!v "e"=?!v 02.
>0b. > > > > 0b.
"ON"oo;
最長実行時間 : 42 ms
提出したコードはこちら
第10問 ABC086C - Traveling
さあ，ついに最終問題です．2次元の座標$(x_i,y_i)$と時間$t_i$が渡されるので，$t_i$の時$(x_i,y_i)$にいることができるか調べる問題です．ただし，時刻0の時には$(0,0)$におり，１秒ごとに$x$か$y$を1増やすか減らすことができます，
皆さんご存じのとおり，><>は1次元のスタックを用いてデータを操作するので，2次元以上の次元を持つデータの処理が苦手です．ですが，今回は気合で処理していきます．
0i :01-=?v :a=?v:" "=?v "0"-$a*+ 10.
TXYTXY >04. > >~00.
"oN"oo;
"seY"ooo;
~~{~ 000}}} 21p 11p 01p 05.
l?!v 51p 41p 31p 07.
> 03.
11g 41g - :0( ?v > 09.
> 01- * ^
21g 51g - :0( ?v > + 0b.
> 01- * ^
: 01g 31g- )?v 01g 31g- $- 2% ?v 0d.
> 02. > 02.
31g 01p 41g 11p 51g 21p 05.
最長実行時間 : 946 ms
提出したコードはこちら
><>は最後に追加したものがスタックの先頭になるので，$t_N$から$t_0$へ逆順に走査しています．そのため，スタックの一番最後に初期状態($t=0$，$(x,y)=(0,0)$)を追加してから，走査を開始するようにしています．
結びに
2024年現在，Qiitaに><>でAtCoderを解く方法について解説している記事は(おそらく)0件です．確かに，そもそも難易度の高いAtCoderの問題を，書きづらい><>で解こうとする人はほとんどいないでしょう．
しかし，><>には他の言語にはない仕様がたくさんあり，メジャーなプログラミング言語を使っているだけでは消して味わえない貴重な体験ができます．また，命令ポインターが動き回りながらスタックのデータを処理していく様子は大変味わい深いです．
皆さんもぜひ><>で，普段とは違うAtCoderライフを送ってみてください．私は疲れたのでC++の勉強に戻ります．
提出したコード一覧
- 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
- ABC087B - Coins https://atcoder.jp/contests/abs/submissions/59093840
- ABC083B - Some Sums https://atcoder.jp/contests/abs/submissions/59054083
- ABC088B - Card Game for Two https://atcoder.jp/contests/abs/submissions/59093712
- ABC085B - Kagami Mochi https://atcoder.jp/contests/abs/submissions/59094332
- ABC085C - Otoshidama https://atcoder.jp/contests/abs/submissions/59898889
- ABC049C - 白昼夢 https://atcoder.jp/contests/abs/submissions/59778436
- ABC086C - Traveling https://atcoder.jp/contests/abs/submissions/59460117