2023 年の振り返り・2024 年への抱負

2023 年の振り返り

• 1 月: よく覚えていないが、実験 2 で ALU を作っていた。大変だった記憶がある。
• 2 月: 知り合いに X 線画像から乳ガンを検出する Kaggle のコンペ に一緒に出ないかと言われた。勢い良く「出る！」と言ったものの、機械学習が何もわからず、5万枚のおっぱい画像をダウンロードしただけの人になったままコンペが終了した。愚か。
• 3 月: 何をしていたか覚えておらず、おそらく何もしていない。
• 4 月: 実験 3 の CPU 作成が始まって目を回していた。
• 5 月: ひたすら Quartus Prime (CPU 作成に使っていたシミュレーション用ソフトウェア) と向き合っていた。辛かった。
• 6 月: 上旬に CPU 実験が終わる。最後の 1 ~ 2 週間はひたすらデバッグをしていて、3 時寝 8 時半起きを繰り返していた。それでもろくに終わらず、結局最終デモの日の朝 5 時までソートのアセンブリを書いていた。結局ソフト面ではソートしか書けなかったが、コンテストでは学年 2 位、歴代 4 位だった。達成感があったので、機会があれば記事を書きたい。中旬からはインタプリタ実験だったが、すでに真っ白な灰になっていたためほとんど身が入らなかった。あと、急に自作 PC ほしい！となって作った。翌月口座の残高がすごいことになっていた。
• 7 月: 引き続き真っ白な灰になっていたため、これといったことはできなかった。期末試験は散々だった…
• 8 月: 夏休みが始まって、小さなハッカソン①に出させてもらったりしていた。ここでは React を使っていたが、全く理解しないまま ChatGPT にコードを書いてもらっていた。React 歴が 2 日になった。あとは少し AHC などに出ていた。
• 9 月: 小さなハッカソン②に出たりしていた。ここでは Django REST Framework を使って簡単な認証やトーク・リアクションなどができる API を作っていた。Django (REST Framework ではない方の) は少し経験があったので、ハッカソン①よりは実感のあるコードを書けた。結果はあまり芳しくなかったが、得るものは多かった。そのあとは、軽い気持ちでベンガル語の音声認識をする Kaggle のコンペ に参加していたが、思わず熱中してしまった。
• 10 月: Kaggle のコンペの結果が出て、ビギナーズラックを引いてしまい銀メダルを獲得した。実験 4 が始まり、多層パーセプトロンを NumPy で自力実装した。
• 11 月: 引き続き実験 4 で、CNN を NumPy で自力実装した。あと、新しくバイトを始めた。
• 12 月: 8 月に何も分からないままにしていた React に急に入門したくなって、勉強していた。練習がてらお遊びサイト を作った。React に入門したら、これでいろんな API を叩いてみたいという気持ちになり、バックエンドのモチベも上がった (でも何もできていない…) 。また、atmaCup にも少し参加したが、勉強不足で何もできず、悔しかった。

2024 年への抱負

• 11 月からのバイトであまり貢献できていない気持ちが大きい。もう少し貢献したい。
• 現在は忙しくてコンペなどにあまり参加できていないが、積極的に参加したい。どちらかというと、DNN などよりも GBDT を使うコンペなどに出て勉強したい (GBDT を使えるようになればかっこいいと思うので)
• できれば院試に受かりたい。
• React をもう少し勉強してみたい。初心者の時期の楽しい気持ちを忘れずにいたい。
• バックエンドの勉強をしたい。Django だけでなく、他のフレームワークや言語でも少しは書けるようになりたい。

使わなくなった Windows PC に Linux Mint を入れてみた

0. はじめに

使わなくなった Windows10 が入っている PC*1 が下宿に眠っていたので、このまま眠らせておくのももったいないなあと思い、Linux を入れてみることにしました。以下大まかなスペックです。

• intel Core i5 第 7 世代
• メモリ 8GB
• ストレージ 256 GB

一昔前感がすごい！
ディストリビューションは Mint を入れてみることにします。
備忘録的に、取りあえずこうしたらいけた！みたいなことを書いているので、誤っている所や突っ込み所は、ご指摘頂ければ嬉しいです (それはもう！) 。

