参考資料： https://www.jstage.jst.go.jp/article/jjsai/28/3/28_474/_pdf データの生成モデル (Generative Model) ボルツマン分布に従う。 ボルツマン分布のエネルギー関数はバイアス項に$\theta$, 相互作用項に$w$でパラメトライズされている。 これらの…
線形不等式の許容領域は凸多面体である。 変数が$n$個の場合は$n$次元空間内の凸多面体である。 集合$S$が凸であるとは、集合$S$に属する任意の2点$x, y\in S$に対して、$x$と$y$を結ぶ線分上の全ての点が$S$に属することを言う。 最適解が存在しないのは、 …
youtu.be contentious: 争いを好む、議論好きな、議論のある contentious case: 係争事件 contentious decision: 議論のある決定 neurology: 神経学 via infusion: 点滴で (ヴァイア) mixed up: 関わる、混乱状態にある He was mixed up with the matter: 彼…
ベルヌーイ試行のサンプル数$n$と誤差$\epsilon$の関係 の導出に関するメモです。 導出は以下の資料を参考にしています。 [http://www3.u-toyama.ac.jp/kkarato/2020/statistics/handout/Statistics[B]-2020-19-0703.pdf] ベルヌーイ分布に従う$X_i$からスタ…
youtu.be rollout: 市場への導入 abundance: 大量の、存在 an abundance of caution was cited: 対数の注意が言及された、挙げられた。 adverse event: 有害事象 go forward: 計画を前進する smuggle: 秘密裏に持ち出す、密輸する smuggle in heroin smuggle…
youtu.be awe: 畏敬の念を起こさせる awe-inspiring frightening sight: 畏敬の念を起こさせる恐ろしい光景 fled: fleeの過去形、逃げる they fled the town area after the earthquake. 自身のあとその町から逃げた。(他動詞) 自動詞ではto, fromを伴う。 p…
www.youtube.com on the brink of : ~にひんして、~の目前で Four major insurance companies are on the brink of bankrupt. brew: 醸造する、いれる、たくらむ、起こす a storm is brewing: 嵐が今にも起ころうとしている。 brew a mischief: いたずらを企…
grant: 許可する、与える grant reports: 報告を与える。報告する? ride out: 切り抜ける I think we just need to ride out this slump in the economy and then we will be okay. この経済スランプを乗り越えたらあとは大丈夫だと思う。 He tried to ride …
youtu.be setback: 停滞、妨げ He had(suffered) a setback in his business. It's the latest setback for the AstraZeneca vaccine. jab: ワクチン接種 bloom clot: 血栓 cerebral: 大脳の venous: 静脈の sinus: 曲がり thrombosis: 血栓症 hemorrhage: …
atcoder.jp 今回はダブリングと呼ばれる手法を使って解いて見ます。 drken1215.hatenablog.com 上のブログでも解説されているようにnext[i][v]を定義します。 next[i][v]: vから$2^{i}$ステップで到達できる場所 まずは$i=0$の場合を考えてnext[0][v]を初期…
C++を勉強中です。 与えられる距離行列はサイズ$N$が非常に大きい場合$N^{2}$で確保してしまうと初期化に時間がかかる。 エッジが存在する場所だけに対して情報を保持する。 そのために以下のようにノードuに対して行き先のノードvとその距離costを保持した…
「量子コンピュータ入門(古澤明著)」の5.1章で暗号文から元のメッセージを復元する時の途中計算(p71)のメモになります。 https://www.amazon.co.jp/量子コンピュータ入門-第2版-宮野-健次郎/dp/4535788057 以下の途中計算になります。 数式の番号は適当に降…
atcoder.jp 幾何分布の期待値に対応しているようです。 幾何分布の期待値の計算は以下を参照して下さい。 幾何分布の確率関数からの期待値と分散の導出 | AVILEN AI Trend k回目で初めて成功する期待値を求めてNまで合計すれば計算できます。 コードは以下に…
atcoder.jp 公式の解説 www.ioi-jp.org 参考にした解説 blog.hamayanhamayan.com 上の解説を自分なりに咀嚼してみました。 $O(M!)$の解法 ぬいぐるみの初期配置が「1232132」の場合で考えてみます。 まずは計算量が$O(M!)$の解法について考えます。 左から順…
個人的メモ。 2.1 Multiple Qubits Entangled States 複数量子ビット状態の行列表示 状態をベクトルで表現する時はAer.get_backend('statevector_simulator')を使う。 ゲートはAer.get_backend('unitary_simulator')を使うことで行列表示することが出来る。 …
個人的メモ。 1.2 Atoms Computation 1量子ビットの加算はNOT, CNOT, Toffoliゲートで行える。 (CNOTゲートはなくても良いみたいです。) Toffoliゲートは3量子ビットに間に働く制御ゲートでQiskitではccxとして提供されている。 実装はめんどくさそう。 qiit…
現在QiskitのTextbookを読んで量子コンピュータについて勉強しています。 0章に入る前の導入部分「What is Quantum?」で紹介されている「Quantum Coin Toss」について考察したいと思います。 qiskit.org いきなり「Quantum Coin Toss」が導入されて何のこと…
atcoder.jp 解説読むとめっちゃ簡単ですよね...。 なぜ解けなかったのか...。 こちらの動画のコードを丸パクリさせて頂きました。 他の人のコードを読むのも勉強になります。 youtu.be N = int(input()) N += 1 A = [0] + list(map(int, input().split())) A…
atcoder.jp コンテスト中はコストの計算量の抑え方が分からずにsubmitできませんでした。 公式解説にもあるように生徒hを昇順にソートし、前と後ろからの累積和を予め計算しておけば$O(1)$でコストが計算できます。 累積和系のテクニックの大事さを痛感しま…
文字列に含まれる数字の順番を入れ替えて8の倍数が作れるかどうかを判定する問題です。 atcoder.jp 1000が8の倍数で割り切れるのがポイントです。 1000が8の倍数で割り切れるので当然それより桁の大きい10000も8で割り切れます。 つまり並べ替えた数列の下３…
巡回セールスマン問題(TSP)です。 atcoder.jp $N$が17なのでビットDPを使えば計算量的に間に合うようです。 $S$をビット列の集合として以下のDPを作成します。 DP[S][v]: 訪問済みの集合Sの頂点vからスタートする時の距離の総和 例えば$N=5$の場合、右から順…
最近Cまでしか解けずレートが全然上がりません...。 今回のD問題も方針自体は分かったのですが、友達の数が最も多い集団を探す関数の計算量が抑えきれずTLEしてしまいました。 解説動画でも紹介されていたUnion Findを用いた実装をしてみました。 こちらを参…
ゼロからできるMCMCの練習問題4.3について考えます。 練習問題4.2ではステップの偶数番目と奇数番目でステップの幅$\Delta x$を変更していましたが、練習問題4.3ではステップごとにサイコロを転がしてステップ幅を決めて更新します。 今回シミュレートする分…
ゼロからできるMCMCの練習問題4.2について考えます。 シミュレートしたい真の分布は です。分布の山が$x=0, x=100$に集中していることを考慮して、偶数番目のステップと奇数番目のステップで遷移幅$\Delta x \in [-c, c]$の値域cを変更しています。 具体的に…
というタイトルですが実際は以下の動画を見た感想になります。 【医師解説】全員にコロナウイルス検査をしても意味がない理由 実際に新型コロナウィルス(COVID-19)のデータを使って計算している訳ではないので注意して下さい。 (※内容に誤りなどがあれば遠慮…
ゼロからできるMCMCを現在読んでいます。 修士課程で量子モンテカルロ法を使った数値計算を行っていたのでMCMCについてはある程度知っているのですが初心に戻って基礎から勉強し直しています。 実は現在のお仕事でもSAを使って計算することがあり、MCMCを使…
蟻本(プログラミングコンテストチャレンジブック)のp25に記載されているハードルが上がった「くじびき」をDP(動的計画法)で解きました。 (間違っていたら教えてください。) 問題文はp8に記載されています。 次のDPテーブルを定義します。 DP[i][j]:i枚の紙の…
「ABC 164 D - Multiple of 2019」をC++で実装しようとした。 butch416.hatenablog.com 数年ぶりにC++を触ることになる。 intの範囲とかをもう少し勉強する必要がある。 ・参考ページ： 【C言語入門】整数(int、long int、short int)の使い方 | 侍エンジニア…
問題文 1から9までの数字のみからなる文字列Sが与えられます。 次のような条件を満たす整数の組$(i, j)(1\le i \le j \le |S|)$の総数を求めてください。 条件：$S$の$i$文字目から$j$文字目までを$10$進法の整数としてみると、この整数は$2019$の倍数である…
機械学習や競技プログラミング、数学、物理・・・に関する個人的なメモ置き場です。 Qiitaにも投稿しています。 qiita.com 大人の事情でアカウント名は異なりますが。
