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」が導入されて何のこと…