1. ISO イメージをダウンロードし、USB メモリに書き込む

ここに全部書いてました。

toshio-web.com

ISO イメージなるものをダウンロードしてきて、USB メモリに書き込んであげます*2 。

2. ややトラブル

USB メモリを PC に挿した状態で PC を起動させても Mint のインストール画面に行かなかったので、他の方法を模索します。

設定の「今すぐ再起動」のところから、BIOS を表示して USB メモリから起動します。Windows10 の場合はここに書いてありました。

pc-farm.co.jp

さっきのサイトの流れに合流したので、順調に進めます。
都市を選ぶ直前で、謎のエラーが発生します。

forums.linuxmint.com

パーティション失敗したらしいです。調べても何書いてあるか分からん！そもそも英語が読めない。。。
というか、どこをクリックしても画面が遷移しないので、再起動してみることにしました。

こんなん出た

まあ、うん……OS 吹っ飛ばして次の OS をちゃんと入れられなかったってことでしょうか……
調べても回復用のディスク作ってるよね？それで回復してね？とかばっかり出てくるんですが、あいにく今メインで使ってる PC の回復用 USB メモリしかなかった。しかも、それで回復できても Windows に戻ってまうやん！
なんか普通にさっき使った USB メモリからもう 1 回インストールすれば良いだけな気がしたので、それでやったらできました*3。

3. とりあえずいろいろいじってみる

見た目は予想以上に Windows に似てますね……実験室にある Ubuntu よりとっつきやすそう。ブラウザ (FireFox) 立ち上げて、いろいろ検索してみたりします。

日本語が打てない！！！

toshio-web.com

適当に調べたらなんかいけたけど、ここに詳しく書いてあった。またこのサイトか！システム復元の設定とかも最初の方で聞かれるので、このページ開いて待機しとけばええと思います。もうこのサイトだけ見てたら全部いけるんちゃうかな。

4. 目痛い

ブルーライトを 30 分くらい浴びると目が潰れてしまう体質のため、早くも「夜間モードみたいなの無いの？」と探し始めます。

baker-street.jugem.jp

Linux Mint 18 ですけど、これで行けました (ちゃんと見てない) 。

5. エディタとか入れる

せっかく OS 新しく入れたのにコーディングができないのでは本末転倒なので、VSCode とか Python とかを入れてみることにします。⇢ Python 入ってました。プリインストールされてるみたいです。

zenn.dev

VSCode とか gcc とかのインストールはここに全部書いてありました。実行するだけだったら、Windows のときと同じように、c_cpp_properties.json と tasks.json は書いておいて損ないかも。自分はこんな感じになりました (C++17 です) 。

各種設定ファイルを作るときの参考:
qiita.com

{
    "configurations": [
        {
            "name": "Linux",
            "includePath": [
                "${workspaceFolder}/**"
            ],
            "defines": [],
            "cStandard": "c17",
            "cppStandard": "c++17",
            "intelliSenseMode": "linux-gcc-x64",
            "compilerPath": "/usr/bin/cpp"
        }
    ],
    "version": 4
}

{
    "version": "2.0.0",
    "tasks": [
        {
            "type": "cppbuild",
            "label": "C/C++: cpp アクティブなファイルのビルド",
            "command": "/usr/bin/g++",
            "args": [
                "-D_GLIBCXX_DEBUG",
                "-fdiagnostics-color=always",
                "-g",
                "${file}",
                "-o",
                "${fileDirname}/${fileBasenameNoExtension}.out"
            ],
            "options": {
                "cwd": "${fileDirname}"
            },
            "problemMatcher": [
                "$gcc"
            ],
            "group": {
                "kind": "build",
                "isDefault": true
            },
            "detail": "コンパイラ: /usr/bin/g++"
        }
    ]
}

いろいろ入ってないからか、コンパイルが爆速です。ファイル 1 つだけやったら 1 秒とかで終わる。すごい。

