ピタゴラス数の列挙
前にもやったが、このとき言及した別方針でやりましょう。
より一般に、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コミュニティの掲示板にも書いてみたけど特にリアクションはなかった。悲しいね
以下に図
動物園
2022年はアクティブに活動するか
— hidesugar(9) (@hidesugar2) December 31, 2021
目標
・東京メトロ全部歩く会完遂(残り:丸ノ内線,東西線,南北線)
・月1で動物園に遠征する
東京メトロ全部歩く会完遂については前の記事で述べた
動物園についてここでは述べる
01/12 神戸どうぶつ王国
01/13 王子動物園
02/26 夢見ヶ崎動物公園
03/05 千葉市動物公園
04/16 井の頭自然文化園
05/15 江戸川区自然動物園
05/15 葛西臨海水族園
06/04 よこはま動物園ズーラシア
06/25 札幌市円山動物園
06/27 旭川市旭山動物園
06/28 おびひろ動物園
06/30 釧路市動物園
07/18 羽村市動物公園
08/28 池田動物園
09/04 多摩動物公園
10/15 埼玉こども動物自然公園
11/12 東武動物公園
12/02 (再) 葛西臨海水族園
12/03 (再) 井の頭自然文化園
12/24 足立区生物園
関東周辺はだいたい行ったように見えて、jaza加盟動物園だけで28あるので、まだ半分にも満たないんですよね~
来年もこのペースを維持したいところだが、家から片道2時間圏内のところはほとんど行ったので、徐々に難易度が上がっていくという罠がある