今更だけども鳩祭で書いたやつうp
いや本当に今更なんですけどね。
1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, です!続き分かりますか(*´・_・`*)
— PMOB@鳩祭 (@PMOB_) 2016年11月6日
これです。到着してからちょっと考えて閃きました。
答えについては考えたい方もいると思うので、ソースの下の方で書きます。
んで、この問題は30回目の操作後の桁数を求めるというものだった模様なので、それを求めるためにこのソースを書いたわけです。言語はC++。マクロは適当に読み替えて(丸投げstyle)
#include <iostream> #include <string> #include <algorithm> #include <map> #include <vector> using namespace std; #define debug(x) cout<<#x<<": "<<x<<endl #define rep(i,a,b) for(int i=a;i<b;i++) #define PB push_back typedef long long ll; int main(){ vector <int> now,next; int tmp,p,n,m; cin >> n >> m; rep(i,0,n){ cin >> tmp; now.PB(tmp); } rep(i,0,n)cout<<now[i]; cout <<endl; rep(i,0,m){ tmp = now[0]; p=0; rep(j,0,now.size()){ if(now[j]!=tmp){ next.PB(p); next.PB(now[j-1]); p=1; tmp=now[j]; } else{ p++; } } if(p!=0){ next.PB(p); next.PB(tmp); } rep(j,0,next.size())cout << next[j]; cout <<endl; now = next; next.clear(); cout << i+2 <<"digits :"<<now.size()<<endl; } return 0; }
んで、この問題なんなのさ?という解説。
look-and-say sequenceとかいうらしい。見て言う数列とな。
規則性は単純で、1ステップごとに直前の数列で同じ数字が連続している個数とその数字をどんどん出していく。
例を挙げると
1145141919810100081
の次の数列は
21 14 15 11 14 19 18 11 10 30 18 11
だし、もっと単純な例なら
111112222333445
だったら
51 42 33 24 15
ってことやね
なんかラングレス圧縮を思い浮かべるなぁ。と思いました。まる。
b.b.k.k.b.k.k.を出力
+++++++++++[>+++++++++>++++++++++>++++<<<-]>->--->++>+#初期化 >>>,#ループ回数の入力(仮) [#メインループ <[-<<<<<.>>.<.>.<.>.>+>>]#"b.k.k."を出力 <[-<<<.>.<.>.>>>+<]#"k.k."を出力 <[-<<<.>>.<<.>>.>>+<]#"b.b."を出力 >>>-]#イテレータのディクリメント
b.b.k.k.b.k.k.を出力し続けるコードを書いた。
ループ回数の入力はASCIIコードの数値でしか表せない適当仕様
メモリの配置としては
初期化に使うカウンタ | 'b' | 'k' | '.' | b.b.フラグ | k.k.フラグ | b.k.k.フラグ | イテレータ
となっている。
初期化時点ではb.b.フラグに1が入った状態になっている。
初期化を行った後、イテレータにループ回数を入力し、ループへ入る。
ループ内ではフラグが立っているかを一つづつ確認し、立っているフラグごとに
フラグを0にし、
"b.b.", "k.k.", "b.k.k."それぞれの出力処理を行い
次に出力するべき文字列のフラグを立ててから処理を終えてループに戻る。
b.b.k.k.b.k.k.を出力していくだけならば、もっと汚い感じで書けば短いだろうが、綺麗に書くことを目的としているので今回はこのようになった。