はじめに
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】という記事にある、分野別 初中級者が解くべき過去問精選 100 問をpython解いている。
今回は、全探索:工夫して通り数を減らす全列挙の5問!
ノートブックはここ。Google Colabに置いてみたのはこちら
続きを読む『アルゴリズムパズル ―プログラマのための数学パズル入門』という本を読んでいたところ、問題20の山下りの最大和が以下のようなものだった。
正の整数が三角形状に配置されている。この三角形の頂点から初めて、それぞれの回想で直前に選んだ数字と隣接する1つの数字を選びながらふもとまで降下していくときに、たどった数字を合計したあたいの最大値を求めるアルゴリズムを設計せよ(もちろん、全探索よりも効率的であること)。
答えとしては、動的計画法を使えば全探索より効率的に解を求めることができるわけであるが、問題設定が簡単で、かつ色々なアプローチを考えることができるので、勉強していたことをいくつか試してみた。
jupyter notebookはここに置いておいた。
続きを読む言われれば「確かにそうか」と思うのだけど、言われるまで自分の頭の中で整理できていないことってあるよね。
p280において、一般的な(機械学習の)手続きが書かれていて、例えば教師あり学習については、
model = Algorithm(parameters) #インスタンス化 model.fit(x, y) # 学習 y_predicted = model.predict(X_test) # 評価用データについての予測値を取得
と、シンプルに整理されている。その後にスクラッチで書いていくコードも、上記の手順の整理を踏まえたものになっている。もちろん、この手順の他にも、そもそもparameterとなるデータをきれいにしたりだとか、性能評価や、そもそもどのアルゴリズム使うねん、という(泥臭い)手順がたくさんあるのだけど、上記の3行で記述されている部分が、機械学習の「エッセンス」なんだろうなぁと読み取った。
どうなんでしょう。『見て試してわかる機械学習アルゴリズムの仕組み 機械学習図鑑』読んで、もう少し広く把握したあと、python自体について勉強したい。(業務で「きれいなグラフ作って」という雑な仕事が舞い込んで来る可能性があるので、そこまでにはpythonでのデータ処理と可視化をスムーズにできるようにせねば。最悪Rでやろう。)
いわゆる英語の4技能の中で、圧倒的にリスニングが苦手である。なんでみんな英語があんなに聞き取れているのか理解できないことが多々あった。リスニングに関する本はずっと探していたのだけれども、 - 日本語を母語とする人がなぜ聞き取れないのか、聞き取りづらいののかといったことを説明しており - 聞き取りの練習問題がたくさんあり - 専門的なバックグラウンドのある人によって書かれている といった条件を満たす本がないな、と思っていた。しかし、本屋に立ち寄ったところ、上記の条件を満たす本を発見してしまったため、購入して勉強したところ。
これまで、発音についてはMastering The American Accentをたびたび取り出しては練習してきていたところ。割と細かいところの違いについては忘れていたりしていたので、発音に関する知識の整理にも役に立った。
ディクテーションといったpracticeは基本的に全部行った。発音の練習については、外で勉強していたこともあって割愛している。practiceの正答率は、9割5分くらい。事前に心構えができているので、割と聞き取れていたように思う。100則とあるので、これからは苦手な部分(herの弱形とか)を抜粋して練習したい。
もともとアルゴリズムについてはなんとなくの知識があり、かつ興味もあった一方で、アルゴリズムと一緒に語られるデータ構造ってなんなのだろうという疑問を持っていた。たまたまipadアプリ「アルゴリズム図鑑」を購入して動かしていたところ、具体的に自分で実装してみたいと考えるようになった。
並行して勉強している言語がpythonであったので、pythonでアルゴリズムに書かれている本の中から、
を探したところ、本書を手に取った。
kindleで読んでいた。流れとしては、本文を読み、コードをPCで開いてコードの解説を読んだあと、自分自身でコードを写経するということの繰り返しをした。頭から終わりまで、この方法で一通り進めた。9月9日に購入したようなので、3週間で読んだようだ。
一言で言うと「いい意味で地味」。(少なくともkindleでは)2色刷りとかになっていないし、淡々とした説明が続くので、飽きやすいといった可能性はある。しかし、裏を返せば無駄な記載がなく、必要な説明をすることに専念されているともいえる。コードについての説明もかなり詳しく書かれていると感じている。
また、コードについても、base Python(という言い方があるのだろうか。)で一からアルゴリズムやデータ構造を構成しており、理解につながりやすい工夫がなされていた。また、変数の命名方法や、条件処理など「ほーなるほどそう書くとスッキリするな」と私のレベルで思うところも多く、単純にpythonのコーディングの勉強にもなった。
上記のとおり「いい意味で地味」であるのでパッと見で面白さがわかりにくい可能性もある。そのため、「アルゴリズム図鑑」のアプリや書籍で興味を持った後に、自分で具体的にpythonで実装してみたいと思ったなら、手に取るのが良いのではないだろうか。
割と詰め込み感があったので、ことあるごとに見返すことになると思われる。ダイクストラとA*アルゴリズムがちょっとあやしい。また、本書で扱われていないアルゴリズムについても、ぐぐりながら自分で構成してみる、といったことができるレベルまでは連れてきてくれたと思うので、必要に応じて知識を広げたい。