京都大学を卒業しました (文学部3年+工学部情報学科4年)
概要
京都大学文学部に入学し2年間勉強した後、1年間休学して2021年に京都大学工学部情報学科に入学しました。2025年3月24日をもって卒業しました。 高校・大学生活の振り返りを書いています。
高校時代
中学からの惰性で水泳部に入りました。特に優れた選手ではありませんでしたが、部活ばかりに打ち込んでいました。入学してからは勉強にはあまり手を付けなかったため、物理の斜方投射 (斜めに物体を投げる運動) や数学の三角比が理解できませんでした。自分には理系は向いていないと感じたため、1年生の中ごろにして文系を選択することを決心しました。
学年が進むにつれ数学は楽しくなったものの、理系に転向することはありませんでした。卒業後の就職も少し考えていましたが、結局大学の文系学部を受験することになりました。当時は英語に興味があったので、大阪大学の外国語学部を検討していました。しかし3年生になって、言語の運用を勉強したいのか、言語の構造を勉強したいのかで悩み、後者を選択して京都大学の文学部に進学することになりました。
学部時代 (文学部)
文学部では、言語学 (特に、音声学や音韻論) を勉強・研究することに決めていました。ところが、講義開始から2週間経ったころ、勉強内容に全く興味を持てないことに気づきました。 当時の自分は、言語学で発見されたキャッチーな現象を鑑賞しているのみで、そういった現象はどのようなプロセスを経て見つけられるのか、またそのプロセスにどの程度の苦労が伴うのかを全く理解しようとしていませんでした。そのため、自分で手を動かして能動的な学びを得ることはなく、不完全燃焼していました。
そのまま2年間過ごしていましたが、2回生の後期ごろには文学部から離れたいと感じていました。いろいろな思いが積もっていたのですが、決定打となったのは英語で詠む俳句を扱う講義でのことでした。自分の解釈が誤りと伝えられた際に、その理由が明確に説明されず、もやもやした気持ちが残ることが何度もありました。当時は「作品は、それ自体の内にすべてを説明する責任を持つべきで、解釈が一意に定まらないのは非合理的だ」と考えていたことを覚えています。
法学で過去の判例から解釈を作り上げるのと同じように、文学でも過去に触れた文章から解釈を作り上げていく面はあるでしょう。したがって、自分がスタンダードな解釈をできなかったのは、単純にインプット不足に起因するものだったということになります。 これまでの蓄積を活かして工夫を重ねることで、よりスタンダードな解釈やより洗練された表現が可能になるのは何においても当然のことといえますが、当時の自分はこのことに気づかず、このまま学びを続けて良いものかと悩んでいました。
それからというもの、自分が本当にしたいことを考えていましたが、あるとき言語を機械的に処理することに強く惹かれました。特に、音声認識がどのように行われているのかに興味を持ったため、今後の学びの方針について言語学研究室の先生に相談してみました。すると、「このような分野で言語学の知識を援用することはほとんどなく、大量のデータを活用して処理する時代になっている」とのことで、文学部で適切な指導を受けることは難しいと判断しました。 周囲の友だちや先輩にも話を伺ったところ、情報系が最適であるとの結論に至り、再受験を決心しました。受験する大学も少し調べましたが、通い慣れていて雰囲気も好きな京都大学が良さそうということになりました。 他の選択肢としては総合人間学部への転学部がありましたが、特色入試という方式で小論文を2つ3つ書いて文学部に合格したため、入試科目の不一致から認められませんでした。
再受験
両親に再受験の相談をしたところ、文学部を卒業してからでも良いのではと諭されました。しかしながら、一刻も早く状況を打破したかったため、ぜひ来年度受験したいと説得しました。Word や PowerPoint で資料を色々作って帰省したことを覚えています。その結果、「1年だけかけるのであれば再受験して良い、その間は休学し、予備校に入れてやるから本気でやれ」ということになりました。 このときの両親の提言には感謝してもしきれません。
物理や化学・数学Ⅲはほとんど勉強したことがありませんでしたが、予備校で新しいことを学ぶのは楽しかったです。プレッシャーはあったものの、無事工学部情報学科に合格できました。
学部時代 (工学部情報学科)
新型コロナウイルスの影響で、講義開始後2週間程度でオンライン体制に移行しました。この期間に非常に大きな価値があり、多くの友だちと知り合うことができました。2~3学年上であるにもかかわらずフレンドリーに接してくれた学科同期は、昔も今もありがたい存在であり続けています。今でもたまに年齢イジリをされますが……。学部では、苦労をいとわず積極的に手を動かすことの重要さ、また多方面での同期の優秀さを身近に感じることができ、とても意義のある日々を過ごすことができました。
学部生活において、自分の生活の指針となっている言葉が1つあります。 1回生前期の少人数講義でのことだったのですが、4回生配当のセミナーに参加する機会があり、当時 PFN に所属されていた比戸さんが講演にいらっしゃっていました。 ためになることは多くありましたが、中でも講演の終盤で「学生時代の時間は有限。どのカードを切るかはよく考えたほうが良い」とおっしゃっていたのを、今でも鮮明に覚えています。 自分は入学以前に目立った成果を上げたわけでもなく、際立った能力もなかったため、4回生での研究開始までに何をしたものか悩んでいました。要領の良さや物事の理解の深さでは周囲に遅れを取っている自覚があり、学科のカリキュラムを実感を持って学べたとはとても言い難いですが、この言葉を時たま思い出していたことで、自分にしては有意義な4年間になったと感じています。
入学当初は Windows と Mac の違いも理解していなかった自分が、学生実験やアルバイト・趣味のコーディングを通じてある程度の規模のプログラムを書けるようになったことは、大きな財産の1つになりました。エンジニアのアルバイトは、お金をもらいながらスキルを身につけられる点で、貴重な経験になると思います。学業との両立には注意する必要がありますが。
研究室は色々迷いましたが、入学当時からの目標通り音声メディア研究室に所属し、音声認識を勉強 (とても今のレベルでは研究とは言えない) することになりました。指導教員の河原先生はいつでも相談に乗ってくださいますし、修士・博士・研究員の方々のお話もためになることばかりです。他の先生方・先輩方・同期の人たちも仲良く接してくださって、温かい研究室だと思います。自分が研究が好きなのかは未だ分からず、単に手を動かしているのが好きなだけかもしれません。しかし、卒業研究と称して行っていた活動は楽しく、今後も学術活動は続けられたらと願っています。
学士論文の執筆と学会への投稿を経て、現在は息抜きのため周囲の人たちと食事や旅行に行ったりしていますが、こうはしていられない、もっと研究のための時間を取りたいという気持ちが日増しに強くなってきています。春休みが明けた後は生活スタイルや予定の立て方を見直し、自分の使いうる時間を有効活用していきたいです。 4月からも同じ研究室 (情報学研究科知能情報学コース 音声メディア研究室) ですが、修士課程の学生らしい実感のある学びができるよう、邁進していきます。
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 年への抱負
使わなくなった Windows PC に Linux Mint を入れてみた
0. はじめに
使わなくなった Windows10 が入っている PC*1 が下宿に眠っていたので、このまま眠らせておくのももったいないなあと思い、Linux を入れてみることにしました。以下大まかなスペックです。
一昔前感がすごい！
ディストリビューションは Mint を入れてみることにします。
備忘録的に、取りあえずこうしたらいけた！みたいなことを書いているので、誤っている所や突っ込み所は、ご指摘頂ければ嬉しいです (それはもう！) 。
2. ややトラブル
USB メモリを PC に挿した状態で PC を起動させても Mint のインストール画面に行かなかったので、他の方法を模索します。
設定の「今すぐ再起動」のところから、BIOS を表示して USB メモリから起動します。Windows10 の場合はここに書いてありました。
さっきのサイトの流れに合流したので、順調に進めます。
都市を選ぶ直前で、謎のエラーが発生します。
パーティション失敗したらしいです。調べても何書いてあるか分からん！そもそも英語が読めない。。。
というか、どこをクリックしても画面が遷移しないので、再起動してみることにしました。
まあ、うん……OS 吹っ飛ばして次の OS をちゃんと入れられなかったってことでしょうか……
調べても回復用のディスク作ってるよね？それで回復してね？とかばっかり出てくるんですが、あいにく今メインで使ってる PC の回復用 USB メモリしかなかった。しかも、それで回復できても Windows に戻ってまうやん！
なんか普通にさっき使った USB メモリからもう 1 回インストールすれば良いだけな気がしたので、それでやったらできました*3。
3. とりあえずいろいろいじってみる
見た目は予想以上に Windows に似てますね……実験室にある Ubuntu よりとっつきやすそう。ブラウザ (FireFox) 立ち上げて、いろいろ検索してみたりします。
日本語が打てない！！！
適当に調べたらなんかいけたけど、ここに詳しく書いてあった。またこのサイトか！システム復元の設定とかも最初の方で聞かれるので、このページ開いて待機しとけばええと思います。もうこのサイトだけ見てたら全部いけるんちゃうかな。
4. 目痛い
ブルーライトを 30 分くらい浴びると目が潰れてしまう体質のため、早くも「夜間モードみたいなの無いの？」と探し始めます。
Linux Mint 18 ですけど、これで行けました (ちゃんと見てない) 。
5. エディタとか入れる
せっかく OS 新しく入れたのにコーディングができないのでは本末転倒なので、VSCode とか Python とかを入れてみることにします。⇢ Python 入ってました。プリインストールされてるみたいです。
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 とかやったらいけました。こんなんでええんかな
計算機科学実験及演習2ソフトウェア (Mario AI) 遺伝的アルゴリズムによる解法
- Mario AI とは？
- Mario AI の基本的な実装法
- シンプルなルールベースによる解法
- サンプルコードの遺伝的アルゴリズムによる解法
- サンプルコードの問題点
- 愚直解の構成
- 愚直解の改善 (1)
- 愚直解の改善 (2)
- サンプルとの性能比較
Mario AI とは？
Mario AI とは、スーパーマリオブラザーズのステージを、あらかじめ動きがプログラムされたマリオを用いてクリアしていく競技会のことで、2009 ~ 2012 年の間行われていたものです。マリオを動作させるためのプログラムは、何らかのプログラミング言語で自分で設計することになっています。
自分が大学で所属しているコースでは、このプログラムを設計・動作させるためのソースコードが配布され、自分たちでマリオの動きをプログラムしていくという課題を行います。ソースコードについては、こちらからダウンロードすることも可能なようです。
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 マスについて、障害物や敵があるかどうかの組み合わせは、4^8 = 65536 通りあります。この 65536 通りの場合*2に対して、どのように動けばよいかを考えれば良いです。
さらに、前述の 6 種類の動き方の組み合わせを考えると、ナイーブには 2^6 = 64 通りあります。したがって、周囲 1 マスの情報を全て取得し、その情報に応じて行動するマリオは、全部で 65536 * 64 = 4194304 体存在することになります。これらを 1 体ずつ試してみて、指定されたコースをクリアできるマリオを見つけようという作戦です。
しかし、このプログラムをそのまま用いようとすると、終了までにかなり時間がかかってしまうおそれがあります。例えば、上の例ですと周囲 8 マスについて調べましたが、「周囲 8 マスだけでは足りない！」と思って、さらに 3 マス分追加で調べるとすると、なんと 268435456 体のマリオを作らなければいけなくなります。このように、周囲の情報を手に入れようとすればするだけ、指数的に手数が増えていってしまいます。
サンプルコードの遺伝的アルゴリズムによる解法
解の候補となるマリオを全て作って試す、ということが難しい場合でも、「さっき作ったマリオよりも改善された (と思われる) マリオを作り続ける」という方針を取った場合、調べるマリオの個体数が大きく減少することがあります。これを実現するための 1 つの方法として、「遺伝的アルゴリズム」というものがあります (遺伝的アルゴリズムの簡単な説明としては、このサイトが分かりやすいです) 。
各マリオは「どういった周囲の情報に対し、どのように行動するか」という対応付けを持っています。この対応付けは、マリオの各個体によって異なることから、「遺伝子」と呼ばれ、配列で実現できます。サンプルコードでも、(先ほどの解法とは少し異なりますが) 周囲の環境情報に行動を対応付ける解法を取っています。
遺伝的アルゴリズムを用いると、例えば以下のようにしてコースをクリア可能なマリオを見つけることができます。
- まず、ランダムに 100 体ほどマリオを作る。この 100 体を「1 世代目」とする。
- 次に、現世代の 100 体それぞれにコースを走らせてみて、最も良い成績であった上位 2 体を選出する。
- 上位 2 体については、次世代に引き継ぐ。それ以外の個体については、以下の方法で遺伝子を「組み換え」する。
- 選択: そのまま次世代に引き継ぐ。
- 交叉: 個体を 2 つ選び、遺伝子の一部を交換して次世代の個体とする。
- 突然変異: 個体を 1 つ選び、ランダムに遺伝子を異なるものにする。
- 次世代を次の現世代とする。コースをクリアできる個体が見つかるまで、2. 3. 4. を繰り返す。見つかれば終了。
上位の数個体はそのまま次世代に引き継いでいることから、解は単調非減少となり、選択・交叉・突然変異により、条件を満たす解に近づいていく方法です。
サンプルコードの問題点
このようにすると無事解が求まるように思われますが、そのままサンプルコードを動かしても、うまく行きません。理由として、周囲の 1 マス単位でしか環境情報を取得していないため、情報の粒度が粗いから、というのがありそうです*3。また、シンプルに探索するマスを増加させてみたりしましたが、解の更新が低速になるだけで、あまり改善しませんでした。そこで、少し異なる方法を採用してみることにしました。
愚直解の構成
各フレームごとに取る行動は、action という 6 要素の true または false が入っている配列で表現しますが、これを 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 世代ほどで解が見つかりました。もっとちゃんとデータ取ればよかったかも……
【Python】湯婆婆の業務を効率化しよう
はじめに
みなさんは、ジブリの大ヒット映画「千と千尋の神隠し」を知っていますか？
中でも特に有名なシーンは、油屋にやって来た千尋に、湯婆婆が新たに名前をつける場面でしょう。
このようにして、湯婆婆は各従業員に名前をつけることが知られています。しかしながら、大規模な営業を行う油屋において、一人ひとりに湯婆婆自身が名前をつけていては、大変なはずです。過酷を極める湯婆婆の業務の一助になりたいと思い、ここに至りました。
アイデア
最近 Python というプログラミング言語を勉強し始めたので、これを用いて効率化を図れないかと考えました。従業員一人ひとりを短い名前で管理できるような方法があればさらに良いですね。そこで、以下のように考えました。
挙動
このように、PC からの操作によって、湯婆婆の業務を効率化します。また、元の名前と与えた名前は自動で作成された CSV ファイルに格納され、この CSV ファイルは Excel などで開くことができます。
実装
以下のように行いました。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()
N 以下の正整数のうち、各桁に特定の数字のみを含むものの数を数える
はじめに
この問題を解くことが幼少期*1からの夢でした。2021年度後期で『アルゴリズムとデータ構造入門』を履修し、少しアルゴリズムに興味が持てたため、プログラムを作成してこの問題を解いてみようと思います。使用言語は一応 C++ としています。
そもそもどういう問題？
タイトルの通りですが、例えば で、特定の (使ってよい) 数字が
の場合、条件を満たす数は「
以下で
しか桁に現れない数」ということで、
の
種類となります。よって答は
です。そんな感じです。
愚直にやってみる (解法1)
まず初めに思いつくのは、
以下の正整数をfor文で全列挙する
- 全列挙した各整数の各桁を取り出し、使用可能な数字かどうか確かめる
という方法がありそうです。プログラムの一例としては、以下のようなものがあると思います。
#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; }
おわりに
意識の底にあった問題をついに解くことができ (たと思われ) 、少しうれしい気持ちになっています。作成したプログラムはかなり乱雑なものとなってしまいました。記事内に誤りがあれば、教えて頂けますと幸いです。
また、進法を用いた考え方などもできそうです。またゆっくり考えてみたいと思っています。
