SRM 354 500pt : RemissiveSwaps

keyword

探索　C++

問題概要

N(<10^6)が与えられる。Nを10進表現したとき、0でない2つの桁を選んで、数字を1減らして交換する。この作業を任意回繰り替えしてできる最大の数を求める問題。

解法

桁数は増えないので到達可能な数はMAX_N以下。また、各数から到達可能な数の列挙はO((log N)^2)でできる。なのでDFSなりBFSなりで全ての到達可能なノードを調べられるので、最大のものを返せばよい。

感想

再帰関数でDFSしたけどスタックオーバーフローの可能性とか真面目に考えてなかった。結果的に大丈夫だったけど、可能ならやっぱり検証すべきだろう。

#include <string.h>
#include <stdio.h>
const int MAX_N = 10000009;
bool visited[MAX_N];

int tens[20];

struct RemissiveSwaps {

	int findMaximum(int N) {
		tens[0] = 1;
		for(int i=1; i<20; i++){
			tens[i] = tens[i-1]*10;
		}
		dfs(N);
		int ret = 0;
		for(int i=0; i<MAX_N; i++)if(visited[i]) ret = i;
		return ret;
	}

	void dfs(int n){
		visited[n] = true;
		char buf[12];
		sprintf(buf, "%d", n);
		int L = strlen(buf);
		for(int i=0; buf[i]; i++)if(buf[i] > '0'){
			for(int j=i+1; buf[j]; j++)if(buf[j] > '0'){
				int x = n + tens[L-i-1]*(buf[j] - buf[i] - 1) + tens[L-j-1]*(buf[i] - buf[j] - 1);
				if(!visited[x]){
					dfs(x);
				}
			}
		}
	}
};