AtCoderでSageMathを使う - Qiita
AtCoderの最新の言語アップデートが過去問にも適用された。この言語アップデートでSageMathを希望していて、採用されている。これで誰も使わなかったら、申し訳ないし、次の言語アップデートで消されてしまうだろう。ということで、紹介記事を書く。でも、私も詳しいわけではないので、皆使って知見を共有してほしい。正解者数2桁くらいの難しい問題で、「え？ SageMathのこの関数を使うだけでしたが、何か？」と誰かが通している姿を見たい。 SageMathとは？ Wikipediaを見ると良いだろうか。要はOSS版Mathematicaである。 文法はほぼPython。競技プログラミング視点で見ると、便利なライブラリが大量に入ったPythonとして使える。 ローカルで動かす方法 AtCoderのコードテストだけだと面倒。 ローカルで動かすには、Dockerを使うのが簡単。 ソースコードをA.sa
正規分布に従う疑似乱数を生成する方法は？速度は？調べてみました！
この文書は 応用情報 Advent Calender 2020 に投稿した PDF の記事 の Web ページ版です。 はじめに こんにちは。応用情報 Advent Calender 2020 も9日目に突入しましたが、みなさまいかがお過ごしでしょうか。知的情報処理研究室 M1 の生田です。 正規分布は自然現象を良く表現する 1 ことから、数値シミュレーションをはじめとした工学上の応用が数多くあります。また、正規分布からのサンプリングは、他の確率分布（t分布やベータ分布など）に従う乱数の生成にも用いられるため、直接的に正規分布を用いないシミュレーションでも、間接的に正規分布が必要になることがあります。私たちの研究室でも、ニューラルネットワークの重みの初期値など、正規分布は至るところで活躍しています。 しかし、現在広く使われている疑似乱数生成アルゴリズム（線形合同法やメルセンヌ・ツイスターな
IEEE浮動小数点数における平方根演算の精度に関する覚書 - よーる
IEEE浮動小数点数における演算では、丸め誤差が不可避です。特に、複数回の演算を繰り返すと丸め誤差が積もっていき、正確な値と大きく離れた答えを得てしまうことがあります。しかし、次の演算については、（数学的に）正確な値を求めた後、一回だけの丸めが発生することが、IEEE標準で規定されています。 四則演算 積和演算 Fused multiply add (FMA) 平方根演算（正の平方根を求める*1） 浮動小数点数演算のできるCPUであれば、普通、四則演算や積和演算を行う命令を持っています。 しかし、平方根を正確に計算する命令を持たない命令セットも存在します。 そのような場合、平方根関数はライブラリ実装となるわけですが、どのように実装すれば要求を満たせるのでしょうか？ C++のstd::sqrtは正確に計算しているのか？ 結論 しています。 標準の丸めモード、つまり最近接丸め（ぴったり半分なら
アルゴリズム・AtCoder のための数学【前編：数学的知識編①】 - Qiita
こんにちは、大学 1 年生になったばかりの E869120 です。 私は競技プログラミングが趣味で、AtCoder や日本情報オリンピックなどに出場しています。ちなみに、2021 年 4 月 7 日現在、AtCoder では赤（レッドコーダー）です。 本記事では、アルゴリズムの学習や競技プログラミングで使える数学的な部分を総整理し、それらについて解説したいと思います。前編・中編では数学的知識、後編（2021/4/26 公開予定）では数学的考察の側面から書いていきます。 【シリーズ】 アルゴリズム・AtCoder のための数学【前編：数学的知識編①】 ← 本記事 アルゴリズム・AtCoder のための数学【中編：数学的知識編②】 アルゴリズム・AtCoder のための数学【後編：数学的考察編】 1. はじめに 21 世紀も中盤に入り、情報化社会（いわゆる「IT 化」）が急激に進行していく中、
最小共通祖先を求めるアルゴリズムの形式検証 | Wantedly Engineer Blog
競技プログラミングには概念を知っておかないと解きようがない、いわゆる覚えゲーのような問題が存在します。典型的な例が 10^9+7 といった素数で割った余りを求めろといったもので、普段業務で日常的に素数で割った余りを求めている人でもなければ、割り算がしたければフェルマーの小定理や拡張ユークリッドの互除法を使えば良いと直ぐには思い付けないのではないでしょうか。 最小共通祖先も覚えゲーで必要な概念の一種と言えます。これは読んで字のごとく、与えられた根付き木の下で2頂点に共通する祖先のうち、最も根から遠い頂点を指す概念で、例えば木の2頂点が与えられて、頂点間の経路について何かを求めろといった問題で威力を発揮することが多いです。これを用いて解ける例を挙げるとすると次の問題でしょうか。 https://atcoder.jp/contests/abc014/tasks/abc014_4 最小共通祖先を求
AGC018: C – Coins を離散凸解析（L 凸関数最小化）で解く
頂点集合が $U = \set{1,\dots,N},$ $V = \set{1,2,3}$ である完全二部グラフ $G = (U, V; E)$ を考える．以下が与えられる: 正整数 $b_1, b_2, b_3$（ただし $b_1 + b_2 + b_3 = N$），各辺 $(i, j) \in E$ の正整数重み $c_{ij}$．以下の $2$ 条件を満たすように辺部分集合 $S \subseteq E$ を選ぶとき，重みの和 $\sum_{(i, j) \in S} c_{ij}$ の最大値を求めよ: 二部グラフ $(U, V; S)$ において各頂点 $i \in U$ の次数は $1$，二部グラフ $(U, V; S)$ において各頂点 $j \in V$ の次数は $b_j$． 入力に対する制約$3 \leq N \leq 10^5$$1 \leq c_{ij} \leq
高速逆平方根(fast inverse square root)のアルゴリズム解説 - 滴了庵日録
高速逆平方根とは？ C言語のコード 検証 アルゴリズムの要点 [1] 逆平方根の計算を対数・指数の計算に置き換える [2] 浮動小数点型の内部表現を利用した対数・指数の近似計算 [2.1] 対数の近似 [2.2] σの最適値 [2.3] 整数型での解釈 [2.4] 逆平方根の計算とマジックナンバー0x5F3759DF [3] ニュートン法による収束で精度アップ 感想 高速逆平方根とは？ 高速逆平方根(fast inverse square root)とは、平方根の逆数 を高速に計算するアルゴリズムです。平方根の逆数は逆平方根とも呼ばれます。逆平方根はベクトルの正規化などに用いられるので、これを高速に計算できるアルゴリズムには大きなご利益があります。 参照： Fast inverse square root - Wikipedia C言語のコード 高速逆平方根の関数を示します。0x5F375
第31回 どんな人がソフトウェアエンジニアに向いているのか | gihyo.jp
本連載も5年目になるが、今年は私がこの業界に長年関わる中で得た教訓というテーマで書いてみたいと考えている。 この業界で仕事をしていると、いろいろな場面で「どんな人がソフトウェアエンジニアに向いているのか」という話題になる。一番多いのが人を採用する場面でだが、キャリアパスに悩んでいるエンジニアに相談されるケースもあれば、子どもたちの教育に関する話題でこの話になることもある。 問題解決能力の高さ どんな人がソフトウェアエンジニアに向いているかを一言で言えば、それは「問題解決能力の高さ」である。それも、知識や経験を使った問題解決でははなく、複雑な問題をよりシンプルな問題の集まりに分解して解決していくという、地頭を使った純粋な問題解決能力の高さである。 算数、数学への興味 私は典型的な「理科系少年」として少年時代を過ごした。小学生のときは、算数の応用問題を解くのが大好きだった。武蔵や開成などの名門
初心者でも機械学習の基本的なアルゴリズムを学べる11のスライド -
Photo by fdecomite こんにちは。谷口です。 最近、機械学習の勉強をしている人や、機械学習関連の求人が増えてきましたね。弊社のエンジニアにも、機械学習を勉強中の人達が何人かいます。 ただ、初心者だと「機械学習を勉強したいけど、難しいし何から手を付けたらいいのかよくわからない」という人も多いかと思います。 そこで今回は、機械学習の勉強を始めたばかりという初心者の方向けに、機械学習でよく使われるアルゴリズムがわかるスライドをいくつかご紹介します。 ■機械学習以前 そもそも「機械学習で何ができるのか・どんなものなのか知りたい」という段階の人が機械学習の概要をつかむには、このあたりのスライドが参考になるかと思います。 If文から機械学習への道 from nishio www.slideshare.net 機械学習入門以前 from mrtc0 www.slideshare.net
半順序集合と全順序集合の意味と例 - 具体例で学ぶ数学
ただし（$S$ 上の）半順序関係とは、以下の３つの条件を満たす二項関係 $\leq$ のことです。 反射律： 任意の $a\in S$ に対して、$a\leq a$ 推移律： 任意の $a,b,c\in S$ に対して、$a\leq b$ かつ $b\leq c$ なら $a\leq c$ 反対称律： 任意の $a,b$ に対して、$a\leq b$ かつ $b\leq a$ なら $a=b$ なお、半順序集合のことを、英語で partially ordered set というので、略して poset（ポセット）と呼ぶことがあります。
EMアルゴリズム徹底解説 - Qiita
ステップ2 $r_{nk}$を固定して$J$を$\mu_k$で偏微分して最小化します。 式変形をすると、 クラスタ$k$の最適なCentroidは上記のように、クラスター$k$に所属しているデータの平均であることがわかりました。 上記より最初のデモンストレーションで行っていたアルゴリズムは損失関数$J$の最適化によって導出されたものを適用していたことがわかります。 2−3. 実装 上記で示した２ステップを計算して、イテレーションを回すだけのシンプルなプログラムです。最後に更新前のmuと更新後のmuの差を取り、それがある程度小さくなったら収束したと判断し、イテレーションを止めるようにしています。 下記はアルゴリズム部分の抜粋です。プログラムの全文はコチラにあります。 for _iter in range(100): # Step 1 =============================
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
The definitive guide to “Modulo Bias and how to avoid it”!
https://twitter.com/ngtkana/status/1634777658964996096?s=12&t=YpIPcsjKfoTpmECNdRL-uw
https://twitter.com/yujitach/status/1575874872688852992
たもと on Twitter: "「繰り返し処理を回す」「配列をなめる」「API を叩く」などの、和語の動詞が IT 分野に意味範囲を広げてくるやつがけっこうすき 最近だと「AI に教師データを食わせる」などもある"
ところてん on Twitter: "プログラマーになるのに数学は要らない、ってツイートが流れてきたけど、 まあ、半分正しくて、半分間違ってんだよなぁ 上の世界の仕事をしないなら、数学は要らないと思うよ https://t.co/kiB5muMifz https://t.co/L5niUGeJ3O"
すど on Twitter: "「この世界に一度行くと帰ってこれない可能性があるので，十分気を付けるように」 https://t.co/qr0HdcikO9"
共立出版 アリがと蟻 on Twitter: "本書は、力学的な「運動解析」ではなく、コンピュータによる「計算処理」の観点から、3次元回転に関する話題を提供します。また本書では、最適化の数値探索法として「リー代数の方法」を定式化します。恐らくこのような内容の専門書は、我が国では… https://t.co/NUkfN1Pv6P"
How Things Work on Twitter: "This is what happens when you divide by zero on a mechanical calculator https://t.co/rUen0srotQ"
Definitions of sqrt, sin, cos, pow etc. in cmath