アルゴリズム・AtCoder のための数学【前編：数学的知識編①】 - Qiita
こんにちは、大学 1 年生になったばかりの E869120 です。 私は競技プログラミングが趣味で、AtCoder や日本情報オリンピックなどに出場しています。ちなみに、2021 年 4 月 7 日現在、AtCoder では赤（レッドコーダー）です。 本記事では、アルゴリズムの学習や競技プログラミングで使える数学的な部分を総整理し、それらについて解説したいと思います。前編・中編では数学的知識、後編（2021/4/26 公開予定）では数学的考察の側面から書いていきます。 【シリーズ】 アルゴリズム・AtCoder のための数学【前編：数学的知識編①】 ← 本記事 アルゴリズム・AtCoder のための数学【中編：数学的知識編②】 アルゴリズム・AtCoder のための数学【後編：数学的考察編】 1. はじめに 21 世紀も中盤に入り、情報化社会（いわゆる「IT 化」）が急激に進行していく中、
モンテカルロシミュレーション
このホームページは、乱数をたくさん発生させ、確率実験を行なう手法――これをモンテカルロ・シミュレーションといいます――のオンライン教科書です。あなたのパソコンを用いて、実際にプログラミングしてＷＥＢ上で実行することができます。 C言語版はこちら １９９４年に、著者はソフトバンク社から「Ｃによるシミュレーションプログラミング」 という本を、出版しました。現在それは絶版となっています。しかしながら、その後、それを大学などの教科書に使いたい、再版しないのかなどの問い合わせが ありました。出版したときの電子ファイルが残っていたので、それのすべてをホームページで、公開することといたします。その際、ホームページ上から、直接 プログラムを実行出来るように、ＣプログラムをＪａｖａアプレットに変換し、公表します。 このホームページが、シミュレーションに興味をお持ちの方、トラヒック理論の研究者などのお役に立て
逆関数法を用いた乱数生成の証明と例 | 高校数学の美しい物語
UUU が一様分布に従うことを式で表す： P(U≤u)=uP(U\leq u)=uP(U≤u)=u （ただし 0≤u≤10\leq u\leq 10≤u≤1） ここで， U≤u ⟺ F−1(U)≤F−1(u)U\leq u\iff F^{-1}(U)\leq F^{-1}(u)U≤u⟺F−1(U)≤F−1(u) に注意すると上式は P(F−1(U)≤F−1(u))=uP(F^{-1}(U)\leq F^{-1}(u))=uP(F−1(U)≤F−1(u))=u となる。 さらに，F−1(u)=xF^{-1}(u)=xF−1(u)=x と置くと， P(F−1(U)≤x)=F(x)P(F^{-1}(U)\leq x)=F(x)P(F−1(U)≤x)=F(x) これは確率変数 F−1(U)F^{-1}(U)F−1(U) が，累積分布関数が F(x)F(x)F(x) であるような確率分布に従うこ
完全に理解するアフィン変換 - Qiita
アフィン変換の真価を知ったら実はかなり強かった、という話。我々はアフィン変換の本当のすごさを知らない。 サンプル 非常に複雑な変換に見えますが、たった1回のアフィン変換でやっています。この記事の処理を組み合わせていけばこの処理が実装できます。 平面のアフィン変換とは三角形の移動（写像）を与えることで決まる変換のこと（証明は末尾参照）。 画像の回転処理にアフィン変換がよく用いられますが、アフィン変換≠回転です。アフィン変換はもっと広く処理ができますし、回転処理はその一部です。最初に回転を考えると理解しにくくなります。 OpenCVでの実装 今回は数学的にあまり突っ込まずに「PythonのOpenCVで自分で実装できればOK」レベルを目指します。OpenCVでは次のようにアフィン変換を行います。 import cv2 af = cv2.getAffineTransform(src, dest)
アフィン変換とは - 大人になってからの再学習
幾何学の分野で、ある図形を回転させたり引き延ばしたりする変換をアフィン変換と呼ぶ。 もう少しきちんと説明すると、「アフィン変換とは平行移動と線形変換を組み合わせた変換」のこと。 平行移動はわかるけど、線形変換って？ 線形変換とは、「変換の前に直線だった場所は、変換後も直線のまま保たれる」変換のこと。直線が変換によって曲がったりしない。ということ。 さらに、「直線上に点A,B,Cが並んでいたとき、変換の前後でAB:BCの比が変化しない」。線の形が変わらないから線形変換という、と覚えてしまって構わない。 で、アフィン変換って具体的にはどのような変換？ 具体的には、線形変換（拡大縮小、剪断、回転）、平行移動があり、これらの組み合わせで表現される。 2次元の図形であれば、線形変換は元の座標に2x2の行列を掛けることで表現できる。平行移動は2次元のベクトルの加算で表現できる。 つまり、次のように表す
オイラーのファイ関数のイメージ | 高校数学の美しい物語
n=p1e1p2e2⋯pkekn=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}n=p1e1p2e2⋯pkek と素因数分解できるとき， ϕ(n)=n∏i=1k(1−1pi) \phi(n) = n \prod_{i=1}^k \left( 1-\dfrac{1}{p_i} \right) ϕ(n)=ni=1∏k(1−pi1) となります。この公式を使えば，「自然数 nnn と互いに素な nnn 以下の自然数の個数」を高速で求めることができます。 121212 と互いに素な 121212 以下の自然数の個数は， 12=22⋅312=2^2\cdot 312=22⋅3 より，12(1−12)(1−13)=412\left(1-\dfrac{1}{2}\right)\left(1-\dfrac{1}{3}\right)=412(1−21)(1−31)
ラグランジュの未定乗数法のイメージ - 小人さんの妄想
ある一定の制約条件の下で、関数の最大値（あるいは最小値）を求めたいとき、 「ラグランジュの未定乗数法」という便利な計算方法があります。 たとえば、決まった燃費の下で一番速い車を作れとか、 決まった資本を割り当てて利潤が最大になる方法を探せとか、 実際問題としてもかなり役立つ計算方法です。 さて、ある関数の最大値（あるいは最小値）を求めるには、微分して０になる点を探すという方法が定番です。 微分して０になる点というのは、「山のてっぺんか、谷の底」に相当するからです。 しかし、そこに何らかの制約条件が加わったら、どうでしょうか。 例えば Wikipediaを見ると >> wikipedia:ラグランジュの未定乗数法 関数: f(P1,P2,P3･･･,Pn) = - Σ Pk log2 Pk が最大となる点を、 制約条件: g(P1,P2,P3･･･,Pn) = Σ Pk - 1 が 0 とな
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
