bouzuya.hatenablog.com

ぼうずやのにっき

アルゴリズムと数学 演習問題集 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 なので ba を掛けると O(b) になるため間に合わない。

そこで b を 2 のべき乗として扱うことで高速化する。 a を掛ける代わりに a^2a^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 4N を解いた。

問題: 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 となる。

このとき 4S4S = 4^1 + 4^2 + ... + 4^N + 4^{N+1} となる。

4S - S すると対応する値を消せる。 4S - S = 4^{N+1} - 4^0S で整理すると S = (4^{N+1} - 1) / 3

10^9+7 における powsubinv が取れれば良い。 pow は 2 のべき乗を使うなどして高速化する必要がある。これは 050 を参照すると良い。 sub は念のため 10^9+7 を足してから引いてやると良い。 inv は書籍のモジュラ逆数の通り 1/3 (3inv) は 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 を追加した。


今日のコミット。