プチコン 非公式コミュニティ
プレイ日記
こういち
◆ou0jbJnEJ0Kb
2019/8/28 9:39
2019/8/28 9:39
問題
サンタさんは、自分の副業が空き巣だということを皆に打ち明けようと思っています。
任意の人に自分の正体を打ち明けたとき、その人は1/Nの格率で絶望し、サンタさんのファンをやめてしまいます。
M人に正体を打ち明けたとき、サンタさんのファンが一人も減らない確率の逆数を32768で割った余りを求めてください。
サンタさんは、自分の副業が空き巣だということを皆に打ち明けようと思っています。
任意の人に自分の正体を打ち明けたとき、その人は1/Nの格率で絶望し、サンタさんのファンをやめてしまいます。
M人に正体を打ち明けたとき、サンタさんのファンが一人も減らない確率の逆数を32768で割った余りを求めてください。
コメント
Na
2019/8/30 19:59
◆QoELVrBXBQCI
かなり上に書いたFOR使ったコード、全然間違ってました
N/(N-1)は整数じゃないから、毎回32768を引くではだめだった
N/(N-1)は整数じゃないから、毎回32768を引くではだめだった
SatoshiMcCloud
2019/8/30 20:11
◆Z1qfV11i63Jr
まあ組み合わせ計算のCが出た時点である程度は察してましたが…うーん
Na
2019/8/30 20:23 ネタバレ
◆QoELVrBXBQCI
SatoshiMcCloud
2019/8/30 20:44
◆Z1qfV11i63Jr
>>Naさん
やっぱそうなりますかね…
やっぱそうなりますかね…
高原のな
2019/8/30 20:58 ネタバレ
◆bY8RViwvoODw
SatoshiMcCloud
2019/8/30 22:00
◆Z1qfV11i63Jr
がんばったけど、満足な精度が出ないのでギブアップします。無念…
高原のな
2019/8/30 22:47
◆bY8RViwvoODw
32bitよりでかい整数を配列を用いて表現しているのですが、でかい整数同士の掛け算と割り算(特に割り算)さえ実装できれば問題は解決
ユークリッドの互除法を用いて最大公約数を算出→約分という処理をどうにかうまくできれば……
ユークリッドの互除法を用いて最大公約数を算出→約分という処理をどうにかうまくできれば……
高原のな
2019/8/30 22:48
◆bY8RViwvoODw
(筆算の割り算を10進法以外に拡張するとか？)
Na
2019/8/30 22:54
◆QoELVrBXBQCI
>高原のなさん
文字列を用いて表現するという方法は(適当)
文字列を用いて表現するという方法は(適当)
高原のな
2019/8/30 23:00
◆bY8RViwvoODw
(実装してみて思ったけれど、確かに文字列の方が簡単そう)
高原のな
2019/8/31 0:19
◆bY8RViwvoODw
(あと整数の割り算さえ実装すれば、Nが有理数なら無限精度の実装が完成する)
SatoshiMcCloud
2019/8/31 0:25
◆Z1qfV11i63Jr
最終手段としては、確率問題なら実際に試行してみる手がある！
それにしたって精度が欲しいなら相当回数試行しないとダメですが…。
それにしたって精度が欲しいなら相当回数試行しないとダメですが…。
高原のな
2019/8/31 0:30
◆bY8RViwvoODw
(割り算処理を除いて)完成した…… 現時点で32768で割る前の分数表示までできる
割り算処理を書くの面倒なので正直やりたくないけど、やらないことには完成しない……ちゃんとそのうちやる
(追記：無限精度C#解(途中かけ)をGitHub Gistにアップしました。興味のある方はどうぞ。 https://gist.github.com/taka-impact/170e13ed867431b478f5d599d1eac76b )
(追記２：LargeIntegerクラスですが、同符号の場合絶対値の大小になってしまうという実装ミスをしました。もし利用される際はお気をつけて)
割り算処理を書くの面倒なので正直やりたくないけど、やらないことには完成しない……ちゃんとそのうちやる
(追記：無限精度C#解(途中かけ)をGitHub Gistにアップしました。興味のある方はどうぞ。 https://gist.github.com/taka-impact/170e13ed867431b478f5d599d1eac76b )
(追記２：LargeIntegerクラスですが、同符号の場合絶対値の大小になってしまうという実装ミスをしました。もし利用される際はお気をつけて)
こういち
2019/9/24 15:19
◆ou0jbJnEJ0Kb
盛り上がってますね。
逆元が、互いに素でないと存在しないという事実を知って絶望中。
やっぱり気合いで巨大な数の計算できるようにするしかないのかな…
そもそも分数を32768で割った余りって何やねん。
これ、最後の1文を
M人に正体を打ち明けたとき、M人全員がサンタさんのファンをやめる確率の逆数を20123で割った余りを求めてください。
に変えたら大分解きやすくなるんだろうな…(夢の中が元ネタなので問題文ガハガバ)
逆元が、互いに素でないと存在しないという事実を知って絶望中。
やっぱり気合いで巨大な数の計算できるようにするしかないのかな…
そもそも分数を32768で割った余りって何やねん。
これ、最後の1文を
M人に正体を打ち明けたとき、M人全員がサンタさんのファンをやめる確率の逆数を20123で割った余りを求めてください。
に変えたら大分解きやすくなるんだろうな…(夢の中が元ネタなので問題文ガハガバ)
高原のな
2019/9/24 20:27
◆bY8RViwvoODw
そういえば割り算をまだ作ってないのだ〜〜〜()
実装は小学校で習った筆算のやり方でできそうですね．ただ重そうですが
一応プチコンにも移植できそうなので，割り算ができ次第やってみようと思いました
実装は小学校で習った筆算のやり方でできそうですね．ただ重そうですが
一応プチコンにも移植できそうなので，割り算ができ次第やってみようと思いました
こういち
2019/10/15 8:37 ネタバレ
◆ou0jbJnEJ0Kb
こういち
2019/10/21 16:24
◆ou0jbJnEJ0Kb
>そもそも分数を32768で割った余りって何やねん。<
https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a
逆元ついて調べてみたら、ここに記述がありました。
a/bをpで割ったときの余りは、pで割ったときのbの逆元にaを掛けたものだそうです。
https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a
逆元ついて調べてみたら、ここに記述がありました。
a/bをpで割ったときの余りは、pで割ったときのbの逆元にaを掛けたものだそうです。
こういち
2019/10/21 22:42
◆ou0jbJnEJ0Kb
今まで当たり前のように逆元と呼んでたそれ。モジュラ逆数という名前がついていたようです。
蟻本の影響力なのか…
蟻本の影響力なのか…
こういち
2019/10/21 23:09
◆ou0jbJnEJ0Kb
ちなみに、bと32768が互いに素というのはbが奇数であると言い換えることができる。多分。
こういち
2019/11/11 14:29
◆ou0jbJnEJ0Kb
とりあえずC言語で書いてみた。
あとはプチコンで書き直せば完成なはず。
コメントを書く
- こちらは「プチコン3号」「プチコンBIG」など、プチコンシリーズに関する話題を扱ったコミュニティです
- プチコンシリーズにまったく関係ない書き込みはご遠慮下さい。削除の対象となります
- こちらにはその他のゲームや雑談のコミュニティはなく、作る予定もありません (ひとりで管理できないため)。ごめんなさい
- ユーザー登録なしで書き込みができます
- 秘密の合い言葉は成りすましの防止 (トリップ機能)、書き込みの編集時の本人認証に使用します
- 秘密の合い言葉に他人に推測されやすい言葉、他サービスと同じパスワードは入力しないでください。
- 書き込むと、投稿時に入力したお名前と秘密の暗号が記憶され、ログイン状態になります