CPSCO2019 Session1 B問題 をbrainf*ckで解く(前編)
こんにちは、先日はにーまさん主催の初心者向け競プロ合宿CPSCOに参加してきました。 主催してくれたはにーまさんには感謝しています。
細かいSessionの話とかはほかの人に任せて、今回はSession1のB問題に関して書いていきます。
使用言語はBreakbrainf*ckです。
brainf*ckの言語に関して下ない人向けに、ざっくり説明すると。
「コンパイラのサイズが最小になるように作られた言語」です。
以下はbrainf*ckの予約語一覧です。
| 予約語 | C++ の対応コード | 説明 |
|---|---|---|
+ |
array[ptr]++; |
現在のポインタが指す値をインクリメントする |
- |
array[ptr]--; |
現在のポインタが指す値をデクリメントする |
> |
ptr++; |
ポインタをインクリメントする |
< |
ptr--; |
ポインタをデクリメントする |
[ |
while(array[ptr]){ |
現在のポインタが指す値が0なら対応する]に飛ぶ |
] |
} |
現在のポインタが指す値が0でないなら対応する[に飛ぶ |
, |
array[ptr] = readchar(); |
標準入力から1文字を受け取りそのASCII文字コードを現在のポインタに格納 |
. |
putchar(array[ptr]); |
現在のポインタが指す値をASCII文字コードとして出力する |
わかりやすさのためにC++に置換したときの対応コードを書いておきました。
細かい仕様とか知りたい方は適当にググってもらえればと思います。（brainf*ckの基礎的な話もまとめたいなと思わなくはない。)
さて、本題の問題に関してですが、 a~zの各文字が何回出てくるかを見て、0でない要素がすべて同じであればOKとなります。（解説のまんま） 普通の言語であれば入力を文字列で受け取ってから処理しますが、brainf*ckだとめんどくさいので(そもそも配列が面倒)、 1文字ずつ受け取りながら処理をしていきます。
C++でこういうイメージです。
unsigned char letter = getchar(); letter -='\n'; // -=10 while(letter){ letter -= ('a'-'\n'); // -= 87; data[letter]++; letter = getchar(); letter -='\n'; }
これをもとにbfainf*ckで書きます。
ただし、制約の関係上256以上の値をとる可能性はありますが、brainf*ckで256以上を扱うのは非常に面倒なため、
今回は気にしないことにしました。
具体的に言うと、256nは存在しない文字と同列として扱われ、256n+a (0<a<256) は a と同じ文字数として扱われます。
テストケースによってはWAが生えますが、無いと信じて実装しました。(実際になかったです。)
, // letter = getchar(); ---------- // letter -= 10; [ // while(letter){ ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ------- // letter -= 87; [- > >>>[>>>]+[<<<]<]> >>>[>>>]<<+>> <<<[-<<<] < // data[letter]++; , // letter = getchar(); ---------- // letter -= 10; ] // }
上記のコードはコメントっぽく書いてる部分の予約語にも反応するため、コピペしただけではうまくいきません。 (コメントを削除するとうまく動きます)
data[letter]++; 以外の部分は何となく理解できるのではないかと思います。
data[letter]++; 部分の細かい説明ですが、まず前提条件として、「brainf*ckで配列の操作は容易ではない」ものがあります。
理由としては、指定数ポインタを移動させることができないので、「ポインタを１移動させる」を指定数行うことになります。 ここで登場するのが「for文」となります。(余談ですが、brainf*ckにおいてfor文は最も基礎的な構文です。)
そして 、brain*ckのfor文の欠点として、 for分の内部の処理が終わった段階で、初期位置(繰り返し回数が格納されているポインタ)まで戻ってくる必要があるため、for分でのポインタを指定数ずらすという命令は不可能になります。
そこで、data配列を以下のような構造体をで定義することを想定します。
struct Cnt { unsigned char Count; bool IsEmpty; bool PtrMarker; }; struct Cnt data[26];
(IsEmptyは前編では使用していません。)
そして、data[n].Count++;を行うコードを以下のように想定します。
while(n > 0){ n--; int pos = 0; while(data[pos].PtrMarker) pos++; data[pos].PtrMarker =1; while(data[pos].PtrMarker) pos--; pos++; } while(data[pos].Count++) pos++; data[pos].Count ++; while(data[pos].PtrMarker){ data[pos].PtrMarker = 0; pos --; }
ここでposはポインタを示すので、実際にどこかに値が格納されることはないです。
また、ループの終わりに0になっている必要があり、このコードではそれを実現しています。
また、察しのいい人は気づくかもしれませんが data[-1]の領域を参照しますが、data[-1]相当のメモリも存在しているので、参照しても、エラーも何も起きません。
これをbrainf*ckで書くと
[ //while(n > 0){ - // n--; > // int pos = -1; ( data[-1].PtrMarker 相当の場所にポインタを移動) >>> // pos = 0; ( data[0].PtrMarker 相当の場所にポインタを移動) [>>>] // while(data[pos].PtrMarker) pos++; + // data[pos].PtrMarker =1; [<<<] // while(data[pos].PtrMarker) pos--; < // ( ループカウンタの部分にポインタを戻す ) ] //} > // int pos = -1; ( data[-1].PtrMarker 相当の場所にポインタを移動) >>> // pos = 0; ( data[0].PtrMarker 相当の場所にポインタを移動) [>>>] // while(data[pos].PtrMarker) pos++; <<+>> // data[pos].Count =1; <<< // ( data[pos-1].PtrMarker 相当の場所にポインタを移動 ) [ // while(data[pos].PtrMarker){ - // data[pos].PtrMarker = 0; <<< // pos --; ] // } < // ( ループカウンタの部分にポインタを戻す )
このコードの条件として、繰り返し回数が格納されているのは data[-2].PtrMarker相当の場所で、 data[-1]相当の場所は全て0になっています。
この説明で理解できるかどうかはわかりませんが（きっと理解できる人はひと握りしかいない)、理解したものとして進めます。
ここまでのコードで、各文字が何文字あるかを配列に格納することができました。
前編はここまでにします。
すべての文字数が同じかどうかの判別は後編としていつか書きます。
書きました。
