環境 qiskit-terra 0.20.1 qiskit 0.36.1 Python version 3.10.4 本題 以下のコードを実行すると、表題のエラーが発生します。 from qiskit import QuantumCircuit qc = QuantumCircuit(1) qc.x(0) qc.barrier() gate = qc.to_gate() ----------------------…

問題：AtCoder Beginner Contest 190: D - Staircase Sequences 解説 解説PDFまんまです。 初項a, 末項b とすると、数列は[a, a+1, ... , b-1, b]と表現できる この数列の総和をSとすると、 今回の問題では より、 両辺2倍すると、 となる。これを満たすの組…

pythonnetパッケージとは、Python for .NETと呼ばれるもので、.NETのCommon Language Runtime(CLR)をPythonで扱えるようになるパッケージです。 といってもあまりよくわかってないのですが、とにかくこのpythonnetのclrモジュールを使うことで、Pythonプログ…

何がやりたいかと端的に言うと、 30.100 => 30.1 30.000 => 30 のようにしたい。 Decimalモジュールを使う 小数点といえばDecimalなので、Decimalモジュールを探したらそれっぽいDecimal.normalizeがありました。 数値を正規化 (normalize) して、右端に連続…

問題：AtCoder Beginner Contest 112: D - Partition 公式解説PDF：https://img.atcoder.jp/abc112/editorial.pdf 公式解説動画：AtCoder Beginner Contest 112 解説放送 - YouTube 解説 解説動画まんまです。 のとき、最大公約数の最大値は？という問題です…

問題：AtCoder Beginner Contest 030: C - 飛行機乗り 公式解説PDF：https://www.slideshare.net/chokudai/abc030 公式解説動画：なし 解説 二分探索問題です。 以下の解説は公式PDFの解説まんまです。 入力例1を考えます。 初期状態は以下のように、高橋く…

