2021-01-01から1年間の記事一覧

AtCoder Beginner Contest 232 F

https://atcoder.jp/contests/abc232/tasks/abc232_f解説を見てもよくわからなかったので、「bitDP 順列」で検索してみると、https://qiita.com/masayoshi361/items/0be4bce77783b6013b34ここのコードを読んだらわかりました。要は、順列を集合に圧縮するわ…

AtCoder Beginner Contest 232 E

https://atcoder.jp/contests/abc232/tasks/abc232_eまず縦の移動のみの場合の数を数えます。なぜなら、縦の移動回数をkとすれば、縦と横の移動が決まれば、それらの場合の数の積にを掛けたものになるからです。 1回の移動による場合の数は、のときは0です。…

AtCoder Beginner Contest 231 G

https://atcoder.jp/contests/abc231/tasks/abc231_g最初の例で、2×2×3 + 1×3×3 + 1×2×4の計算をしていますが、これは母関数を考えるとすぐに出てきます。 のxの係数を見ればよいです。 だから、2×2×3 + 1×3×3 + 1×2×4 = 29です。2番目の例を見てみましょう…

AtCoder Regular Contest 129 D

https://atcoder.jp/contests/arc129/tasks/arc129_d3 0 -1 -2から-1 2 -1を足していくと全て0になるということですが、逆に0から1 -2 1を足していくと3 0 -1 -2になると考えることができます。 よくあるように多項式で考えましょう。すなわち、3 0 -1 -2は…

AtCoder Beginner Contest 227 B

https://atcoder.jp/contests/abc227/tasks/abc227_b第一感は、を列挙してsetにするでした。 def F_naive(S): M = max(S) possible_areas = set(4*a*b + 3*a + 3*b for a in range(1, (M - 3) / 7 + 1) for b in range(1, (M - 3*a) / (4*a + 3) + 1)) retur…

AtCoder Beginner Contest 224 B

https://atcoder.jp/contests/abc224/tasks/abc224_b問題文通りに書けば十分間に合いますが、 が成り立つと、 なので、 が成り立ちます。 これは、要するに長方形を2分割して、それぞれの領域で不等式成り立てば、元の長方形でも成り立つことを意味します。…

AtCoder Beginner Contest 222 E

https://atcoder.jp/contests/abc222/tasks/abc222_e最短経路が辺を通る回数をとすると、母関数を考えて、 このの係数を求めればよいです。と置いて、 として、と置けば、 なので、を計算しての係数を求めればよいです。同じの重複度をと書くと、 これを最初…

競プロ典型90問 002https://atcoder.jp/contests/typical90/tasks/typical90_bこれは、wikipedia:カタラン数ですね。格子状の経路の数え方に対応していて、右に一つ移動すると'('、上に一つ移動すると')'です。 単純に1歩ずつ進むだけでOKです。 def F(N): d…

競プロ典型90問 001

https://atcoder.jp/contests/typical90/tasks/typical90_a話題になっていた問題です。 少し考えれば、スコア以上が成り立つかは簡単に求められるので、二分探索するだけですね。これで十分速いです。以下は、PyPy2のコードです。 # coding: utf-8 # Yokan P…

AtCoder Beginner Contest 221 D

https://atcoder.jp/contests/abc221/tasks/abc221_d分割統治法で、区間の集まりを[(first, last, num)]で表して、それをマージする、というコードを書いたら意外と長いコードになってしまって、max1462msec。 解説を見ると、ああって感じで、書いてみたら実…

AtCoder Beginner Contest 215 E

https://atcoder.jp/contests/abc215/tasks/abc215_eただのDPで、PyPy2だとあっさり通りました。 で、Python3で試したら、24ケース中13ケースでTLE。案の定Pythonでは遅いです。 手元でも試したら、実行時間は元の文字列の長さにだいたい比例するので、長さ…

AtCoder Regular Contest 118 D

https://atcoder.jp/contests/arc118/tasks/arc118_d面白かったので解説してみます。P = 13, a = 4, b = 5で考えてみます。 まず、グラフを描いてみましょう。a倍していくと、 1 -> 4 -> 3 -> 12 -> 9 -> 10 -> 1 と周期6になります。 もう1つサークルがあり…

Project Euler 750

https://projecteuler.net/problem=750これは自作問題です。 図を何度も書き直させられました。

logの和の近似

の近似によくスターリングの公式が用いられます。 これで十分なことも多いですが、もう少しよい近似を考えてみましょう。積分で近似して、 この差を取ると、 summationの中は、 をテイラー展開すると、 だから、summationの中は、 右辺第一項はリーマン・ゼ…

新型コロナウイルスに関連した患者の死亡の統計

https://www.bousai.metro.tokyo.lg.jp/taisaku/saigai/1010035/1012790/index.html ここから辿ると、死亡情報が例えば、https://www.bousai.metro.tokyo.lg.jp/taisaku/saigai/1010035/1012790/1012818.htmlのように得られます。年代・性別・居住地・診断日…

PythonのライブラリをC++で作成する(5)

もう一つ、これはC/C++で行列の掛け算を書いたことがある人にはよく知られていると思いますが、乗数の方の行列を転置すると速くなります。 もう一度C++のコードを見てみましょう。 Matrix C(H, Vec(W)); for(size_t i = 0U; i < H; ++i) { for(size_t j = 0U…

PythonのライブラリをC++で作成する(4)

なぜC++で書いたライブラリは遅いのでしょう。 Pythonのコードは、 for i in range(H): for j in range(W): C[i][j] = int(sum(A[i][k] * B[k][j] for k in range(M)) % D) return C C++のコードは、 for(size_t i = 0U; i < H; ++i) { for(size_t j = 0U; j …

PythonのライブラリをC++で作成する(3)

いよいよ本題、C++でMatrixの掛け算をするPythonのライブラリを作ります。まず、リストをstd::vectorに変換します。 PyObject *mul(PyObject *self, PyObject *args) { PyObject *obj1, *obj2; long D; if(!PyArg_ParseTuple(args, "OOl", &obj1, &obj2, &D)…

PythonのライブラリをC++で作成する(2)

C++で簡単なPythonのライブラリを作ります。 整数同士を掛け算する関数です。さっそくコードを示します。 # setup.py from distutils.core import setup, Extension setup(name = 'mymath', version = '1.0.0', \ ext_modules = [Extension('mymath', ['myma…

PythonのライブラリをC++で作成する(1)

PythonのライブラリをC++で作ります。 例えば、次のような問題を考えます。 H×Wの長方形があり、そこに1×2の長方形を隙間なく敷き詰めます。敷き詰め方は何通りあるでしょう。 2×3なら、の2通りです。 さて、この問題はどのように解くでしょう。この手の問題…