分野別 初中級者が解くべき過去問精選 100 問 in python(全探索:工夫)

はじめに

レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】という記事にある、分野別 初中級者が解くべき過去問精選 100 問python解いている。

今回は、全探索:工夫して通り数を減らす全列挙の5問!

ノートブックはここGoogle Colabに置いてみたのはこちら

続きを読む

分野別 初中級者が解くべき過去問精選 100 問 in python(全探索:全列挙)

はじめに

レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】という記事にある、分野別 初中級者が解くべき過去問精選 100 問python解いている。問題を得ことよりは、どう考えるか、ということに重きを置いているつもりなので、メモがわりに載せておく。

ノートブックはここGoogle Colabに置いてみたのはこちら

最初は全探索:全列挙の4問!

続きを読む

全探索、動的計画法、分枝限定法(枝刈り)、ダイクストラを実装して比較してみた

はじめに

アルゴリズムパズル ―プログラマのための数学パズル入門』という本を読んでいたところ、問題20の山下りの最大和が以下のようなものだった。

正の整数が三角形状に配置されている。この三角形の頂点から初めて、それぞれの回想で直前に選んだ数字と隣接する1つの数字を選びながらふもとまで降下していくときに、たどった数字を合計したあたいの最大値を求めるアルゴリズムを設計せよ(もちろん、全探索よりも効率的であること)。

f:id:Aratamotsu:20201225134315p:plain
4階層の場合。青い経路がこの場合の解

答えとしては、動的計画法を使えば全探索より効率的に解を求めることができるわけであるが、問題設定が簡単で、かつ色々なアプローチを考えることができるので、勉強していたことをいくつか試してみた。

jupyter notebookはここに置いておいた。

続きを読む

『機械学習のエッセンス』を読んだ

とりあえずのメモ

  • 第3章の「機械学習に必要な数学」は、知っている内容だったので読んでいない。
  • 上記の部分についても、濃い内容だった。
  • 掲載されているおおよそのコードの動きは把握し、必要に応じて写経した上で動かした。
  • 自分でスクラッチで書いてみとと言われたら、まだまだ難しい。
  • (なので)必要に応じて振り返りたい。
  • 数値計算の基本ということで、桁落ちの話題が載っているのは、ありがたい。参考分家に「数値計算の常識」が出てきて、元物理学徒としておおぉとなった。
  • 量子力学で使われているブラケット記法は便利だったなと。縦ベクトルと横ベクトルや射影演算子をブラケットに変換せずに考えられるようにならねば・・・。
  • Lagrange multiplierについてはSemidefinite programの文脈でdualityやKKT conditionまでさらっと勉強したことがあるのだけど、\lambda の符号の取り方とか、なんだかわからなくなってモヤモヤしているので、一般的な記述で扱われている何か他の本を当たってスッキリさせておきたい。
  • Principal Component Analysis(PCA)って単語では聞いたことあったのだけど、「特徴量をできる限り保ったまま、次元をへらしたい」という、結構シンプルなことを目指しているのだと知れたのはよかった。読んでいて、singular value decompositionすればいいじゃんと思ったら、案の定したので、とても懐かしかった。
  • (自分のバックグラウンドのせいもあって、)数式を追ったりする場合は、もう少し抽象化された記述だと楽だなぁと感じた(のでそういった本も読まねばな。)
  • Pythonの知識が足りない。(この本に書かれているコードの動きを把握したり、必要に応じてググって理解したりするために必要なことはおよそ書いてあると思います。が、pythonやプログラミングについて全く知識がない訳ではないので、全く知識がない人が読んだら読めるのか、というのは正直分からん。全く知識がない人は本書を最初に手に取ることもないのではないか、と思う。本屋でみたら結構分厚かったし。)

あーそっかと思ったところ

言われれば「確かにそうか」と思うのだけど、言われるまで自分の頭の中で整理できていないことってあるよね。

p280において、一般的な(機械学習の)手続きが書かれていて、例えば教師あり学習については、

model = Algorithm(parameters) #インスタンス化
model.fit(x, y)               # 学習
y_predicted = model.predict(X_test) # 評価用データについての予測値を取得

