引き続きAtCoderで遊んでます。さっくです。
今日はAtCoderに出てきた「753数」を紹介します。
ある自然数が「753数」であるとは
- の各桁が7,5,3のいずれかである・・・(1)
- 7,5,3がそれぞれ少なくとも1回以上に含まれる・・・(2)
この2つの条件を満たすことを言います。
例えば753や37575、55555537などが753数です。
一方、7775や35、555は753数ではありません。
AtCoderでは
「与えられた自然数に対して、以下の753数の個数を求めよ」
という問題でした。
今回は少し問題を変えて、
「桁の753数の個数を求めよ」
という問題について考えてみたいと思います。
まず、上の条件(1)を満たし、条件(2)を満たさない数を「準753数」と呼ぶことにしましょう。
桁の準753数は個ですね。
なぜなら、各桁には7,5,3の3通りの数字の選び方があるからです。
twitter上で見かけたある方のつぶやきでベン図の有用性を改めて認識したので、
ベン図を描いてみます。
求めたいのはグレーの部分(A)です。
です。3も5も7も含まない準753数は0個。
です。3しか含まない桁の753数は1個です。
です。例えば7含まない桁の753数は個です。
したがって
です。
ゆえに桁の753数は個でした。
これをうまく使って、与えられた自然数に対して、以下の753数の個数を高速に求められないかなぁ。などと考えていました。