2022-02-23 アルゴリズムと数学 演習問題集 050, 051, 052, 053 を解いた
アルゴリズムと数学 演習問題集 050 - Power を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_aq
a^b (mod 1_000_000_007) を求める。 b <= 10^9 なので b 回 a を掛けると O(b) になるため間に合わない。
そこで b を 2 のべき乗として扱うことで高速化する。 a を掛ける代わりに a^2 や a^4 ... を掛けることで回数が減らせる。 b をビット演算で扱うと良い感じに処理できる。
let mut p = 1;
while b != 0 {
if (b & 1) != 0 {
p *= a;
}
a *= a;
b >>= 1;
}
あとは掛け算している箇所で mod を入れれば良い。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/29488217
アルゴリズムと数学 演習問題集 051 - Combination Hard を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_ar
右に X 上に Y 移動する経路の数は _{X+Y}C_{Y} 。 \frac{(X+Y)!}{Y!(X+Y-Y)!} 。 mod 1_000_007 なので逆数にフェルマーの小定理からあれこれが必要になる。ぼくはもう面倒なので ACL https://github.com/rust-lang-ja/ac-library-rs の ModInt で求めた。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/29488453
アルゴリズムと数学 演習問題集 052 - Knight を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/abc145_d
a 回目の移動で移動できる場所とその個数を書き出してみる。いくつかのことが分かる。
x + y = 3aになる- a 回目に到達できる位置は a + 1 個になる
- パスカルの三角形になっている
0: 0: (0,0)x1
1: 3: (1,2)x1, (2,1)x1
2: 6: (2,4)x1, (3,3)x2, (4,2)x1
3: 9: (3,6)x1, (4,5)x3, (5,4)x3, (6,3)x1
4: 12: (4,8)x1, (5,7)x4, (6,6)x6, (7,5)x4, (8,4)x1
a: 3a: (a,2a)x1, (a+b,2a-b)xa, ...
(+1,+2) か (+2,+1) しか選べないので (X + Y) % 3 != 0 なら到達できない。
到達できる場合は a = (X + Y) / 3 で求めたい値がパスカルの三角形の a 行目にあることが分かる。左から何個目にあるかは MIN(X,Y) - a で求められる。もし MIN(X,Y) < a の場合は到達できない。あとは _{a}C_{b} で個数を求められる。これは 051 と同様に求められる。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/29596028
アルゴリズムと数学 演習問題集 053 - Sum of 4^N を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_as
N <= 10^18 なので愚直に計算しては間に合わない。等比数列の和を求める。
求める値を S と置くと S = 4^0 + 4^1 + 4^2 + ... + 4^N となる。
このとき 4S は 4S = 4^1 + 4^2 + ... + 4^N + 4^{N+1} となる。
4S - S すると対応する値を消せる。 4S - S = 4^{N+1} - 4^0 。 S で整理すると S = (4^{N+1} - 1) / 3 。
10^9+7 における pow と sub と inv が取れれば良い。 pow は 2 のべき乗を使うなどして高速化する必要がある。これは 050 を参照すると良い。 sub は念のため 10^9+7 を足してから引いてやると良い。 inv は書籍のモジュラ逆数の通り 1/3 (3 の inv) は 10^9+7 なら pow(3, 10^9+7 - 2) で求められる。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/29597601
bouzuya/rust-sandbox の its を実際に使ってみて issue_id 列の MAX を取っているのだけど issue_id 列は TEXT になっていて……というくだらないミスをしている。修正するための Migration を適用するために sqlx の Migration の使い方を調べて bouzuya/rust-examples に sqlx1 を追加した。
今日のコミット。