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

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

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

就活の飛行機を抑えるのに必死です、ねむーです。

今回はAtCoder(https://atcoder.jp/contests/abc114)にて開催されました、AtCoder Beginner Contest 114の第3問「C - 755」の問題と僕との戦闘記です。

0.はじめに

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

1.問題文

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

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

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

2.入力例

入力

575

出力

4

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.最後に

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