今更だけども鳩祭で書いたやつうp

いや本当に今更なんですけどね。

これです。到着してからちょっと考えて閃きました。

答えについては考えたい方もいると思うので、ソースの下の方で書きます。

んで、この問題は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
ってことやね

なんかラングレス圧縮を思い浮かべるなぁ。と思いました。まる。