実行しようとしたら許可がありませんとか言われたので、 chmod u+x ./*.out とかやったらいけました。こんなんでええんかな

*1:2018 年頃に大学生協で売られていたモデルに酷似したもの

*2:ISO イメージというのは CD とか DVD 用のアーカイブファイルらしいですが、この中身は USB メモリにも入るらしいです。すごい！

*3:てかこれに今 PC に入ってるもろもろを付け加えてバックアップ取ったのを回復用ディスクとか言うのでは？と思ってるんですが、どうなんやろ

計算機科学実験及演習2ソフトウェア (Mario AI) 遺伝的アルゴリズムによる解法

Mario AI とは？

Mario AI とは、スーパーマリオブラザーズのステージを、あらかじめ動きがプログラムされたマリオを用いてクリアしていく競技会のことで、2009 ~ 2012 年の間行われていたものです。マリオを動作させるためのプログラムは、何らかのプログラミング言語で自分で設計することになっています。
自分が大学で所属しているコースでは、このプログラムを設計・動作させるためのソースコードが配布され、自分たちでマリオの動きをプログラムしていくという課題を行います。ソースコードについては、こちらからダウンロードすることも可能なようです。

マリオAIのプレイ画面。画像中のマリオが、自分で設計したプログラムに従って動きます

Mario AI の基本的な実装法

マリオの各個体は、アニメーションの原理と同じような原理で動作します。短い時間間隔ごとにフレームが区切られて、各フレームごとにマリオの次動作 (右に動く、ジャンプするなど) をプログラムにより決定します。
具体的には、true か false が格納される 6 要素の配列 (action という名前がついています) を「マリオの動作」とします。
配列の

• 0 番目を true にすると左移動
• 1 番目を true にすると右移動
• 2 番目を true にするとしゃがむ
• 3 番目を true にするとジャンプ
• 4 番目を true にするとダッシュ & ファイヤ
• 5 番目を true にすると上移動 (自分の環境では動作しませんでした)

となっていて、この配列の要素を適宜決めたのち返してあげると、次のフレームの行動が決定されることになります*1。
下の画像は実際のプログラム中の「毎フレームの動きを決定する」部分です。action という配列の 1 番目のみを true にしているので、「毎フレームで右移動」をするマリオができあがります。目の前に落とし穴があってもジャンプはしませんし、敵がいても突進してしまうお茶目な子です。
「お茶目な子なんです！てへ」などと言ってこのプログラムを提出してしまうと留年しますので、何とかしてもう少し良いものを作らないといけません。

ただ右方向に進むだけのマリオ

シンプルなルールベースによる解法

まず考えられるのは、「目の前に落とし穴があったらジャンプする」「上に敵がいたらしゃがむ」などといった、特定の条件に対して特定の動きを割り当てるようなマリオを作ることです。
「1 マス前に障害物があるかどうか」「1 マス上、1 マス前に敵がいるかどうか」といった、周囲の環境情報を取得するための関数は、既にソースコードに用意されています。なので、実はこれを使ってあげるだけで、先ほどの右移動しかしないマリオよりもかなり良いものを作ることができます。このようなルール決めを、自分の周囲の各マスに対して行うことを考えます。

マリオの周囲 8 マスについて、障害物があるか・敵がいるかを調べ、適切な行動を割り当てる

マリオの周囲 8 マスについて、障害物や敵があるかどうかの組み合わせは、4^8 = 65536 通りあります。この 65536 通りの場合*2に対して、どのように動けばよいかを考えれば良いです。
さらに、前述の 6 種類の動き方の組み合わせを考えると、ナイーブには 2^6 = 64 通りあります。したがって、周囲 1 マスの情報を全て取得し、その情報に応じて行動するマリオは、全部で 65536 * 64 = 4194304 体存在することになります。これらを 1 体ずつ試してみて、指定されたコースをクリアできるマリオを見つけようという作戦です。

しかし、このプログラムをそのまま用いようとすると、終了までにかなり時間がかかってしまうおそれがあります。例えば、上の例ですと周囲 8 マスについて調べましたが、「周囲 8 マスだけでは足りない！」と思って、さらに 3 マス分追加で調べるとすると、なんと 268435456 体のマリオを作らなければいけなくなります。このように、周囲の情報を手に入れようとすればするだけ、指数的に手数が増えていってしまいます。

サンプルコードの遺伝的アルゴリズムによる解法

解の候補となるマリオを全て作って試す、ということが難しい場合でも、「さっき作ったマリオよりも改善された (と思われる) マリオを作り続ける」という方針を取った場合、調べるマリオの個体数が大きく減少することがあります。これを実現するための 1 つの方法として、「遺伝的アルゴリズム」というものがあります (遺伝的アルゴリズムの簡単な説明としては、このサイトが分かりやすいです) 。

各マリオは「どういった周囲の情報に対し、どのように行動するか」という対応付けを持っています。この対応付けは、マリオの各個体によって異なることから、「遺伝子」と呼ばれ、配列で実現できます。サンプルコードでも、(先ほどの解法とは少し異なりますが) 周囲の環境情報に行動を対応付ける解法を取っています。

サンプルコードの解法。周囲の環境情報を bit 列と見て 10 進数に変換し、その 10 進数から取るべき行動への対応付けを定める。

遺伝的アルゴリズムを用いると、例えば以下のようにしてコースをクリア可能なマリオを見つけることができます。

1. まず、ランダムに 100 体ほどマリオを作る。この 100 体を「1 世代目」とする。
2. 次に、現世代の 100 体それぞれにコースを走らせてみて、最も良い成績であった上位 2 体を選出する。
3. 上位 2 体については、次世代に引き継ぐ。それ以外の個体については、以下の方法で遺伝子を「組み換え」する。
   1. 選択: そのまま次世代に引き継ぐ。
   2. 交叉: 個体を 2 つ選び、遺伝子の一部を交換して次世代の個体とする。
   3. 突然変異: 個体を 1 つ選び、ランダムに遺伝子を異なるものにする。
4. 次世代を次の現世代とする。コースをクリアできる個体が見つかるまで、2. 3. 4. を繰り返す。見つかれば終了。

上位の数個体はそのまま次世代に引き継いでいることから、解は単調非減少となり、選択・交叉・突然変異により、条件を満たす解に近づいていく方法です。

サンプルコードの問題点

このようにすると無事解が求まるように思われますが、そのままサンプルコードを動かしても、うまく行きません。理由として、周囲の 1 マス単位でしか環境情報を取得していないため、情報の粒度が粗いから、というのがありそうです*3。また、シンプルに探索するマスを増加させてみたりしましたが、解の更新が低速になるだけで、あまり改善しませんでした。そこで、少し異なる方法を採用してみることにしました。

愚直解の構成

各フレームごとに取る行動は、action という 6 要素の true または false が入っている配列で表現しますが、これを 2 進数で表し、10 進数に変換することを考えます。

action の中身を 2 進数で表し、10 進数に変換する

すると、各フレームでの action は自然数で表されるので、マリオが 1 フレーム目から N フレーム目までで取る行動は、要素数 N の (0 から 63 までの) 数列で表現することができます。
すると、コースをクリアできるマリオの個体を探すという問題は、数列を探し当てる問題にすり替えることができるようになります。

次に、この数列の要素を全探索してみることを考えます。行動パターンは 2^6 = 64 通りですから、仮にフレーム数を 2000 とすると、64^2000 通りという膨大な数を全探索することになります。全探索により必ず解が見つかることは保証されますが、実験期間内にプログラムが終了せず、確実に留年します。

愚直解の改善 (1)

そこで、先ほど見た「遺伝的アルゴリズム」で、効率よく解を探索することを考えます。先ほどは「周囲の環境情報→取るべき行動」の対応付けを遺伝子としましたが、今回は「何フレーム目か→取るべき行動」の対応付けを遺伝子とします。
これによる最大の違いは、全体的な問題を部分問題に落とし込むことで、解の逐次改善が可能となることです。
例えば、m 世代目の最優秀個体が 150 フレーム目まで順調にコースを進んでいて、その後すぐに落とし穴に落ちてゲームオーバーとなっていた場合を考えます。このとき、150 フレーム目までの行動はおおむね正しいと判断して、m + 1 世代目の全個体は、その最優秀個体の 150 フレーム目までと全く同じ行動を取るように初期設定してあげれば良いということになります*4。
次に、続く 200 フレーム分の行動の改善を目指すとすると、遺伝的アルゴリズムの「交叉・突然変異」について、およそ 150 フレーム目 ~ 350 フレーム目のみで起こるとして良いです*5。このようにすると、まるで尺取り虫が進むように少しずつ解が改善されていき、解の 1 つを探し当てることができます。

愚直解を改善したプログラム

愚直解の改善 (2)

しかし、これだけではあまり高速化しません。さらに 2 つほどルールを加えてあげることを考えます。
まず 1 つ目のルールは、初期状態での動き方についてです。当初、初期状態ではランダムな動き方をするように設計していたため、同じところを行ったり来たりうろちょろし、そもそも難所にたどり着かないということがありました。これを受けて、初期状態で取れる動きは「右方向の移動・ジャンプ・およびこれらの組み合わせのみ」とします。このようにすることで、1 世代目で猪突猛進なマリオを構成し、その後少しずつ行動を改善していけるようになります。

猪突猛進に進む人

2 つ目のルールは、落とし穴のかわし方についてです。落とし穴に関しては飛び越えるの一択なのですが、これは右方向への移動とジャンプを常に行った状態にするという単調な行動です。一方で、飛び越し中はこれを行っていないと失速し、落とし穴に簡単に落ちてしまいます。この部分は遺伝的アルゴリズムを用いるまでもなく、ルールベースで行動を上書きしてあげることで、より解の探索が高速になります。

サンプルとの性能比較

サンプルのプログラムでは 20,000 世代ほど繰り返しても解が見つかりませんでした (やりすぎ) が、改善したプログラムでは 10 ~ 700 世代ほどで解が見つかりました。もっとちゃんとデータ取ればよかったかも……

*1:もちろん、右移動と左移動を同時に true するなどの無効な動きは存在します

*2:例えば、「周囲 8 マスに障害物も敵もない」という場合や、「1 マス前方に障害物があり、1 マス前方・1 マス上方に敵がいる」という場合があります

*3:例えば、0.8 マス先に敵がいる場合と、1.2 マス先に敵がいる場合では取る行動を変えた方が良いかもしれませんが、そのような調整はできません

*4:実際は、局所最適に陥っている可能性を考えて、もう 100 フレームほど戻ったところまでをコピーしています

*5:こちらでも、さらに 100 フレームほど戻ったところから交叉と突然変異を行っています

【Python】湯婆婆の業務を効率化しよう

はじめに

みなさんは、ジブリの大ヒット映画「千と千尋の神隠し」を知っていますか？
中でも特に有名なシーンは、油屋にやって来た千尋に、湯婆婆が新たに名前をつける場面でしょう。

「千尋というのかい？贅沢な名だね。今からお前の名前は千だ。いいかい、千だよ。分かったら返事をするんだ、千！」と言い、千尋から名前を奪って新しく名前をつける湯婆婆

このようにして、湯婆婆は各従業員に名前をつけることが知られています。しかしながら、大規模な営業を行う油屋において、一人ひとりに湯婆婆自身が名前をつけていては、大変なはずです。過酷を極める湯婆婆の業務の一助になりたいと思い、ここに至りました。

アイデア

最近 Python というプログラミング言語を勉強し始めたので、これを用いて効率化を図れないかと考えました。従業員一人ひとりを短い名前で管理できるような方法があればさらに良いですね。そこで、以下のように考えました。

• pandas の DataFrame を用いて、従業員名の管理を行う。
• 各従業員名が一意に定まり、さらに短い表記を用いたいため、16 進の 0 以上の整数を割り当てる。

挙動

爆速で名前を奪っては与える湯婆婆

このように、PC からの操作によって、湯婆婆の業務を効率化します。また、元の名前と与えた名前は自動で作成された CSV ファイルに格納され、この CSV ファイルは Excel などで開くことができます。

DataFrame には 10 進数で保存しています

実装

以下のように行いました。AutomatedBase16Yubaba (自動化 16 進湯婆婆) クラスを作成して、処理を行っています。
github.com

import os
import time
from math import isnan
import csv
import pandas as pd

class AutomatedBase16Yubaba:
    def __init__(self, input_file_name="aburaya_data.csv") -> None:
        self.columns = ["old_name", "new_name"]
        if not os.path.isfile(input_file_name):
            with open(input_file_name, 'w') as f:
                writer = csv.writer(f)
                writer.writerow(self.columns)
        self._aburaya_data = pd.read_csv(input_file_name, encoding="cp932")

    def explain_operation(self) -> None:
        print("\n湯婆婆: お前の名前をターミナルから標準入力でお入れ。入れ終わったら Enter をお押し\n")

    def get_next_name(self) -> int:
        if isnan(self._aburaya_data["new_name"].max()):
            return 0
        return self._aburaya_data["new_name"].max() + 1
    
    def point_out_extravagant_name(self, new_name, old_name) -> None:
        print("湯婆婆: {0}というのかい？贅沢な名だね。\n湯婆婆: 今からお前の名は{1}だ。いいかい、{1}だよ。\n湯婆婆: 分かったら返事をするんだ、{1}！".format(old_name, hex(new_name)))

    def is_old_name_valid(self, old_name) -> bool:
        space_deleted_name = old_name.replace(" ", "").replace("　", "").replace("\t", "")
        if not space_deleted_name:
            print("ちゃんと名前をお入れ！")
            return False
        return True
    
    def rename(self, old_name, input_file_name="aburaya_data.csv") -> None:
        new_name = self.get_next_name()
        self.point_out_extravagant_name(new_name, old_name)
        new_clerk = pd.DataFrame({
            "old_name": [old_name],
            "new_name": [new_name],
        })
        self._aburaya_data = pd.concat([self._aburaya_data, new_clerk], ignore_index=True)
        self._aburaya_data.to_csv(input_file_name, index=False, encoding="cp932")
        print("\n湯婆婆: 次の方～")

def main() -> None:
    yubaba = AutomatedBase16Yubaba()
    yubaba.explain_operation()
    while True:
        old_name = input("あなた: ")
        if not yubaba.is_old_name_valid(old_name):
            continue
        yubaba.rename(old_name)
        time.sleep(0.2)

if __name__ == "__main__":
    main()

反省点

本来であれば、Esc キーを押したときなどに、DataFrame をまとめて CSV ファイルに書き込むようにしたかったのですが、Esc などを感知するキー入力と日本語標準入力の相性が悪く、挫折してしまいました (今のところ、とても効率の悪いコードです……)。blessedなどのモジュールを使えば可能なのかもしれませんが、ご存じの方いらっしゃれば、教えて頂けると幸いです。

N 以下の正整数のうち、各桁に特定の数字のみを含むものの数を数える

はじめに

この問題を解くことが幼少期*1からの夢でした。2021年度後期で『アルゴリズムとデータ構造入門』を履修し、少しアルゴリズムに興味が持てたため、プログラムを作成してこの問題を解いてみようと思います。使用言語は一応 C++ としています。

そもそもどういう問題？

タイトルの通りですが、例えば で、特定の (使ってよい) 数字が の場合、条件を満たす数は「 以下で しか桁に現れない数」ということで、 の 種類となります。よって答は です。そんな感じです。

愚直にやってみる (解法1)

まず初めに思いつくのは、

1. 以下の正整数をfor文で全列挙する
2. 全列挙した各整数の各桁を取り出し、使用可能な数字かどうか確かめる

という方法がありそうです。プログラムの一例としては、以下のようなものがあると思います。

#include <iostream>
#include <vector>

using namespace std;

long long digits_restricted_number(long long x, vector<int> &specified_digit) {
    // 返り値
    long long ret = 0; 

    // x 以下の正整数 i を全走査
    for (long long i = 1; i <= x; i++) {
        bool ok = true;
        long long j = i;
        while (j) {
            // i の各桁を順番に取り出していく
            long long n = j % 10;
            bool is_n_included = false;
            // 今見ている i の桁が specified_digit に含まれていればよい
            for (auto &e : specified_digit) {
                if (n == e) {
                    is_n_included = true;
                }
            }
            if (!is_n_included) {
                ok = false;
            }
            j /= 10;
        }
        // i の各桁がすべて specified_digit に含まれていれば、ret を 1 増やす
        if (ok) ret++;
    }

    return ret;
}

int main() {
    // 標準入力
    long long N; cin >> N;
    int n; cin >> n;

    vector<int> specified_digit(n);
    for (int i = 0; i < n; i++) {
        cin >> specified_digit[i];
    }

    cout << digits_restricted_number(N, specified_digit) << endl;

    return 0;
}

時間計算量ですが、 個の各整数の各桁について調べ、さらにその中で使用可能な数字を線形探索しているため、使用可能な数字の種類数 (正とします) を として、 くらいです*2。
だとしても少なくとも 回の計算ステップがあり、現実的な計算時間とはならなそうで、悲しくなってしまいました。

もうちょっと考えてみる (解法2)

桁ごとに考えてみれば、もう少し良い解法が思いつくかもしれません。
動的計画法 の1つである Digit DP*3 というものを用いれば、この問題がもう少し高速に解けそうです。動的計画法では使用する配列の名前を慣習的に dp とするようなので、自分もそうしてみました。
0 を使用する数字に含めるか否かの場合分けが面倒でした。

#include <iostream>
#include <vector>

using namespace std;

long long digits_restricted_number(long long x, vector<int> &specified_digit) {
    // specified_digit に 0 が含まれているかチェック
    bool is_zero_permitted = false;
    for (auto &i : specified_digit) {
        if (i == 0) {
            is_zero_permitted = true;
        }
    }
    // どのみち 0 はゼロ埋めに使うので、specified_digit に入れておく
    if (!is_zero_permitted) specified_digit.push_back(0);

    string x_str = to_string(x);
    int digit = int(x_str.size());

    // dp[i][j][k] :
    // 上から i 桁目まで見た時点で、
    // x ギリギリである ⇒ j = 1, でない ⇒ j = 0
    // 今までの桁で 0 以外を使った ⇒ k = 1, 使っていない ⇒ k = 0
    vector<vector<vector<long long>>> dp(digit+1, vector<vector<long long>>(2, vector<long long>(2, 0)));

    dp[0][0][0] = 1;
    for (int dgt = 0; dgt < digit; dgt++) {
        int cur = x_str[dgt] - '0';
        for (int is_less = 0; is_less < 2; is_less++) {
            for (int is_nonzero_included = 0; is_nonzero_included < 2; is_nonzero_included++) {
                for (auto &nxt : specified_digit) {

                    int is_less_new = is_less;
                    int is_nonzero_included_new = is_nonzero_included;

                    if (!is_less and nxt < cur) {
                        is_less_new = 1;
                    }
                    if (nxt != 0) {
                        is_nonzero_included_new = 1;
                    }

                    if (!is_less and nxt > cur) {
                        continue;
                    }
                    if (!is_zero_permitted and is_nonzero_included and nxt == 0) {
                        continue;
                    }
                    dp[dgt+1][is_less_new][is_nonzero_included_new] += dp[dgt][is_less][is_nonzero_included];
                }
            }
        }
    }

    long long ret = 0;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            ret += dp[digit][i][j];
        }
    }

    ret--;

    return ret;
}

int main() {
    // 標準入力
    long long N; cin >> N;
    int n; cin >> n;

    vector<int> specified_digit(n);
    for (int i = 0; i < n; i++) {
        cin >> specified_digit[i];
    }

    cout << digits_restricted_number(N, specified_digit) << endl;

    return 0;
}

時間計算量は、各桁に対して使用可能な数字を線形探索するため、 *4 となり、かなり高速になりました*5。

おわりに

意識の底にあった問題をついに解くことができ (たと思われ) 、少しうれしい気持ちになっています。作成したプログラムはかなり乱雑なものとなってしまいました。記事内に誤りがあれば、教えて頂けますと幸いです。
また、進法を用いた考え方などもできそうです。またゆっくり考えてみたいと思っています。

*1:2021年9月下旬

*2:あやしい。

*3:よくわかっていません。

*4:あやしい。

*5:おおざっぱに考えると、 倍高速になっているので、 とすると兆倍くらい速くなりました (テキトーですみません)。