2022-02-01から1ヶ月間の記事一覧

AtCoder Beginner Contest 239 E

https://atcoder.jp/contests/abc239/tasks/abc239_eKに制限があるところが全てですね。ちゃんと読まないとそんなのがあると思わない。 # coding: utf-8 # Subtree K-th Max from itertools import * from collections import defaultdict import sys sys.se…

AtCoder Beginner Contest 239 Ex

https://atcoder.jp/contests/abc239/tasks/abc239_h例えば、N=4, M=5で考えてみましょう。 1回サイコロを振って、目が1ならそのまま、2なら次以降が2より大きければ終わり、3なら次以降が1より大きければ終わり、4と5も同様です。をmになる回数の期待値とす…

AtCoder Beginner Contest 238 E

https://atcoder.jp/contests/abc238/tasks/abc238_eパッと見線形代数ですが、AtCoderだからDPかもしれないと考えると、次のような状態を考えることができます。そう考えるとから(4, 6)を足すと、(2, 3)を引くととなります。すなわち、6 3 1というようなグラ…

AtCoder Beginner Contest 237 F

https://atcoder.jp/contests/abc237/tasks/abc237_fこれはDPですね。 数列が与えられたとき、数列の各要素までで最長の長さを考えると、例えば、3 1 4 2 3 5が与えられたとすると、 3 1 4 2 3 5 1 1 2 2 3 3例えば、この数列に4を追加するとき、例えば先頭…

AtCoder Regular Contest 133 B

https://atcoder.jp/contests/arc133/tasks/arc133_b解説にあるように、まず(i, j)を(i, -j)をキーにソートします。しかし、PyPyではこれが遅いんですね。適当なN=200000の列で2.7秒かかりました。 これを、iが小さい方から、iが同じjを降順にソートしてexte…