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でリプもらえれば反応すると思います。
今回の記事の内容じゃなくても全然大丈夫なので気軽に質問ください。
ところで、こんな記事見る人いるんですかね…(定型文)