ピタゴラス数の列挙
前にもやったが、このとき言及した別方針でやりましょう。
より一般に、2次曲線C上の有理点を列挙します。
・どうにかしてC上の有理点Pを1つ見つける
・Pを通る傾き有理数の直線Lと、LとCの交点であってPでない方が一対一対応
証明：
・有理点を結ぶ直線の傾きは有理数である
→自明
・2次曲線上の有理点を通り傾きが有理数の直線とその2次曲線のもう一つの交点は有理点
→解と係数の関係から自明
証明終わり
2次斉次3変数方程式の解を列挙することができるようになりました
・X^2+Y^2=Z^2 → x^2+y^2=1と(1,0)を使う
・X^2+XY+Y^2=Z^2 → x^2+xy+y^2=1と(1,0)を使う
・X^2-2Y^2=Z^2 → x^2-2y^2=1と(1,0)を使う
おわり
より一般に、2次曲線C上の有理点を列挙します。
・どうにかしてC上の有理点Pを1つ見つける
・Pを通る傾き有理数の直線Lと、LとCの交点であってPでない方が一対一対応
証明：
・有理点を結ぶ直線の傾きは有理数である
→自明
・2次曲線上の有理点を通り傾きが有理数の直線とその2次曲線のもう一つの交点は有理点
→解と係数の関係から自明
証明終わり
2次斉次3変数方程式の解を列挙することができるようになりました
・X^2+Y^2=Z^2 → x^2+y^2=1と(1,0)を使う
・X^2+XY+Y^2=Z^2 → x^2+xy+y^2=1と(1,0)を使う
・X^2-2Y^2=Z^2 → x^2-2y^2=1と(1,0)を使う
おわり
互いに素な整数の組の列挙
Euler296のThreadから
問題：互いに素な正整数の組x,yであって、x+y<=n (など、x,yについて単調な何らかの条件)を満たす組を順序不問で全て列挙せよ
この問題は愚直にやるとgcdのlogがついてO(ans*log)になる。
Stern-Brocot treeを使うとgcdが不要になりO(ans)になるが、空間O(n)などになる
Stern-Brocot treeを使うアプローチで空間O(1)にすると時間にlogがつくと思う
実は時間O(ans)空間O(1)でできます
問題：互いに素な正整数の組x,yであって、x+y<=n (など、x,yについて単調な何らかの条件)を満たす組を順序不問で全て列挙せよ
この問題は愚直にやるとgcdのlogがついてO(ans*log)になる。
Stern-Brocot treeを使うとgcdが不要になりO(ans)になるが、空間O(n)などになる
Stern-Brocot treeを使うアプローチで空間O(1)にすると時間にlogがつくと思う
実は時間O(ans)空間O(1)でできます
マインスイーパ半加算器
4年くらい前にマインスイーパで論理回路を作ったことをこのブログに記録していなかったことに気づいた。
昨今の情勢ではtwitterもいつ使い物にならなくなるかわからないし(?)、とりあえずこっちにも記録を残しておこう。
ツイートはこれ
minesweeperコミュニティの掲示板にも書いてみたけど特にリアクションはなかった。悲しいね
以下に図
昨今の情勢ではtwitterもいつ使い物にならなくなるかわからないし(?)、とりあえずこっちにも記録を残しておこう。
ツイートはこれ
図の盤面には、and回路内のCの真下のマスとxor回路内部のSの真下のマスの計2マスが開けられないことを除いて、最も外側のopeningsだけ開いた状態から安全に到達できる。どうせ全部が確定するわけじゃないのだからとこの条件を気にしないことにすればand回路への接続をもう少し縮めることができる pic.twitter.com/5d2ljOAS39
— hidesugar(9) (@hidesugar2) December 10, 2018
minesweeperコミュニティの掲示板にも書いてみたけど特にリアクションはなかった。悲しいね
以下に図
直角三角形の個数
周長がN以下である直角三角形の個数をO(N^(3/5))で求める。
出典はPE279のmin_25さんの書き込み。計算式が書いてあるだけでその"意味"が書かれていないので、それを読解したものがこの記事。
出典はPE279のmin_25さんの書き込み。計算式が書いてあるだけでその"意味"が書かれていないので、それを読解したものがこの記事。
偏りありコンプガチャ問題
N種類を揃えるまでの期待値はNlog(N)くらいになるというやつ。
では確率に偏りがある場合は？
むかし考えた事がある。考えたというよりは、調べた結果をまとめただけだが。
8年経ったいま改めて考えてみると、簡単に証明できたため、以下で述べる。
問題の定式化：
N種類のアイテムがあり、1回のくじでアイテムxが手に入る確率はP(x)である。コンプする(全てのアイテムを1回以上引く)までに必要な試行回数の期待値を求めよ。
回答：
アイテムの集合Sに対して、P(S):=Σ_{x∈S}P(x)とする。
包除原理より、高々n回の試行でコンプできる確率はQ(n):=Σ_{S}(-1)^(N-|S|)P(S)^nである。
よって求める期待値はΣ_{n≧0}(1-Q(n))=Σ_{S≠φ}(-1)^(N-1-|S|)/(1-P(S))である。
たったこれだけで証明できるとは思わなかった。なるほどな～。
では確率に偏りがある場合は？
むかし考えた事がある。考えたというよりは、調べた結果をまとめただけだが。
8年経ったいま改めて考えてみると、簡単に証明できたため、以下で述べる。
問題の定式化：
N種類のアイテムがあり、1回のくじでアイテムxが手に入る確率はP(x)である。コンプする(全てのアイテムを1回以上引く)までに必要な試行回数の期待値を求めよ。
回答：
アイテムの集合Sに対して、P(S):=Σ_{x∈S}P(x)とする。
包除原理より、高々n回の試行でコンプできる確率はQ(n):=Σ_{S}(-1)^(N-|S|)P(S)^nである。
よって求める期待値はΣ_{n≧0}(1-Q(n))=Σ_{S≠φ}(-1)^(N-1-|S|)/(1-P(S))である。
たったこれだけで証明できるとは思わなかった。なるほどな～。
