CODE FESTIVAL 2014 上海 : A - Lock

Code Festivalの上海大会オープンに参加。
本選オープンに続き、早解き逃げ切りだけで好順位。
http://code-festival-2014-china-open.contest.atcoder.jp/tasks/code_festival_china_a

問題

N桁の数字の錠前がある。
１回の操作で、１つの桁の数字を加算または減算できる。

全部の桁が0の状態から初めて、全部の数字を列挙する場合、最低何回操作が必要か。
またその際の手順の例を示せ。

解法

全ての数字を重複なく列挙できる。
すなわち操作回数は(10^N)-1である。

手順の方法だが、(N-1)桁の手順がXXXXX～YYYYYであるとすると

XXXXX0
...
YYYYY0
YYYYY1
...
XXXXX1
XXXXX2
...

とこの手順を毎回反転させながら10回繰り返し、１回分ごとに末尾に0,1,2...を付与していけば良い。

int N;
string S[100000];
int p=1;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	FOR(x,N) {
		for(j=1;j<10;j++) {
			FOR(i,p) {
				if(j%2==0) S[j*p+i]=S[i];
				else S[j*p+i]=S[p-1-i];
			}
		}
		FOR(j,10) FOR(i,p) S[j*p+i]+='0'+j;
		p*=10;
	}
	
	cout<<p-1<<endl;
	FOR(i,p) cout<<S[i]<<endl;
}

まとめ

本番一瞬迷ったけど、すぐ思いつけた。
とはいえCode Festivalの他の回に比べるとAから難しめ。