ABC170のE問題でmultisetを使う問題が出題されましたが、Pythonにはmultisetがありません（さらに順序付きの普通の集合もないですが...）。そこで以下の処理を行うことができるデータ構造、HeapDictを作りました（ソースコードも一番下にあります）。〇O(log…

備忘録 〇sys ・sys.stdin.readlineは入力の高速化に必須 ・sys.exitもたまに使う 〇math ・gcdをよく使う ・factorialは階乗を返す ・三角関数などもここにある 〇decimal ・精度の高い小数を扱える 〇collections ・dequeをよく使う ・Counterも多少使う …

numpyで簡潔に書けたり劇的に高速化できたりする問題一覧 競プロでPythonを使っているが、numpyをあまり使っていないという人はやってみるとnumpyの効果を実感できると思います。 D - Knapsack 1 典型的なナップサックDP。Pythonで愚直にfor文を回すやり方で…

A A*Bを出力する。B 単純に計算しながら結果が10^18を超えたところで打ち切りにするやり方では0があるケースに対応できない。そのため、まず0があるかどうか確認する。C PythonならDecimaiでゴリ押せる。D 素因数分解してそれぞれの素因数pについてp^1,p^2,p…

AtCoderのPython3はnumpyを使うことができる。その高速化テクニックをまとめる。 時間計測はAtCoderのコードテストを使用。 ※追記中〇基本的な考え方 クリックで展開 ・for文を減らす。→numpyの配列を使ってまとめて計算する。 ＜例題＞ D - Lamp D - Knapsa…

atcoder.jp 解法 貪欲的に考える。 例えば2 1 4 2のような場合、2と1を色aと色bで塗ったとする（これらは異なる色で塗るしかない）。そうすると、次の4は2と同じ色aで塗った方がよいことが分かる。なぜなら、 〇色aの最大値が4、色bの最大値が1 〇色aの最大…

Python3でAtCoderなど競プロをやる人向け 入力を受け取る方法についてのまとめです。これらを覚えておけばほとんど場合の入力に対応できます。 〇文字列を受け取る 例 abc s=input() 〇ひとつの整数を受け取る 例 3 n=int(input()) 〇横に並んだ複数の文字列…

AtCoder Beginner Contest 146 atcoder.jp 解法 まず、使用する色の数はすべての頂点の次数のうち最大のものである（次数とは頂点から出る辺の数である）。 次に、色の塗分けは幅優先探索を使って行う。具体的には任意の頂点を根として、子となる頂点との間…