前回はこちらから。

さぁ今回はABC114Cを解いていこう。
頑張るぞ。

ABC114Cの問題

問題文
整数 N が与えられます。
1 以上 N 以下の整数のうち、七五三数 は何個あるでしょうか？
ここで、七五三数とは以下の条件を満たす正の整数です。
十進法で表記したとき、数字 7, 5, 3 がそれぞれ 1 回以上現れ、これら以外の数字は現れない。

制約
- 1≤N<10^9
- N は整数である。

むっ...どういう流れで解けばいいんだろう...

アルゴリズム

いつもなら、すぐに解答のアルゴリズムが思いつくのだけど、今回は手が止まってしまった...

なんとか思いついた解き方は、全パターン列挙して一個一個条件に適しているかの確認を行う方法。もう少し計算量を落としたうまい方法がありそうだなぁ...と考えてみたけどどうにも思いつかず...

いろいろ考えた挙句、3,5,7しか含まない数値をすべて列挙して、条件を満たしているか確認する方法にしてみた。

1.  現在の数値を空とする
2.  x を3,5,7として以下の手順2~6を繰り返す
3.  現在の数値の後ろに x をつけ、新たな数値を生成する
4.  x の使用済みフラグをオンにする
5.  作成された数値が N を超えていないかのチェック
6.  使用済みフラグをチェックして3,5,7が使用済みかのチェック
7.  N を超えていないかつ使用済みならば七五三数としてカウントする
8.  N を超えていないならば、手順2に戻る
9.  すべてのパターンを確認し終えたら、合計カウント数を答えとする

これを実装するには木構造がシンプルになるかな？

こんな感じに木を展開していって、生成された数値が条件満たしていたらカウントしていく流れでいいかな。

木構造のノードを表す関数を以下のように実装してみた。

// cur: 現在の数値, used: 使用済みフラグ
func node(cur, used, n int) int {
    if cur > n { // 現在の数値が N を超えていないか
	return 0
    }
    ans := 0
    if used == 7 { // 3,5,7が使用済みか
	ans++
    }
    ans += node(cur*10+3, used|1, n) // 後ろに3をつけて次のノードへ
    ans += node(cur*10+5, used|2, n) // 後ろに5をつけて次のノードへ
    ans += node(cur*10+7, used|4, n) // 後ろに7をつけて次のノードへ
    return ans
}

これは手順2~7を実装していて、現在の数値を受け取り、条件を満たしているかの確認を行っている。条件を満たしているとき、七五三数としてカウント。その後、次の数値を生成＆使用済みフラグを更新して、次のノードへGo!
返り値は自ノード以下の条件を満たしたノード数にして、ルートノードに向かってカウント結果が返るように。

こうすれば再帰的にこの関数が呼び出されて、いい感じにカウントできるはず！

あと、初めてビット列でのフラグ管理してみたけど、とってもシンプルでいいね。

解答

解答はこんな感じに。

package main

import (
    "fmt"
)

func node(cur, used, n int) int {
    if cur > n {
	return 0
    }
    ans := 0
    if used == 7 {
	ans++
    }
    ans += node(cur*10+3, used|1, n)
    ans += node(cur*10+5, used|2, n)
    ans += node(cur*10+7, used|4, n)
    return ans
}

func main() {
    var n int
    fmt.Scan(&n)
    ans := node(0, 0, n)
    fmt.Println(ans)
}

結構アルゴリズムに悩んでしまったけど、何とか解けた～。
ただの計算で求めるのではなくて、再帰処理に木構造とおもしろい処理構造を利用することができて楽しかった！

次もおもしろい問題が解きたいなぁ。
次回も頑張るぞ。