Dynamic Programming is not Black Magic - Quentin Santos
This year’s Advent of Code has been brutal (compare the stats of 2023 with that of 2022, especially day 1 part 1 vs. day 1 part 2). It included a problem to solve with dynamic programming as soon as day 12, which discouraged some people I know. This specific problem was particularly gnarly for Advent of Code, with multiple special cases to take into account, making it basically intractable if you
Python言語による実務で使える100+の最適化問題 | opt100
はじめに 本書は，筆者が長年書き溜めた様々な実務的な最適化問題についてまとめたものである． 本書は，Jupyter Laboで記述されたものを自動的に変換したものであり，以下のサポートページで公開している． コードも一部公開しているが，ソースコードを保管した Github 自体はプライベートである． 本を購入した人は，サポートページで公開していないプログラムを 圧縮ファイル でダウンロードすることができる． ダウンロードしたファイルの解凍パスワードは<本に記述>である． 作者のページ My HP 本書のサポートページ Support Page 出版社のページ Pythonによる実務で役立つ最適化問題100+ (1) ―グラフ理論と組合せ最適化への招待― Pythonによる実務で役立つ最適化問題100+ (2) ―割当・施設配置・在庫最適化・巡回セールスマン― Pythonによる実務で役立つ
アルゴリズムと数学の本を書きました - E869120's Blog
1. はじめに こんにちは、はじめまして。東京大学 1 年生の米田優峻（E869120）と申します。私は競技プログラミングが趣味で、AtCoder や国際情報オリンピックなどの大会に出場しています1。2021 年 11 月時点で、AtCoder では赤色（レッドコーダー）です。また、2020 年以降、アルゴリズムを学べる以下のようなコンテンツや資料を作成してきました。 レッドコーダーが教える、競プロ上達ガイドライン 競プロ典型 90 問 50 分で学ぶアルゴリズム さて、このたびは技術評論社から、書籍を出版させていただくことになりました2。アルゴリズムと数学が同時に学べる新しい入門書です。 「アルゴリズム×数学」が基礎からしっかり身につく本 - amazon 発売日は今年のクリスマス、2021/12/25 です。電子書籍版も同時期に出る予定です。本記事では、この本の内容と想定読者について、
こわくないbit全探索1 入門編: bit全探索ってなに？【競プロ解説】 - Qiita
競技プログラミング（AtCoder）初心者が、最初に突き当たる壁になることが多いアルゴリズムのひとつに『bit全探索』があります。 この記事では、その『bit全探索』についてできる限り丁寧に解説をしていきます。 記事リンク 1. 入門編 bit全探索ってなに？ : bit全探索はどんなことをするアルゴリズムなのか解説します。 2. 基本編1 簡単な例題でbit全探索をやってみよう！ : 簡単な例題（部分和問題）で実際にbit全探索を実装してみます。 3. 基本編2 2進法を使って実装してみよう！ : 2進法を使ったbit全探索の実装をしてみます。 4. 実践編 AtCoderの問題を解いてみよう！ : AtCoderのbit全探索を使う問題のヒントとコード（Python・C++）を載せています。 5. 応用編 3つ以上の選択肢は再帰関数で書こう！ : 再帰関数を使ってbit全探索に似た問題
中学・高校数学で学ぶ、数学×Pythonプログラミングの第一歩
中学・高校数学で学ぶ、数学×Pythonプログラミングの第一歩：数学×Pythonプログラミング入門 「Pythonの文法は分かったけど、自分では数学や数式をプログラミングコードに起こせない」という人に向けて、中学や高校で学んだ数学を題材に「数学的な考え方×Pythonプログラミング」を習得するための新連載がスタート。連載コンセプトから、前提知識、目標、本格的に始めるための準備までを説明する。 連載目次 この連載では、中学や高校で学んだ数学を題材にして、Pythonによるプログラミングを学びます。といっても、数学の教科書に載っている定理や公式だけに限らず、興味深い数式の例やAI／機械学習の基本となる例を取り上げながら、数学的な考え方を背景としてプログラミングを学ぶお話にしていこうと思います。 今回は、それに先だって、プログラミングを学ぶ上で数学を使うことのメリットや、Pythonでどのよう
Pythonで検索エンジンを自作する方法 Part.1
2019年9月16、17日、日本最大のPythonの祭典である「PyCon JP 2019」が開催されました。「Python New Era」をキャッチコピーに、日本だけでなく世界各地からPythonエンジニアたちが一堂に会し、さまざまな知見を共有します。プレゼンテーション「入門 自作検索エンジン」に登壇したのは加藤遼氏。講演資料はこちら 検索エンジン自作の入門編加藤遼 氏：普段はサーバサイドの開発やAPI、検索まわりをやっています。技術的にはPythonやElasticsearchがメインです。このセッションにこんなに人が来ると思っていなかったので、これだけ集まってくれて大変ありがとうございます。 ここに来たということは、みなさん検索に多少なりとも興味がある方だと思います。なのでちょっとだけ宣伝させてください。検索技術勉強会という勉強会のスタッフをやってます。これは特定のライブラリに関わ
atcoderでよく使う手法python版 - Qiita
はじめに 1年前に機械学習をやりたい、それならpythonだ！ってなったものの、別に情報系卒でもないし、プログラミングをやった経験もないので始めようと思いながら何も動かすことができませんでした。 「何か、なにかプログラミングやってみたい、でも何をやればいいの?」ってときに見つけたのが競技プログラミングです。これをやることで、いろんなアルゴリズムの考え方や、プログラミングでできることをいろいろと学べました。そして、普通に競技プログラミングにハマって今日まで続けています。 そんなところで競技プログラミングでよく使う技術のメモと、もっと使ってほしい技術の紹介です。もっとpython勢増えてほしい。特に短い、早い、わかりやすいコードの人が増えてほしい。いつも短い順、早い順で探して参考にしてるので。 ※githubにjupyterのコードをアップしました。 基本入力、出力、format関数 他の人が
Pythonで幅優先探索を実装する - りんごとバナナ
アルゴリズムの勉強のために、幅優先探索を書いてみた。 使ったのはAtCoder Beginers Contest 007Cの問題。この頃はアルゴリズムがそのまま出題されてたようだ。 特殊事項として、この問題ではスタートからゴールまでは必ず行くことができる前提がある。さらに周り中が壁で囲まれているので、盤面からはみ出すのを考慮する必要がない。 実装 from collections import deque def bfs(maze, visited, sy, sx, gy, gx): queue = deque([[sy, sx]]) visited[sy][sx] = 0 while queue: y, x = queue.popleft() if [y, x] == [gy, gx]: return visited[y][x] for j, k in ([1, 0], [-1, 0],
EMアルゴリズム徹底解説 - Qiita
こんにちは、DeNAでデータサイエンティストをやっているまつけんです。 本ブログは、混合ガウス分布を題材に、EMアルゴリズムという機械学習界隈では有名なアルゴリズムを丁寧に解説することを目的として書いています。 また、この記事は、「数学とコンピュータ Advent Calendar 2017」の24日目の記事です。 そして長いです。 1. はじめに 観測した確率変数 $X$ をよく表現する、モデル $p(x|\theta)$ のパラメータを求めることが確率分布の推定ではよく行われます。つまり最尤法ですね。より複雑な分布になるとその分布の構造に潜在変数(Latent Variable) $Z$ があると仮定してモデル化を行うと、シンプルな組み合わせで $X$ の分布を表現できることがあります。今回扱う混合ガウス分布もその一つです。 のちに説明しますが、データセットの種別を完全データ集合と不完
Algorithmic trading in less than 100 lines of Python code
Read Python for Finance to learn more about analyzing financial data with Python. Algorithmic TradingAlgorithmic trading refers to the computerized, automated trading of financial instruments (based on some algorithm or rule) with little or no human intervention during trading hours. Almost any kind of financial instrument — be it stocks, currencies, commodities, credit products or volatility — ca
勾配降下法の最適化アルゴリズムを概観する | POSTD
(編注：2020/10/01、2016/07/29、いただいたフィードバックをもとに記事を修正いたしました。) 目次： さまざまな勾配降下法 バッチ勾配降下法 確率的勾配降下法 ミニバッチ勾配降下法 課題 勾配降下法を最適化するアルゴリズム Momentum(慣性) Nesterovの加速勾配降下法 Adagrad Adadelta RMSprop Adam アルゴリズムの可視化 どのオプティマイザを選ぶべき？ SGDの並列化と分散化 Hogwild! Downpour SGD SGDのための遅延耐性アルゴリズム TensorFlow Elastic Averaging SGD 最適化されたSGDに対する更なる戦略 シャッフル学習とカリキュラム学習 バッチ正規化 早期終了 勾配ノイズ 結論 参考文献 勾配降下法は、最適化のための最も知られたアルゴリズムの1つです。これまではニューラルネット
機械学習アルゴリズムのボトルネックをCythonで改善する話 - Qiita
class MFbpr(Recommender): ''' コンストラクタとか他の処理 ''' def buildModel(self): loss_pre = sys.float_info.max nonzeros = self.trainMatrix.nnz hr_prev = 0.0 sys.stderr.write("Run for BPR. \n") for itr in xrange(self.maxIter): start = time.time() # Each training epoch for s in xrange(nonzeros): # sample a user u = np.random.randint(self.userCount) itemList = self.trainMatrix.getrowview(u).rows[0] if len(itemL
整数の公式でフィボナッチ数列を求める | POSTD
(注：2020/10/01、2017/6/10、いただいたフィードバックを元に翻訳を修正いたしました。) 次のコードを用いると、なんとフィボナッチ数列が生成できます。 def fib(n): return (4 << n*(3+n)) // ((4 << 2*n) - (2 << n) - 1) & ((2 << n) - 1) この記事では、その導き方と振る舞いを説明しましょう。 具体的な説明に入る前に、背景としてフィボナッチ数列の概要と計算方法を駆け足で紹介します。すでに数学の専門知識がある方は、導入部分はほとんど飛ばして、「母関数」のセクションをざっと読んでから、「整数の公式」に進んでいただいて構いません。 概要 フィボナッチ数列とは、言わずと知れた以下の数列です。 \[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots\] この数列の \(n\) 番目
確率的カウントアルゴリズム Morris Counting の話 - Debug me
ちゃお。舞い降り......† ハイパフォーマンスPython 作者: Micha Gorelick,Ian Ozsvald,相川愛三出版社/メーカー: オライリージャパン発売日: 2015/11/20メディア: 大型本この商品を含むブログ (3件) を見る 11/20にオライリーのHigh Performance Pythonの日本語版が出るようです。 著者のMicha Gorelickさんの紹介文がエキセントリックなことで一部で話題沸騰中な本です。(未来から来たマッドサイエンティストらしい...†) 私は先に出た英語版を読んでMorris Countingという推定カウントアルゴリズムが面白いと思ったんですけど、検索してみたら日本語だとあまりヒットしなかったので、今回はそのお話をしたいと思います。トニーモリス (有名人) の話じゃないよ〜。 さてMorris Counting [Mor
Pythonでの機械学習を支援するツール MALSS（応用） - Qiita
Python3に対応しました(2016.01.25) MALSSの仕様変更に対応しました(2020.02.08) 特徴量選択について追記しました(2020.08.22) Pythonでの機械学習を支援する，MALSS（Machine Learning Support System）というツールを作りました（PyPI／GitHub）． 導入編，基本編と書いてきて，今回は応用編です． 準備 前回と同じデータを使います． 普通にfitメソッドを呼んでしまうとモデリングを行うため処理に時間がかかってしまいます． そこで，algorithm_selection_onlyオプションをTrueにして，アルゴリズム選択のみを行うようにします． from malss import MALSS import pandas as pd data = pd.read_csv('http://www-bcf.usc
Pythonで基本のアルゴリズムを書いてみた - Something Beyond
2015-01-05 Pythonで基本のアルゴリズムを書いてみた Programming アルゴリズムを学ぶ意義みたいなものはいろいろなところで語り尽くされていると思うので私からは特にコメントしませんが、今回の勉強に利用した書籍でも引用されていた言葉が印象的なので、記しておきます。 最先端の機械を使って製品をつくるのは簡単で、しかも楽なことだが、基本技術を固める前に楽なほうに流れていってしまった。俺のような基本的なことがきちんとできるローテクが、今、我が世の春を謳歌しているんだ。 岡野雅行さんという職人さんの言葉のようです。そういえば随分前にこんな記事が盛り上がりました。 今すぐ辞めて欲しい、「Ruby on Rails勉強してます」「CakePHP勉強してます」 最新技術だけではなくて、その基礎となる技術をしっかり理解しなければダメだよということでしょう。ということで基本のアルゴリ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
近似最近傍探索の最前線
GitHub - crampon231/ALDS: Algorithms and Data Structures
正規表現エンジンを作ろう一覧
強くなるためのプログラミング -プログラミングに関する様々なコンテストとそのはじめ方-#pyconjp
