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通りです。 さて、この問題はどのように解くでしょう。この手の問題…

Project Euler 725

https://projecteuler.net/problem=725259着。問題はを求めよでしたが、がPyPyで10秒以内でした。

Project Euler 723

https://projecteuler.net/problem=723120着。この問題は面白いです。 高速化がドンドン進んで、PyPyで4msecになりました。 工夫すればもっと速くなると思います。

Project Euler 719

https://projecteuler.net/problem=719481着。Problem 704以来の自作問題です。 去年の10月に提案しました。 特に工夫しなくても解けてしまいます。

Microsoft Solitaire Collection

Windowsユーザにはおなじみのゲームかと思うが、この中にイベントというのがあって、大勢が24時間以内に一斉に行ってスコアとタイムを競う。 これに初めてちゃんと参加したところ59万人中で25位だった。本当だろうか。 全ての面をクリアすると、最終的にはタ…

RustでProject Euler (6)

Problem 4 https://projecteuler.net/problem=4PriorityQueueを使うと速いのですが、ここでは、3桁同士の掛け算を全て配列に入れて、降順に並べて、palindromeを探します。 Vec VecはC++のstd::vectorに相当するものです。空の配列を作って、 let mut a: Vec<i32></i32>…

Project Euler 704

https://projecteuler.net/problem=704219着。Problem 701以来の自作問題です。 単純に2の個数がどうなるか知りたくて作った問題です。

RustでProject Euler (5)

Problem 3 https://projecteuler.net/problem=3 関数の返り値の型 こんな感じですね。 fn max_prime(m: i64) -> i64 { ... } これも後ろに書くんですね。 use std::env; fn main() { let args: Vec<String> = env::args().collect(); let n: i64 = args[1].parse().u</string>…

RustでProject Euler (4)

Problem 2 https://projecteuler.net/problem=2 Iterator Pythonならこのようなgeneratorを作りたいかもしれません。 def fibs(): a, b = 0, 1 while True: yield b a, b = b, a+b Rustでは今のところこのような書き方はできないようです。 (Rustはバージョ…

RustでProject Euler (3)

Problem 1 https://projecteuler.net/problem=1 メソッドチェーン この問題は、Pythonならこんな風に書きたいところでしょう。 import sys n = int(sys.argv[1]) s = sum(i for i in range(1, n) if i%3 == 0 or i%5 == 0) print(s) Rustではこういう書き方…

RustでProject Euler (2)

Problem 1 https://projecteuler.net/problem=1 引数 当然1000は固定でなく、引数で指定したいですよね。そのようにコードを変更してみました。 use std::env; fn main() { let args: Vec<String> = env::args().collect(); let n: i64 = args[1].parse().unwrap(); </string>…

RustでProject Euler (1)

いま流行りのRustの勉強のために、RustでProject Eulerを解いていきます。Rustはそんなに簡単ではないです。 install Windows 10のUbuntuに入れます。 ここを参考にしました。 https://doc.rust-jp.rs/book/second-edition/ch01-01-installation.html $ rust…

Project Euler 701

103着。 Problem 678以来の自作問題です。 解くだけなら簡単です。 ただ、10秒程度にするのは面倒。projecteuler.net

Project Euler 700

267着。projecteuler.net記念すべき700問目。 これは易しいが面白い。思いもかけない解法だった。

Project Euler 673

226着。この問題の"Beds and Desks"というタイトルは自分が付けた。 呼び名が無いと不便なので仮に付けたタイトルだったが、それがそのまま使われてしまった。projecteuler.net

Project Euler 688

150着。易しい。伝統的な解法。projecteuler.net

Project Euler 687

119着。 これも単純。 https://projecteuler.net/problem=687