TL;DR Python3.7系だと、エラーを吐かずに終了することがあります。 現象 a = "1*"*100000 ans = eval(a[:-1]) print(ans) print("end.") 自宅のPC(Windows10, 64bit, Python3.6.5)でこれを実行してみると、 >python hoge.py Traceback (most recent call la…

問題：AtCoder Beginner Contest 133: D - Rain Flows into Dams 公式解説PDF：https://img.atcoder.jp/abc133/editorial.pdf 公式解説動画：https://youtu.be/8uowVvQ_-Mo?t=3228 解説 考察問題です。数式を変換してXに対する漸化式を導きます。 以下の解説…

問題：AtCoder Beginner Contest 131: D - Megalomania 公式解説PDF：https://img.atcoder.jp/abc131/editorial.pdf 公式解説動画：https://youtu.be/XI8exXVxZ-Q?t=4046 解説 締切が早い仕事から順に終わらせていく貪欲法です。割と直感で思いつく解法です…

問題：AtCoder Beginner Contest 136: D - Gathering Children 公式解説PDF：https://img.atcoder.jp/abc136/editorial.pdf 公式解説動画：https://youtu.be/lyHk98daDJo?t=3172 解説 発想としてはランレングス法です。 S=RRRL という例を考えます。 i=0の人…

問題：AtCoder Beginner Contest 031: C - 数列ゲーム 公式解説PDF：https://www.slideshare.net/chokudai/abc031 公式解説動画：なし 解説1：力技 Nは高々50なので、 くらいまでいけそうだとあたりをつけます。 全探索で、問題をシミュレートして高橋のとり…

問題：AtCoder Beginner Contest 140: D - Face Produces Unhappiness 公式解説PDF：https://img.atcoder.jp/abc140/editorial.pdf 公式解説動画：https://youtu.be/VSeggcnxwrc?t=3564 ABC140のD問題のPython3による解説です。 初見では全くわからず、解説…

問題：AtCoder Beginner Contest 129: D - Lamp 公式解説PDF：https://img.atcoder.jp/abc129/editorial.pdf 公式解説動画：https://youtu.be/L8grWxBlIZ4?t=4363 ABC129のD問題のPython3による解説です。 解説 DP問題です。 これは公式の解説動画がとてもわ…

問題：AtCoder Beginner Contest 130: D - Enough Array 公式解説PDF：https://img.atcoder.jp/abc130/editorial.pdf 公式解説動画：https://youtu.be/ERZuLAxZffQ?t=2473 解説 ABC130のD問題の解説です。しゃくとり法の問題です。 8 10 6 1 2 7 10 1 2 1 と…

問題：AtCoder Beginner Contest 140: C - Maximal Value 公式解説PDF：https://img.atcoder.jp/abc140/editorial.pdf 公式解説動画：https://youtu.be/VSeggcnxwrc?t=2461 解説 ABC140のC問題の解説です。貪欲法（？）問題です。 数列 を リストAsに、数列 …

問題：AtCoder Beginner Contest 032: C - 列 公式解説：https://www.slideshare.net/chokudai/abc032 しゃくとり法の問題です。 公式解説を読むと、「連続する1を圧縮する」という重要なテクニックが書かれていますが、本記事ではそうではない方法で解いて…

bin_to_double() 関数 2進数の文字列を、float(64bitの倍精度浮動小数点数)型の数値に変換する関数 double_to_bin() 関数 上の逆関数（float型の数値を、2進数の文字列に変換する関数） 詳細は以下のGistのコードを参照してください。 gist.github.com 参考 …

環境はPython3.6.5です。 まずは以下の計算結果を見てください。 gist.github.com なぜ？ float型において、有効数字が16桁以上の値を表現しようとすると誤差が生じてしまう可能性があるからです。 N//3 のような整数同士の切り捨て除算は内部処理的にint型…

いもす法とは いもす法(imos法)とは、長さNの1次元配列において、「ある連続する区間に、ある数vを足す」という操作をK回繰り返した結果を、計算量O(N+K)で高速に構築できる方法。 たとえば、「ある連続する区間に、1を足す」という操作を4回したい次の図の…

pathlibとは Python 3.4以上で推奨されているファイル・パス操作のモジュール。 os.path の代替となるモジュール。 docs.python.org 使い方をよく忘れるので備忘録です。 返り値はPathオブジェクトなので、文字列に変換したかったらstr()で囲んでやります。 …

編集履歴 (2021/02/21)ダイクストラのプライオリティキューが最短距離の小さい順に取り出されるようになっていなかったので、それを修正 ダイクストラ法とは ダイクストラ法とは、「重み付きグラフにおける単一始点最短路アルゴリズム」 つまり、「始点s か…

辞書(dict)でキーの存在確認をする際の方法としては、 in演算子を使いif文で条件分岐する get()メソッドを使う try exceptを使う（そんな人いるか？） の3種類くらいだと思います。 その中でもget()メソッドはワンライナーで書けて便利なのですが、速度的に…

リスト(list)、タプル(tuple)、集合(set)、辞書(dict)にはin演算子がありますが、それぞれ計算量が違うようです。 python リスト、辞書、セット型のinを使った時の参照速度を調べてみた。 - Qiita Python Speed - www.peignot.net リスト(list) タプル(tuple…

ベルマンフォード法とは 蟻本によれば、「重み付き有向グラフにおける単一始点最短路アルゴリズム」 つまり、「始点s から各頂点i までの最短コストを求める」アルゴリズムです。 以下の条件で使えます。 DAG（有向グラフで閉路を持たない）である 負のコス…

Union-Find木とは Union-FindまたはDisjoint Setとは、蟻本の言葉を借りると「グループ管理のためのデータ構造」。 ・要素aと要素bが同じグループかどうか ・aが属するグループと、bが属するグループを併合(unite)する ということをしたいときに使います。 U…

散々語り尽くされていますが、リストの先頭に対する要素の挿入（insert）や要素の削除（pop）の計算コストはO(N)かかります。このことは公式ドキュメントのcolections.dequeの説明に記載されていているのでその該当箇所を引用すると、 docs.python.org list …

再帰関数を書いたら以下のエラーが発生した。 RecursionError: maximum recursion depth exceeded in comparison エラーで検索したら以下の記事にあたった。 Python3で再帰上限数の変更 - Qiita 書いてあるとおりに、ソースに以下のコードを追加したらなおっ…

condaで何かをインストールするときにPackagesNotFoundErrorが出るときの主な原因は、 (1) タイプミス (2) 探すリポジトリになかった (2)の場合は探すリポジトリを追加させます。 # condaが探すリポジトリ先の確認 $conda config --get channels # conda-for…

オブジェクト群を何かの値でソートしたいとき、それはともかくAtCoderのレートで先にソートするソート手法。 コード # coding: utf-8 class Person(): def __init__(self, rate, height, age, name): self.rate = rate # レート self.height = height # 身長…

リストの要素がクラスオブジェクトの場合に、そのオブジェクトのメンバ変数に対してソートをしたい。 クラスに対するソート（と言ったら語弊があるけど）。 やりたいこと class Person(): def __init__(self, _id, height, name): self._id = _id self._heig…