数学
Enumerative Combinatorics の勉強会に参加
開発
WASM のチュートリアル: 進捗なし
rust-number-theory: 多項式 mod p の squarefree factorization の部分を実装。
GitHub - koba-e964/rust-quantifier-elimination: Quantifier elimination: 進捗なし
競プロ
競プロ典型 90 問 01-22 解き。
Enumerative Combinatorics の勉強会に参加
WASM のチュートリアル: 進捗なし
rust-number-theory: 多項式 mod p の squarefree factorization の部分を実装。
GitHub - koba-e964/rust-quantifier-elimination: Quantifier elimination: 進捗なし
競プロ典型 90 問 01-22 解き。
Enumerative Combinatorics の勉強会に参加。練習問題 3 3 (b) が難しい。
rust-number-theory: 多項式 mod p の squarefree factorization の部分を実装した。
競プロ典型 90 問 今まで出題された 22 問すべて通した。
https://boardgamearena.com/ のチェスを何戦かやった。対局後棋譜が簡単にコピペできないので振り返りがだるい。
競プロ典型 90 問をやっている。 005 - Restricted Digits(★7)が難しかった。
https://lichess.org/training/DbkLd 18... Rh8-h1+ 19. Kf1-e2 からの攻めの続け方がわからなかったが、19... Rh3 とナイトを狙うのがうまい。18... Rh3 だと 19. Nf3-g1 と躱される。
lichess puzzle のレートが 2300 くらいに上がった。じっくり考えると明らかにレートが上がるが、その後じっくり考える体力が無くなった時に下がる。
https://lichess.org/training/vFf81 11. Nf3xe5 の勇気が持てず。そのあと 12. Bc4xf7 とかで詰まなかったためだが、そうではなく 12. Nxc6+ で交換得を図るのが正解。
p を奇素数とする。多項式 mod p の素因数分解について、A(X) = A_1(X) A_2(X), A_1(X) と A_2(X) は異なる d 次式としたとき、T(X) を 2d - 1 次以下の一様ランダムな多項式とすれば A_1 と A_2 が T(X)^{(p^d-1)/2} ± 1 の異なる方の約数になる確率は 1/2 程度以上という命題 (?) について、中国剰余定理から 2d-1 次までみないといけなそうなのは納得。そもそも mod A_1(X) と mod A_2(X) でそれぞれ d-1 次以下の多項式 p^d 個の中から一様ランダムに選ぶのは、mod A(X) で 2d-1 次以下の多項式 p^{2d} 個の中から一様ランダムに選ぶのと同値。A_1(X) が T(X), T(X)^{(p^d-1)/2} + 1, T(X)^{(p^d-1)/2} - 1 の約数になる確率はそれぞれ 1/p^d, (p^d-1)/2p^d, (p^d-1)/2p^d であり、A_2(X) についても同様だから、両方とも同じ因子の約数になってしまう確率は c := p^d として (1/c)^2 + 2((c-1)/2c)^2 = (2c^2-4c+6) / 4c^2 < 1/2 である。(c = p^d >= 3 なので)
やっと理解できた。
ある正則言語に対して、その正則言語に含まれる文字列を逆順にした文字列からなる集合も正則言語、だと思うけど、一方を受理するDFAから他方を受理するDFAに変換するアルゴリズムってのは知られてるのかな
— κねこせん (@necocen) 2021年4月20日