AtCoderGrandContest038 を brainfu*ckで挑戦
初めに
AGC038が終わりました。Aのみの1完ではありましたが700点はbrainf*ckでは無理なので、満足いく結果です。
ABC140二続き解説記事を書きました。 ABC141？いえ、知らない子ですねぇ。
目次
注意
今回、コンテストに出るにあたって、言語はbrainf*ckを使用しています。
言語仕様などの細かい説明は今回も行いません。
A - 01 Matrix
概要と設計指針
指定の模様が作れるかどうかという問題ですね。結論から言ってしまうと、どのような場合でも作ることができます。
証明はしていませんが、AC出たので間違いないでしょう。
この手の問題は、入力例がすべて達成できている場合は、必ず達成出来ると思っています。
具体的な目的達成手法としては、1行辺り1がA個、0がW-A個の行要素を用意して、それをB行連続で表示、その後、0と1を反転させた行要素をH-B行連続で表示すれば達成できます。
また、その行要素の0と1の順番は任意であるために1がA個連続したあとに0がW-A個並ぶような行要素を作成することにします。
例によってH,W,A,Bは255を超えうるためにマルチバイトで変数をとります。
マルチバイトの話もいずれ記事にしたいとは思っています。
概要とコード
以下にコードを載せますが、長いので折りたたんでおきます。
（クリックで展開）
>>> #region Multi_ReadNum +>+>+>+>+> +>+> //桁数 >+[-< ,+[-----------[---------------------- [--------------<-[+<-]>[[-<+>]>]+<] ]]> ] <<-[+<-]+>[->]< > #endregion >>> #region Multi_ReadNum +>+>+>+>+> +>+> //桁数 >+[-< ,+[-----------[---------------------- [--------------<-[+<-]>[[-<+>]>]+<] ]]> ] <<-[+<-]+>[->]< > #endregion >>> #region Multi_ReadNum +>+>+>+>+> +>+> //桁数 >+[-< ,+[-----------[---------------------- [--------------<-[+<-]>[[-<+>]>]+<] ]]> ] <<-[+<-]+>[->]< > #endregion < #region Multi_IsTrue // note 非ゼロ判定します //start ___{ a*}___ //resilt ___{ a*}_x_ //x : 0 if 0 1 if not 0 [-[+[>]>]+<] <[[<]<]>>[>]< #endregion >> [ - >>>[>]++[<]<<<< #region Multi_DecrimentIfPuls [-[>[+++++++++>]>]+<]>-<< >>>[<+[>]>>]<<< #endregion [<]<<< #region Multi_DecrimentIfPuls [-[>[+++++++++>]>]+<]>-<< >>>[<+[>]>>]<<< #endregion >>>>[>]< #region Multi_IsTrue [-[+[>]>]+<] <[[<]<]>>[>]< #endregion >> ] <<[<]<<< #region Multi_IsTrue [-[+[>]>]+<] <[[<]<]>>[>]< #endregion >> [ - >>[>]>> >>[>]+[<]<<<< [<]<<< #region Multi_DecrimentIfPuls [-[>[+++++++++>]>]+<]>-<< >>>[<+[>]>>]<<< #endregion #region Multi_IsTrue // note 非ゼロ判定します [-[+[>]>]+<] <[[<]<]>>[>]< #endregion >> ]
解説
今回、必要になる数値は順にA,W-A,B,H-Bとなります。入力順は H,W,A,Bなので、最初にAまで読み取って、必要になったらBを読み取ってます。
今回の処理の流れを以下に示していきます。
H,W,Aの読み取り- メモリに
2をA個追加しつつWをA回デクリメント 2の先に1をW-A個追加2と1で構成される行要素のメモリに対してそれぞれ47を足して2,1を1の文字コード及び0の文字コードの変換Bの読み取りB回行要素を出力しつつ、Hをデクリメント- 行要素から
47を引く - 行要素の
2と1を反転 - 行要素に
47を加算 H-B回行要素を出力
以上となります。
X回繰り返すという作業は「Xが0かどうかを確認して0でないなら、指定動作を行い、Xをデクリメントする」によって実現できます。
(これはシングルバイトで見ればbrainfu*ckでの基本構文になります。)
先に述べたとおりマルチバイト変数の話は長くなるので省略して、ここでは、2,3,4,8について書いていきます。
メモリの末端に2,1を追加
該当コードはこの部分です。
[>] //終端に移動 ++ //値の追加 [<] //始端に移動
コメント以上のことはしていないので詳しい説明は割愛します。++にするか+にするかで 2か1かが変わります。
ここで、1,0ではなく2,1を用いてるのは、終端に上手く移動してくれないからという理由になってます。
行要素に47を加算
この部分の該当コードはこの部分です。
++++++[->--------<]>+ // 47の負数生成 [[>]<[+<]>] // 47の負数が 0 になるまで全ての要素を加算
47の負数という回りくどい書き方をしていますが、-47のことです。
本来の言語仕様では0に対するデクリメントは未定義ですが、AtCoderで採用されているコンパイラは255になると定義されてるのでありがたく使用しています。
普通に47を生成して、繰り返すこともできるのですが、-47を生成したほうがコードが短くなるので自分はこちらを好んで使います。
コード長的には誤差の範囲ではあるんですけど
ちなみに、47生成する場合は以下のコードで実現できます。
>++++++[-<++++++++>]<- [->>[+>]<[<]<]>
行要素の2と1を反転
2と1を反転と書いていますが、2と1は順に連続しているだけなので、2が続く限りその要素をデクリメントその後1が続く限りインクリメントというプログラムで実現できます。
該当コードはこの部分です
[-[>-]] // 2 である限りデクリメント + // 最初の 1 もデクリメントしてしまうのでインクリメント [+>] // 1 が続く限りデクリメント <[<] // 始端に移動
これも普段brainf*ckを書かない人だとわかりにくいと思いますが、コメント以上のことはしていません。
ちなみに記事書いてた時に気がついたんですが、1行目は-[>-]でいいと思います。
あとがき
一応今回のコードはGithubに上げました。
github.com
質問とかあれば、ここにコメントするか、Twitterでリプもらえれば反応すると思います。
今回の記事の内容じゃなくても全然大丈夫なので気軽に質問ください。
ところで、こんな記事見る人いるんですかね…(定型文)
