はじめに

競技プログラミング、AtCoder Beginner Contest 114
C - 755
言語はC#
何かあればTwitter→@pirorirori_n712まで

問題

問題文

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

制約

・1≤N<10~9
・Nは整数である。

入力

入力は以下の形式で標準入力から与えられる。

N

出力

1以上N以下の七五三数の個数を出力せよ。

解き方

こちらの解き方を参考にしています。

atcoder.jp

Nの桁数以下の
3,5,7で構成される数字を全列挙し、
その中で3,5,7をすべて含んでいる、
かつN以下の数字の数を数えます。

数字を列挙する

3,5,7で構成される数字を
どうすれば全列挙できるかを考えます。

10進数を3進数に直していく方法ができそうなので
それを使うことにします。

10進数から2進数へ直す方法
シスアド講座 10進数と2進数の相互変換

ループ

二重でループを回し、
3,5,7で構成される数字を作成していきます。
（3,5,7が全て入っていない数字、
例えば355なども一緒に作成しています。）

数字は文字列として作成し、
一文字ずつ「3,5,7」のどれかを
文字列に足して構成していくとします。
（”3”+”5”+”7”＝”357”）

外側のループは桁数（0～Nの桁）、
内側のループは各桁に「3,5,7」の三通りの可能性があるので
（3^{外側のループ+1}）数ぶん回します。

考え方としては、
外側のループが0のとき→桁数が1のとき（3,5,7）
外側のループが1のとき→桁数が2のとき（35,37,53…）
というように桁数で場合分けしながら
数字を作成していくようなイメージです。

内側のループの中では、
桁数分の数字を文字列として足していけるように
外側のループで指定された回数ぶんwhileで数字を繋げます。

桁はN以下のものを数えれば十分なので、
N桁以下で設定しています。

var N = Int64.Parse(Console.ReadLine());
var nKeta = Math.Log10(N) + 1;
//桁は最大でもNの桁数にしかならない
for (int i = 0; i < nKeta; ++i)
{
      //i+1桁の数字は、3,5,7の3文字しか数字が使えないので3^(i+1)パターンしか存在しないはず
      for (int j = 0; j < Math.Pow(3, i + 1); ++j)
      {
             var keta = 0;
             //i+1桁（0桁の数字は不可）の数字を作りたいので、桁がi+1になるまでループを回す
             while (keta<i+1) {
             //ここで数字を作成
             keta++;
             }
      }
}

数字の作成

whileの中では、
桁数に3,5,7をそれぞれはめ込んでいきます。
内側のループは3^{外側のループ+1}ぶん回ります。

この10進数を3進数に直し、
出てくる「0,1,2」という数字を
「3,5,7」に当てはめます。

        var N = Int64.Parse(Console.ReadLine());
        var nKeta = Math.Log10(N)+1;
        for (int i=0;i<nKeta;++i)
        {
            for (int j=0;j<Math.Pow(3,i+1);++j) {
 
                var num = j;
                var keta = 0;
                var amari = 0;
                var suji = "";
 
                while (keta<i+1) {
                    //10進数を3進数に直していく
                    //3進数の0,1,2をそれぞれ3,5,7に当てはめ直す
                    amari = num % 3;
                    switch (amari)
                    {
                        case 0: suji += "3"; break;
                        case 1: suji += "5"; break;
                        case 2: suji += "7"; break;
                    }
                    num /= 3;
                    keta++;
                }
            }
        }

条件に沿う数字を数える

上で作成した数字がN以下でかつ、
3,5,7をすべて含む数字であることを確認し、
条件に当てはまれば答えに1を足していきます。

        var N = Int64.Parse(Console.ReadLine());
        var nKeta = Math.Log10(N)+1;
        var ans = 0; //答え格納用変数
        for (int i=0;i<nKeta;++i)
        {
            for (int j=0;j<Math.Pow(3,i+1);++j) {
 
                var num = j;
                var keta = 0;
                var amari = 0;
                var suji = "";
 
                while (keta<i+1) {
                    amari = num % 3;
                    switch (amari)
                    {
                        case 0: suji += "3"; break;
                        case 1: suji += "5"; break;
                        case 2: suji += "7"; break;
                    }
                    num /= 3;
                    keta++;
                }
                //答えが条件に当てはまるかどうか確かめる
                //当てはまれば、答えに1を足す
                if (Int64.Parse(suji) <= N && suji.Contains("3") && suji.Contains("5") && suji.Contains("7")) ans++;
            }
        }

最後に答えを出力します。

全体のコード

using System;
using System.Linq;
using System.Collections.Generic;

class Cmondai
{
    static void Main()
    {
        var N = Int64.Parse(Console.ReadLine());
        var nKeta = Math.Log10(N)+1;
        var ans = 0;
        for (int i=0;i<nKeta;++i)
        {
            for (int j=0;j<Math.Pow(3,i+1);++j) {

                var num = j;
                var keta = 0;
                var amari = 0;
                var suji = "";

                while (keta<i+1) {
                    amari = num % 3;
                    switch (amari)
                    {
                        case 0: suji += "3"; break;
                        case 1: suji += "5"; break;
                        case 2: suji += "7"; break;
                    }
                    num /= 3;
                    keta++;
                }
                if (Int64.Parse(suji) <= N && suji.Contains("3") && suji.Contains("5") && suji.Contains("7")) ans++;
            }
        }
        Console.WriteLine(ans);
    }
}