両端が断熱的な導線の熱伝導を記述する, 次の斉次 Neumann 境界付きの熱方程式の初期値境界値問題 を考えます*1. ここで, , を表します. 前進差分法とスペクトル法を用いる方法の2通りでの数値計算例のデモを作成しました. *2 コードがメインで, 数値解析の…
本記事では省略されがちであったり, 正規分布であることを仮定してあったりすることの多い, 不偏標本分散の母分散の推定量としての一致性を証明していきます.
前回記事Rにさいころをたくさん振らせて、さいころの平均を求めてみる - わかばめにっきでは、Rの擬似乱数を使って標本平均が母平均の一致推定量であることを示しました。今回は後で述べる不偏標本分散という量が母分散の不偏推定量であることを調べていきま…
最近は東京大学出版会の統計学入門を用いて、統計学に再入門しています。標本分散の定義に が出てくるのはなぜだっけ?というところからよくわかっていなかったので、何回かに分けてその理由をメモしていきます。 推定とはなにかというところから出発します…
2次元正方形領域における波動方程式の初期値境界値問題を考えます。 こんな感じで波が伝播していく様子を気軽にシミュレーションできます。
入力 1行に1要素の場合 数字(自然数) N = int(input()) 文字列 S = input() 1行にスペース区切りで複数要素の場合 2つの数字を別の変数 N, M に N, M = map(int, input().split()) 2つの文字列を別の変数 S, T に S, T = map(str, input().split()) 複数の…
先ほどまで開催されていた AtCoder の ABC088 に参加してみました。 問題や解説についてはリンク先をご覧ください。 abc088.contest.atcoder.jp 最近は数値計算をしてみたいなと思うところがあり、Julia の勉強を始めていました。 というわけで、使い慣れて…
最近はブログの更新も競プロへの出場も疎かになってしまいました。と同時に5月のゴールデンウィークに行われた AtCoder の AGC014 に初めて競技プログラミングのコンテストに参加してから半年が経ってしまいました。というわけで短い期間を振り返ろうと思い…
注意:この記事は未完成です。こちらの記事を参考にお願いします wakabame.hatenablog.com の素数 で割った余りを求める方法について解説します. は" 個の異なるものから 個を選ぶときの組み合わせの数"を表しており, 階乗記号 を用いて,と表されます. 階乗…
整数 と整数 に対して, を整数 で割った余りを出力します. 安直に を 回乗じてからで割れば良いのではないかと考えたくなりますが, この方法には2つの欠点があります. 回乗じるのに計算量が かかってしまう. は処理しきれなくなるくらい大きくなりえる. この…
ワーシャル=フロイド法を用いた問題演習として, AtCoder Beginner Contest 074 の D 問題の解説をしてみます. 問題はこちら abc074.contest.atcoder.jp これは制限時間内に解けませんでした.
ワーシャル=フロイド法とは 今回は有向グラフの情報が与えられたとき, 全ての始点から全ての終点までの最短距離をワーシャル=フロイド(Warshall–Floyd)法と呼ばれるアルゴリズムで求めていきます. 有向グラフの最短距離を求めるアルゴリズムのうち, ベルマ…
動的計画法(DP)について, qiita でまとめられました qiita.com 勉強になったのでメモ代わりに. やはり数列の添え字は0から始めて記述したほうが実装との親和性が高そうなので, 以下では数列は として書きます. ここで, は数列の要素数を表します. 1. 最大和…
有向グラフとは 有向グラフ(directed graph)とは, 頂点(vertex)と辺(edge)からなり, 辺は の形式を持ち, 頂点 から頂点 へはコスト で移動できることを表しています. 辺に対して逆向きの進路があるとは限らず, あったとしても同じコストとは限りません. 今回…
木構造の距離を求める問題演習として, AtCoder Beginner Contest 070 の D 問題の解説をしてみます. 問題はこちら abc070.contest.atcoder.jp
グラフの一種である木構造での距離を求めるアルゴリズムを考えます. グラフとは 詳しくは グラフ理論 - Wikipedia などの記述をご参照ください. グラフ(graph)とは頂点(vertex)と辺(edge)からなる構造を表しており, 頂点同士が辺によって繋がっていることを…
本記事では先日開催された AtCoder Grand Contest 019 の C 問題の解説を試みます. ちなみに私は本番中には解けず, 解説や他の人のコードを参考にさせていただきました. 問題はこちら agc019.contest.atcoder.jp スタート地点からゴール地点までの最短ルート…
最長増加部分列(Longest Increasing Subsequence )とは 数列 が与えられたとき, その部分列 であって のとき を満たすものを増加部分列と言います. その中で最も長いものの長さを求めるアルゴリズムを以下に説明していきます.