0.はじめに

今回も、プログラミング言語はC#を使用しています。

1.問題文

整数 N が与えられます。 1 以上 N 以下の整数のうち、七五三数は何個あるでしょうか？

ここで、七五三数とは以下の条件を満たす正の整数です。

十進法で表記したとき、数字 7, 5, 3 がそれぞれ 1 回以上現れ、これら以外の数字は現れない。

2.入力例

入力

出力

3.初見の感想

1から順にひたすらループを回すのはTLEとなりそう

4.学びポイント

「数字を七五三数かどうか判定する」のではなく「作成した七五三数が上限を超えていないか判定する」
七五三数は末尾に数字をくっつける作業の繰り返しなので再帰的に書けそうです

5.コードの簡単な解説

再帰的に七五三数を作成する部分

    static int[] d = new[] { 7, 5, 3 };
    static int m1(int x, int max)
    {
        var sum = m2(x) ? 1 : 0;
        for (int i = 0; i < 3; i++)
        {
            var n = 10 * x + d[i];
            if (0 < n && n <= max)
            {
                sum += m1(n, max);
            }
        }
        return sum;
    }

七五三数かどうか判定する部分

static bool m2(int x)
    {
        var s = x.ToString();
        return s.Contains('7') && s.Contains('5') && s.Contains('3');
    }

6.全コード

using System;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var n = int.Parse(Console.ReadLine());
        var ans = m1(0, n);
        Console.WriteLine(ans);
    }

    static int[] d = new[] { 7, 5, 3 };
    static int m1(int x, int max)
    {
        var sum = m2(x) ? 1 : 0;
        for (int i = 0; i < 3; i++)
        {
            var n = 10 * x + d[i];
            if (0 < n && n <= max)
            {
                sum += m1(n, max);
            }
        }
        return sum;
    }

    static bool m2(int x)
    {
        var s = x.ToString();
        return s.Contains('7') && s.Contains('5') && s.Contains('3');
    }
}

7.最後に

最近よいペースで更新できてるのでうれしい限りです♪

ねむーの日記~AtCoderな日々~

福岡に住むプログラミング好きのブログです！

【プログラミングコンテスト】AtCoder Beginner Contest 114③

0.はじめに

1.問題文

2.入力例

3.初見の感想

4.学びポイント

5.コードの簡単な解説

6.全コード

7.最後に