と、シンプルに整理されている。その後にスクラッチで書いていくコードも、上記の手順の整理を踏まえたものになっている。もちろん、この手順の他にも、そもそもparameterとなるデータをきれいにしたりだとか、性能評価や、そもそもどのアルゴリズム使うねん、という(泥臭い)手順がたくさんあるのだけど、上記の3行で記述されている部分が、機械学習の「エッセンス」なんだろうなぁと読み取った。

次どうする

どうなんでしょう。『見て試してわかる機械学習アルゴリズムの仕組み 機械学習図鑑』読んで、もう少し広く把握したあと、python自体について勉強したい。(業務で「きれいなグラフ作って」という雑な仕事が舞い込んで来る可能性があるので、そこまでにはpythonでのデータ処理と可視化をスムーズにできるようにせねば。最悪Rでやろう。)

『英語リスニングの鬼100則』を勉強した

なぜこの本を勉強しようと思ったか

いわゆる英語の4技能の中で、圧倒的にリスニングが苦手である。なんでみんな英語があんなに聞き取れているのか理解できないことが多々あった。リスニングに関する本はずっと探していたのだけれども、 - 日本語を母語とする人がなぜ聞き取れないのか、聞き取りづらいののかといったことを説明しており - 聞き取りの練習問題がたくさんあり - 専門的なバックグラウンドのある人によって書かれている といった条件を満たす本がないな、と思っていた。しかし、本屋に立ち寄ったところ、上記の条件を満たす本を発見してしまったため、購入して勉強したところ。

勉強してどうだったか

これまで、発音についてはMastering The American Accentをたびたび取り出しては練習してきていたところ。割と細かいところの違いについては忘れていたりしていたので、発音に関する知識の整理にも役に立った。

ディクテーションといったpracticeは基本的に全部行った。発音の練習については、外で勉強していたこともあって割愛している。practiceの正答率は、9割5分くらい。事前に心構えができているので、割と聞き取れていたように思う。100則とあるので、これからは苦手な部分(herの弱形とか)を抜粋して練習したい。

www.amazon.co.jp

『Pythonによるアルゴリズム入門』を読んだ

読もうと思った経緯

もともとアルゴリズムについてはなんとなくの知識があり、かつ興味もあった一方で、アルゴリズムと一緒に語られるデータ構造ってなんなのだろうという疑問を持っていた。たまたまipadアプリ「アルゴリズム図鑑」を購入して動かしていたところ、具体的に自分で実装してみたいと考えるようになった。

並行して勉強している言語がpythonであったので、pythonアルゴリズムに書かれている本の中から、

  • 新しめで
  • アルゴリズム図鑑と類似の話題を扱っており
  • コードとコードの説明がしっかりしていそうなもの

を探したところ、本書を手に取った。

どう読んだか

kindleで読んでいた。流れとしては、本文を読み、コードをPCで開いてコードの解説を読んだあと、自分自身でコードを写経するということの繰り返しをした。頭から終わりまで、この方法で一通り進めた。9月9日に購入したようなので、3週間で読んだようだ。

読んだ感想

一言で言うと「いい意味で地味」。(少なくともkindleでは)2色刷りとかになっていないし、淡々とした説明が続くので、飽きやすいといった可能性はある。しかし、裏を返せば無駄な記載がなく、必要な説明をすることに専念されているともいえる。コードについての説明もかなり詳しく書かれていると感じている。

また、コードについても、base Python(という言い方があるのだろうか。)で一からアルゴリズムやデータ構造を構成しており、理解につながりやすい工夫がなされていた。また、変数の命名方法や、条件処理など「ほーなるほどそう書くとスッキリするな」と私のレベルで思うところも多く、単純にpythonのコーディングの勉強にもなった。

上記のとおり「いい意味で地味」であるのでパッと見で面白さがわかりにくい可能性もある。そのため、「アルゴリズム図鑑」のアプリや書籍で興味を持った後に、自分で具体的にpythonで実装してみたいと思ったなら、手に取るのが良いのではないだろうか。

今後どう読んでいくか

割と詰め込み感があったので、ことあるごとに見返すことになると思われる。ダイクストラとA*アルゴリズムがちょっとあやしい。また、本書で扱われていないアルゴリズムについても、ぐぐりながら自分で構成してみる、といったことができるレベルまでは連れてきてくれたと思うので、必要に応じて知識を広げたい。

www.amazon.co.jp

www.amazon.co.jp