torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder SRM 568, Divison 2, Level 1 : TheSimilarNumbers

概要

二つの整数 A, B について、A <= B * 10 かつ B <= A * 10 を満たすものを「類似数」と呼ぶ。
[ lower, upper ] の範囲から、互いに類似数でないように幾つかの数を選ぶとき、最大でいくつの数を選ぶことができるか。

解法

ある数 a について、a より大きく類似数でない数は a * 10 + 1 を超える数です。
a' = a * 10 + 1 について、a' より大きく類似数でない数は、同様に a' * 10 + 1 を超える数となるので、同じ式を使って、最小の非類似数を求めることができます。
初期値として与える数についてですが、区間のできるだけ左から選ぶことで i 番目に選ばれる数を左に寄せることができるので、lower から始めます。

コード

class TheSimilarNumbers
{
public:
	int find( int lower, int upper )
	{
		int res = 0;

		for ( ; lower <= upper; lower = lower * 10 + 1 )
		{
			res++;
		}

		return res;
	}
};