大学学部レベル質問スレ 19単位目

1 名前：１３２人目の素数さん mailto:sage [2022/08/04(木) 23:29:28.02 ID:0Ho6Owof.net] 大学で習う数学に関する質問を扱うスレ ・質問する前に教科書や参考書を読むなりググるなりして ・ただの計算は wolframalpha.com ・数式の表記法は mathmathmath.dote ra.net ・質問のマルチポストは非推奨 ・煽り、荒らしはスルー ※前スレ 大学学部レベル質問スレ 18単位目 https://rio2016.5ch.net/test/read.cgi/math/1651147986/ 684 名前：１３２人目の素数さん [2022/10/23(日) 18:10:06.70 ID:+nDVMN8I.net] >>653 >うるさく言うと 五月蝿くない そこ重要 685 名前：１３２人目の素数さん [2022/10/23(日) 18:12:54.28 ID:7oDzHDGj.net] >>653 複素数平面上ではsinz,coszは常に正則なので、tanzもcosz=0の時以外は正則 そのcosz=0の時のzは|z|=1の内部に無い つまり|z|=1の内部ではtanzは正則 っていう書き方だと減点されますかね？ 686 名前：１３２人目の素数さん mailto:sage [2022/10/23(日) 18:29:07.66 ID:7IX/Ea5L.net] >>659 > ちょうど1回である確率 = 1 - (r/N)^1 > ちょうど2回である確率 = (r/N)^1 - (r/N)^2 > ちょうど3回である確率 = (r/N)^2 - (r/N)^3 > などとなるので、 > 1 * [1 - (r/N)^1] + 2 * [(r/N)^1 - (r/N)^2] + 3 * [(r/N)^2 - (r/N)^3] + … > = 1 + (r/N)^1 + (r/N)^2 + … + = N / (N - r) > となるという説明であれば納得がいきますが、いきなり最後の式を導出しています。 上の式変形して下の式になるので納得行くならそれでいいやん 687 名前：１３２人目の素数さん [2022/10/23(日) 19:04:29.96 ID:F4feulSb.net] >>660 状況に応じて厳密さを使い分けることを覚えましょう 688 名前：１３２人目の素数さん [2022/10/23(日) 19:09:18.60 ID:iiQM/xNP.net] >>661 |z|=1の境界ではどうなんだろうってちょっと気になりますね 689 名前：１３２人目の素数さん [2022/10/23(日) 20:52:23.95 ID:ESu0BzCm.net] ∫_C1/(z^3+4z)dz（C:|z|=3） これを解くとき被積分関数をどう変形すれば良いですか 690 名前：１３２人目の素数さん [2022/10/23(日) 20:53:57.42 ID:+nDVMN8I.net] >>663 立派なことですこと 691 名前：１３２人目の素数さん [2022/10/23(日) 21:01:04.75 ID:7oDzHDGj.net] >>664 なるほど…… 内部だけでなく境界にも含まないことを明示しないとまずいですか 692 名前：１３２人目の素数さん [2022/10/23(日) 21:33:31.86 ID:xgrNemdI.net] 事象が独立、確率変数が独立、試行が独立 これらが詳しく解説されている本はありますか？ 693 名前：１３２人目の素数さん [2022/10/23(日) 22:43:40.11 ID:F4feulSb.net] >>666 立派でもなんでもない普通の話。 単一の尺度しか使えない人間がおかしい。 694 名前：１３２人目の素数さん [2022/10/24(月) 00:41:20.74 ID:+y5g9lSl.net] Σ1/(n+i)って発散するんですか？ ダランベールの判定法を使うと収束しそうなんですが…… 695 名前：１３２人目の素数さん mailto:sage [2022/10/24(月) 00:53:24.28 ID:+apjz/4q.net] Σ1/(n+i)が収束→Σ1/(n+i)、1/(n-i)が収束→Σn/(n²+1)が収束→Σn/(n²+1) + 1/(n(n²+1))が収束→Σ( n/(n²+1) + 1/(n(n²+1)) ) = Σ1/nが収束 696 名前：１３２人目の素数さん [2022/10/24(月) 01:27:59.89 ID:gxR2VJPY.net] >>670 Σ1/nから有限個の項がないだけなので発散する。(これじゃ納得いかないか？ ダランベール判定法だと1になって収束発散は判定できないと思うが。 考えの詳細を書いてもらわないとこれ以上はコメントできないな。 697 名前：１３２人目の素数さん [2022/10/24(月) 06:36:25.48 ID:NqDJNPzo.net] >>669 他人をおかしいと言い切るのはご立派で無くてはできませんね 698 名前：１３２人目の素数さん [2022/10/24(月) 07:04:49.48 ID:GaDzP1V7.net] 自分に対するどんな批判も許さないというのは プーチンのように 老い先短いものにのみ許された特権かもしれない 699 名前：１３２人目の素数さん [2022/10/24(月) 09:20:07.31 ID:+y5g9lSl.net] >>672 Σ1/n自体は収束しますよね？ だから有限個の項を取り除いたΣ1/(n+i)も収束するんじゃ……？ ダランベールの判定法は1になると判定できないんですね 勘違いしてました 700 名前：１３２人目の素数さん [2022/10/24(月) 09:55:21.35 ID:RVVdPxf0.net] >>673 >>666については言いきれ 701 名前：る [] [ここ壊れてます] 702 名前：１３２人目の素数さん [2022/10/24(月) 10:41:00.43 ID:nK7uX7AC.net] >>675 2^k/leq n <2^{{k+1}}-->1+1/2+/cdots+1/n>(k+1)/2. n/to/inftyならk/to/inftyなので Σ1/n=/infty 703 名前：１３２人目の素数さん mailto:sage [2022/10/24(月) 10:55:22.47 ID:rexIrF14.net] さすがにネタ 704 名前：１３２人目の素数さん [2022/10/24(月) 10:57:17.82 ID:Y4d1F0jj.net] >>675 調和級数は発散します 高校生でも知ってると思いますけど 705 名前：１３２人目の素数さん [2022/10/24(月) 10:59:27.70 ID:+y5g9lSl.net] 調和級数を知らなかった……お恥ずかしい…… Σ1/nは発散するので有限個の項を抜いただけのΣ1/(n+i)も発散する、と 調和級数を使わずにΣ1/(n+i)単体で証明する方法とかって他にありますかね？ コーシーもダランベールも使えないので難しいですか 706 名前：１３２人目の素数さん [2022/10/24(月) 11:04:38.27 ID:ZMzmMyLF.net] >>676 >>663がご立派な方からのご指南であることも論を俟ちませんね 707 名前：１３２人目の素数さん [2022/10/24(月) 11:05:05.66 ID:nK7uX7AC.net] >>680 >>Σ1/nは発散するので有限個の項を抜いただけのΣ1/(n+i)も発散する iは自然数であって虚数単位ではなかった？ 708 名前：１３２人目の素数さん [2022/10/24(月) 11:13:53.19 ID:+y5g9lSl.net] >>682 iは虚数単位です あれ虚数単位だと有限個の項を抜いて調和級数になるわけじゃない……？ 頭がごちゃごちゃになってきた…… 709 名前：１３２人目の素数さん mailto:sage [2022/10/24(月) 12:07:43.74 ID:GwN+2kc1.net] 気持ち悪い文末の「…」をNGにした 710 名前：１３２人目の素数さん [2022/10/24(月) 12:41:11.28 ID:+y5g9lSl.net] >>684 癖でつけてました不快にさせてすみません 711 名前：１３２人目の素数さん [2022/10/24(月) 13:12:20.23 ID:WhN3UlUK.net] …のかわりに(´・ω・`)使うとキモさがパワーアップしていいよ 712 名前：１３２人目の素数さん [2022/10/25(火) 09:30:37.43 ID:PmjaftZ2.net] 二項分布B(n, p)がnが大きいとき、正規分布で近似できるという定理を証明するのに必要な 予備知識は何ですか？ 713 名前：１３２人目の素数さん mailto:sage [2022/10/25(火) 09:39:22.89 ID:wusYNZro.net] Levyの反転公式とか 714 名前：１３２人目の素数さん mailto:sage [2022/10/25(火) 09:41:08.17 ID:wusYNZro.net] イヤ, crtではなくて2項分布限定ならstiringの公式だけでもなんとかなるか 715 名前：１３２人目の素数さん [2022/10/25(火) 10:17:52.70 ID:PmjaftZ2.net] >>688-689 ありがとうございました。 純粋に解析学の結果だと思いますが、微分積分の本で演習問題か何かで証明している本はないですか？ 716 名前：１３２人目の素数さん [2022/10/25(火) 10:36:54.58 ID:R1CUsz0D.net] >>687 個数が多いと独立に近づいていく 717 名前：１３２人目の素数さん mailto:sage [2022/10/25(火) 10:47:35.28 ID:wusYNZro.net] >>690 Levy の反転公式はちょっと高度、教科書でさがすなら数学科の専門課程で読むレベルの教科書当たらないと難しい Stiringの公式はそうでもない、般教のレベルの教科書に載ってる 具体的にと言われると俺の読んだ教科書はもう絶版してる でも今の時代なら今のキーワードでググればアホほどネットに転がってる 718 名前：１３２人目の素数さん [2022/10/25(火) 13:04:36.00 ID:PmjaftZ2.net] >>691-692 ありがとうございました。 >>692 ネットで探してみます。 719 名前：１３２人目の素数さん mailto:sage [2022/10/25(火) 16:42:04.11 ID:NushXwQu.net] 三行目の式変形がわからなくて困ってる　どうしたら1/xが出てくるんだ 初歩的な質問で申し訳ない https://imgur.com/a/99y9zEX 720 名前：１３２人目の素数さん [2022/10/25(火) 17:11:46.34 ID:PmjaftZ2.net] 甘利俊一さんの情報理論の本ですね。 721 名前：１３２人目の素数さん [2022/10/25(火) 17:16:27.43 ID:PmjaftZ2.net] f(x + ε * x) = f(1 + ε) + f(x) f(x + ε * x) - f(x) = f(1 + ε) この両辺を ε * x で割ると、 [f(x + ε * x) - f(x)] / [ε * x] = (1/x) * f(1 + ε) / ε となる。 ということだと思います。 722 名前：１３２人目の素数さん [2022/10/25(火) 18:05:16.84 ID:PmjaftZ2.net] 以下のコードが配列 A を昇順にソートすることを証明せよ。 for i in range(N): 723 名前： ■■for j in range(N): ■■■■if A[i] < A[j]: ■■■■■■swap(A[i], A[j]) [] [ここ壊れてます] 724 名前：１３２人目の素数さん [2022/10/25(火) 18:24:25.90 ID:J3r5rMEr.net] >>694 左辺の分母εxじゃん 725 名前：１３２人目の素数さん mailto:sage [2022/10/25(火) 19:35:35.09 ID:x3m7p8p/.net] for loop でi はrange(A)(だよね)の小さい方から呼ばれるのは確定してるん？ 726 名前：１３２人目の素数さん [2022/10/25(火) 19:39:56.71 ID:PmjaftZ2.net] >>699 C++風に書くと、以下のコードになります。 vector<int> A(N); for (int i = 0; i < N; ++i) { ■■cin >> A[i]; } for (int i = 0; i < N; ++i) { ■■for (int j = 0; j < N; ++j) { ■■■■if (A[i] < A[j]) { ■■■■■■swap(A[i], A[j]); ■■■■} ■■} } 727 名前：１３２人目の素数さん mailto:sage [2022/10/25(火) 20:41:41.34 ID:qRcqF8Uu.net] >>700 Aのサイズに関するinduction ♯A = 1なら自明 ♯A<Nではよいとして♯A=Nとする i = 1 で内ループが終わった状態ではA[1]に最大元が移動する ここでi:2〜N-1でのステップでj=Nとなる時点では必ずA[i]は最大元が入ることになるので事実上A[N]は動かない よってループはサイズがひとつ小さいサイズのArrayに対して行なっている操作と同じになる、ただしiが2〜しか走っていないが、仮に改めてもう一度i:1〜N-1で走らせてもA[1]に最大元が入っている状態からスタートなのでどのみちi=1の時点では何も起こらない事に注意する よってi:2〜N-1まで走らせた時点で帰納法の仮定からA[1]〜A[N-1]は昇順に並んでいる この状態で最後のi=Nのステップで全て昇順になる事は容易である□ 728 名前：１３２人目の素数さん mailto:sage [2022/10/26(水) 00:30:01.50 ID:P3jpJ7pP.net] 補題　長さNのarray A[0]〜A[N-1]においてA[0]〜A[N-2]は昇順であるとする ここに次のコードをapplyすると全体が昇順にソートされる i = N-1; for (int j = 0; j < N; ++j) { 　if (A[i] < A[j]) { 　　swap(A[i], A[j]); 　} } (∵) Nについての帰納法 N=1なら自明 N<Mで成立するとしてN=Mとする j=0での処理を終えた時点でA[0]が最小元となるのは自明 またA[1]〜A[N-2]は昇順でここにi=1から始まるコードをapplyすればA[1]〜A[N-1]は帰納法の仮定により昇順にソートされる□ 729 名前：１３２人目の素数さん mailto:sage [2022/10/26(水) 00:30:40.36 ID:P3jpJ7pP.net] 主張の証明 ♯A < N で成立すると仮定して♯A = Nとする コードを次のように変更しても結果は変わらない i = 0; for (int j = 0; j < N; ++j) { 　if (A[i] < A[j]) { 　　swap(A[i], A[j]); 　} } for (int i = 0; i < N-1; ++i) { 　for (int j = 0; j < N-1; ++j) { 　　if (A[i] < A[j]) { 　　　swap(A[i], A[j]); 　　} 　} } i = N-1; for (int j = 0; j < N; ++j) { 　if (A[i] < A[j]) { 　　swap(A[i], A[j]); 　} } (∵ 元のコードでi=0の処理が終わった時点でA[0]には最大元が入っている 一方で各1≦i<N-1にたいしてj<N-1の処理が終わった段階ではA[i]にはA[0]〜A[N-2]の最大元が入る よってこの時点でA[i]には全体の最大元が入ることになる よって続くj=N-1のときの処理ではifの条件は常にFalseであり処理が行われる事はない よって1≦i<N-1, j=N-1の時の処理は省いても結果は変わらない) ここで帰納法の仮定により改変後のコードにおいて最後のループを始める前の時点ではA[0]〜A[N-2]は昇順になっている この状態で最後のループによって昇順になる事は既に補題で示されている□ 730 名前：１３２人目の素数さん mailto:sage [2022/10/26(水) 04:40:11.07 ID:cHlveV8v.net] >>696, 698 ありがとうございます、助かりました 731 名前：１３２人目の素数さん [2022/10/26(水) 06:56:09.62 ID:Vss1j+8B.net] >>701-703 多分正解だと思いますが、正当性を記述するのって面倒ですね。 732 名前：１３２人目の素数さん [2022/10/26(水) 10:15:21.88 ID:Vss1j+8B.net] >>697,700 著者の解答は以下です： github.com/E869120/math-algorithm-book/blob/main/editorial/chap3-6/chap3-6.pdf これって間違っていませんか？ 733 名前：１３２人目の素数さん mailto:sage [2022/10/26(水) 10:37:34.59 ID:rvp30j2k.net] まぁダメやろな i = 0〜N-2まで動く時もjは0〜N-1まで動いてしまうためにi:0〜N-2の時の動作結果は“帰納法の仮定”を適用できんからな 734 名前：１３２人目の素数さん mailto:sage [2022/10/26(水) 11:38:43.03 ID:8peJPiGV.net] >>706 735 名前： だいたい合ってるよ 細かいこと言うならこんな感じ↓ i=I-1の ”内側 j ループ終了の” 時点で、A[t−1] ≦ A[I] ”<” A[t]のとき .. . . • j=t+1,..., I−1でもswapされる。 結果は同じだが A[I]=A[j] の時は swapされない swap過程で A[1]≦A[2]≦...≦A[I-1] 順序に変化は起きないことは明らか • それ以降: A[I] の値が増える可能性はあるが、減ることはない j=I−1 直後は A[I-1] ≦ A[I] とは限らないが jループ終了後は A[I] に最大値が入ることは明らか その結果 A[1]≦A[2]≦...≦A[I-1] ≦A[I] となる. [] [ここ壊れてます] 736 名前：708 mailto:sage [2022/10/26(水) 14:06:51.89 ID:8peJPiGV.net] > j=I−1 直後は A[I-1] ≦ A[I] とは限らないが ↑ 少し訂正 I = 0 の場合: 明らかに内側 j ループ終了時点で A[I] に最大値が入る. I > 0 の場合: 内側 j ループ ”処理開始”時点で A[I-1] に最大値が入っている(※帰納法の仮定に加える)ので j=I-1 で swap が起きたら A[I-1] < A[I] , 起きなければ A[I-1] = A[I] のまま変わらない. いずれにしろ j=I-1 ”処理終了”時点で　A[I-1] ≦ A[I] が確定して A[I] に最大値が入る. j=I 以降で swap は生じない. 737 名前：１３２人目の素数さん mailto:sage [2022/10/26(水) 18:28:46.82 ID:i/+rfYjL.net] まぁ二重の帰納法で受験数学の問題だとかなり難問だよな 738 名前：１３２人目の素数さん [2022/10/26(水) 20:47:56.30 ID:KTa78anx.net] >>705 プログラムの正当性の証明を与える理論があったような気がする 帰納法で証明するなら 「内側のループ抜けた時点でそこまでのソートが終了している」 という命題にするのね 739 名前：１３２人目の素数さん [2022/10/27(木) 20:03:51.08 ID:dVXdGNpU.net] atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bi f : N → N を f(n) が n の約数の個数であるような関数とする。 1 * f(1) + 2 * f(2) + … + n * f(n) の値を O(n) で出力する方法を述べよ。 740 名前：１３２人目の素数さん [2022/10/27(木) 20:04:43.63 ID:dVXdGNpU.net] >>707-711 ありがとうございました。 741 名前：１３２人目の素数さん [2022/10/27(木) 20:06:25.53 ID:dVXdGNpU.net] リンク先を間違えました。訂正します。 atcoder.jp/contests/math-and-algorithm/tasks/abc172_d f : N → N を f(n) が n の約数の個数であるような関数とする。 1 * f(1) + 2 * f(2) + … + n * f(n) の値を O(n) で出力する方法を述べよ。 742 名前：１３２人目の素数さん [2022/10/27(木) 20:56:35.09 ID:dVXdGNpU.net] あ、分かりました。 農{d = 1}^{n} d * (floor(n/d) * (floor(n/d) + 1)) / 2 これで Θ(n) で計算できますね。 743 名前：１３２人目の素数さん mailto:sage [2022/10/27(木) 21:49:23.36 ID:TYQqpd07.net] >>715 どうしてこれで計算できるのか、誰か教えてください 744 名前：１３２人目の素数さん mailto:sage [2022/10/28(金) 01:21:30.81 ID:lv2p8O4G.net] 1 * f(1) + 2 * f(2) + … + n * f(n) = Σ[ m ≦ n ]Σ[ d ≦ n, d | m ] m = Σ[ d ≦ n ]Σ[ m ≦ n, d | m ] m = Σ[ d ≦ n ]( d + 2d + 3d + ... + ⌊n/d⌋d ) = Σ[ d ≦ n ] d⌊n/d⌋(⌊n/d⌋+1)/2 745 名前：１３２人目の素数さん mailto:sage [2022/10/28(金) 08:04:37.22 ID:7H6AX/lv.net] >>717 ありがとうございます、理解できました Σ[ m ≦ n ]Σ[ d ≦ m, d | m ] m = Σ[m ≦ n]Σ[d ≦ m] m * θ(d|m) { θ(expr) := expr ? 1 : 0 } = Σ[m ≦ n]Σ[d ≦ n ] m * θ(d|m) = Σ[d ≦ n]Σ[m ≦ n] m * θ(d|m) =Σ[d ≦ n] { d + 2d + ... + floor(n/d)*d } = ... 746 名前：１３２人目の素数さん [2022/10/28(金) 09:47:19.16 ID:Fb3X/X4M.net] 以下は、高校の教科書からの引用です。 (1) 次に、 U の中に、2つの事象 A, B がある場合を考えよう。 このとき、次のような事象を考えることが多い。 A, B がともに起こる事象 A ∩ B A, B の少なくとも一方が起こる事象 A ∪ B ----------------------------------------------------------- (2) 1枚の硬貨を投げる試行を T_1、1つのサイコロを投げる試行を T_2 とし、試行 T_1 と試行 T_2 を組み合わせた試行を考える。 この試行において、 硬貨では表が出る事象を A, サイコロでは 1 または 2 の目が出る事象を B とするとき、確率 P(A ∩ B) を求めてみよう。 ----------------------------------------------------------- (1)では、全事象 U というのがあって、 A, B はその中の事象です。 (2)では、 T_1 に対応する全事象 U_1 があり、 T_2 に対応する 全事象 U_2 があります。 A は U_1 の中の事象であり、 B は U_2 の中の事象です。それにもかかわらず、「確率 P(A ∩ B) を求めてみよう」 などと平然と書いています。 A ∩ B などというものは考えられないにもかかわらず。 747 名前：１３２人目の素数さん mailto:age [2022/10/28(金) 10:11:13.31 ID:lqOqCRZy.net] このスレを見ていると 3流の国立や私立大の理系への考えが変わったわ。 「3流大でも入学後にちゃんと勉強して単位をとってたら それなりに出来るようになるんやなぁ」 って。 であるならば、入学試験の6科目の受験勉強、 あれは何だったんだろうな。 過剰な学力の訓練・要求に思えてきた。 だって入学後にちゃんと大学レベルの数学、解析学についていけるやん？ ち、ちなみに謙虚な神戸大卒 TOEIC700です…( ; ‘ω‘) ﾊｧﾊｧ 748 名前：１３２人目の素数さん mailto:sage [2022/10/28(金) 10:25:55.37 ID:7H6AX/lv.net] >>719 高校数学は変な縛りがあるんで執筆者も雑なのは分かってて書いてると思います この場合の全事象 U は積空間の U_1 × U_2 に 事象 A は A × U_2, 事象 B は U_1 × B に読み替えるべきですね 749 名前：１３２人目の素数さん mailto:sage [2022/10/28(金) 10:30:44.97 ID:jgM6IsNM.net] >>720 三流大学や四流大学と認定される大学の学生さんが、ちゃんと学べていないのは、 入試ができない人が学ぶことができないというよりもむしろ、 「三流や四流の自分が勉強しても仕方ない」という意識を持つからだろうね 実際、日本の学力テストが素質を測れるという根拠は存在しない これは日本の人材の損失で、少子化で更に人材が減っていく以上、三流や四流みたいな固定観念を撤廃していかない限り日本が他の国々に差をつけられていくのは必定だと思う 750 名前：１３２人目の素数さん mailto:age [2022/10/28(金) 11:40:23.68 ID:lqOqCRZy.net] >>722 一般入試組が受験オタク、学力厨という事実が 明るみになってきてますし 今はAO入試・指定校推薦が 入学者の半分近くっていう大学も多いですね。 (下手したら、学力の高いはずの人々が 大学の成績でAO・指定校などの学力の低めの人に負けている場合さえある) 751 名前：１３２人目の素数さん [2022/10/28(金) 11:57:16.81 ID:FpKcJleB.net] また部外者君か 752 名前：１３２人目の素数さん [2022/10/28(金) 12:02:15.89 ID:FpKcJleB.net] >>723 AOと推薦がどうしようもないのは2流3流大の場合 1流と4流では大して違いない ていうか４流では入試機能しないからな 753 名前：１３２人目の素数さん mailto:sage [2022/10/28(金) 12:32:54.51 ID:zGG7ayBU.net] >>723 東北大、早稲田大で、AO入学者のほうが成績が良いというデータもあるしね 成績が最もいいのはAO入学者　東北大、早稲田大の内部資料で判明 https://www.asahi.com/edua/article/14540038 入試のあり方を今一度見直したほうが良いだろうな、 共通一次が1979年に導入されて以降見直しが殆どないのもどうかと思うし 754 名前：１３２人目の素数さん [2022/10/28(金) 12:36:44.59 ID:FpKcJleB.net] >>726 ここでやる話題ではないし 1流大のAOによい学生が集まるのは当然 枠が増えれば低劣になるだろうも当然 755 名前：１３２人目の素数さん mailto:sage [2022/10/28(金) 12:44:56.72 ID:zGG7ayBU.net] >>727 例えば京都大学の学生数が22,785で、 イギリスのオックスフォード 756 名前：大学が11,930 イギリスの人口が6733万人で日本の1/2しかないことを考えると、 オックスフォード大学はかなり京都大学より枠を広げてるわけだけど、 間違いなく質はオックスフォード大学のほうが京都大学より上だよね？ [] [ここ壊れてます] 757 名前：１３２人目の素数さん mailto:sage [2022/10/28(金) 12:48:20.49 ID:zGG7ayBU.net] オックスフォード大学は京都大学と同じくらいの枠だな、すまん とはいえ、同じくらいの枠でオックスフォード大学のほうが京都大学よりずっと上ということは、 やはり京都大学の学生さんに優秀な人が集まっているとは言えないと思う それはつまり、入試という物差しが優秀さを測ってはいないということだよね 758 名前：１３２人目の素数さん [2022/10/29(土) 09:18:23.92 ID:dxAYdFmh.net] K を自然数とする。 M を K の倍数の集合とする。 N を自然数の集合とする。 f : N → N を f(n) が n を10進法で表したときの各桁の和であるような関数とする。 min {f(n) | n ∈ M} を O(K * log(K)) で計算する方法を述べよ。 759 名前：１３２人目の素数さん [2022/10/29(土) 09:19:36.57 ID:dxAYdFmh.net] N を自然数の集合とする。 K ∈ N とする。 M ⊂ N を K の倍数の集合とする。 f : N → N を f(n) が n を10進法で表したときの各桁の和であるような関数とする。 min {f(n) | n ∈ M} を O(K * log(K)) で計算する方法を述べよ。 760 名前：１３２人目の素数さん mailto:sage [2022/10/29(土) 09:37:37.51 ID:vKZvh9tp.net] g(K) = min {f(n) | n ∈ M} = 1 761 名前：１３２人目の素数さん [2022/10/29(土) 10:06:22.86 ID:dxAYdFmh.net] >>732 不正解です。 762 名前：１３２人目の素数さん mailto:sage [2022/10/29(土) 10:18:10.55 ID:aLXm9oeN.net] >>732 おっと、そりゃそうだ 確認だけど四則演算はO(1)でいいんやな？ 763 名前：１３２人目の素数さん [2022/10/29(土) 11:09:16.64 ID:dxAYdFmh.net] >>734 はい。 764 名前：１３２人目の素数さん mailto:sage [2022/10/29(土) 17:33:04.91 ID:FyC0Ec0W.net] まだdebugしてないけど for(i=0; i<K; i++) A[i] = K; for(i=0; i<K; i++){ 　for(f=1; f<10; f++){ 　　A[ (10^i * f)%K ] 　　　= min ( A[ (10^i * f)%K ], f ); 　} } m = 0; while(A[0]>m){ 　i = 0; 　for(j=0; j<K; j++){ 　　if( A[j]>m && A[j]<A[i] ) i=j; 　} 　m=A[i]; 　for(f = 1; f<10; f++){ 　　for(j=0; j<K; j++]{ 　　　A[ ( i+10^j * f)%K ] 　= min(A[( i + 10^j * f )%K], A[ i ]+f ); 　　} 　} } 765 名前：１３２人目の素数さん [2022/10/29(土) 17:42:21.55 ID:dxAYdFmh.net] >>736 書きませんでしたが、 >>731 は、以下の問題です。 atcoder.jp/contests/math-and-algorithm/tasks/arc084_b 766 名前：１３２人目の素数さん [2022/10/29(土) 17:43:03.30 ID:dxAYdFmh.net] いままで見た競技プログラミングの問題の中でも、いい問題だと思いました。 767 名前：１３２人目の素数さん [2022/10/29(土) 17:49:33.11 ID:dxAYdFmh.net] >>736 コードの内容は見ていませんが、最終的に答えは A のどの要素に入っているんですか？ 768 名前：１３２人目の素数さん mailto:sage [2022/10/29(土) 17:51:14.90 ID:FyC0Ec0W.net] >>739 A[0] 769 名前：１３２人目の素数さん [2022/10/29(土) 18:07:44.42 ID:dxAYdFmh.net] ideone.com/GSFtad 間違っているようです。 770 名前：１３２人目の素数さん [2022/10/29(土) 18:11:45.06 ID:mKrwvqce.net] プログラミングの人居着いちゃったけど 出来たら別スレでやってくれないかな 771 名前：１３２人目の素数さん mailto:sage [2022/10/29(土) 18:55:32.41 ID:FyC0Ec0W.net] せやね プログラミングスレの方がいいかもね 772 名前：１３２人目の素数さん mailto:sage [2022/10/29(土) 19:12:08.74 ID:FyC0Ec0W.net] 書いてきた https://mevius.5ch.net/test/read.cgi/tech/1624028577/845 プログラミングのお題スレ Part20 773 名前：１３２人目の素数さん mailto:sage [2022/10/30(日) 02:36:16.07 ID:jzYKBiql.net] そもそもコレ本当にO(Klog(K))でできるん？ グラフのサイズV = K, E = K²だよな？ 探索アルゴリズムこのサイズのグラフでKlog(K)のやつはグクっても見つからないんだけど 774 名前：１３２人目の素数さん [2022/10/30(日) 04:55:48.16 ID:7xF2sv+k.net] どのようなグラフを考えているのか知りませんが、 #E = 10 * K のグラフを考えるのが普通ではないでしょうか？ 775 名前：１３２人目の素数さん mailto:sage [2022/10/30(日) 09:56:14.75 ID:y/CG6F55.net] >>748 イヤ、普通に V = {0,1,2,3,4,...} E = {(p,q,f) ∈ V×V | f∈{1,2,..,9 }, ∃e∈ℤ, p-q ≡ f×10ᵉ ( mod K ) } w((p,q,f)) = f で1〜9の重� 776 名前：ﾝ付き有向グラフの単経路問題 コレが1番普通だと思うけど これだとちょっと必然的に♯E = O(K²)になるよ [] [ここ壊れてます] 777 名前：１３２人目の素数さん mailto:age [2022/10/30(日) 10:08:37.85 ID:AezHc4Ib.net] 最近、スレのレベルが落ちてるんちゃうかな？ 778 名前：１３２人目の素数さん [2022/10/30(日) 10:14:02.25 ID:e4jmSuJH.net] ウィキペディアに、累次積分(逐次積分)と多重積分が違うものだと書かれているのですが、本当ですか？ > 逐次積分の概念を考えるに当たり一つ重要な点としては、これは多重積分とは原則として異なる概念であるということが挙げられる。すなわち、一般にはこの二つは異なるのであるけれども、それでも十分緩やかな条件下でこれらが一致することを主張するフビニの定理が知られている。 https://ja.m.wikipedia.org/wiki/%E9%80%90%E6%AC%A1%E7%A9%8D%E5%88%86 何が違いますか？ 779 名前：１３２人目の素数さん mailto:sage [2022/10/30(日) 10:17:10.47 ID:y/CG6F55.net] >>749 何が違うも何も明らかに定義違うやん 両方の定義書いてみればいい 780 名前：１３２人目の素数さん mailto:sage [2022/10/30(日) 10:26:31.96 ID:y/CG6F55.net] >>746 そもそもホントにO(Klog(K))のプログラム作って実証実験した？ どっかのフリーideにうpしてよ 781 名前：１３２人目の素数さん [2022/10/30(日) 10:29:00.44 ID:7xF2sv+k.net] >>747,751 github.com/E869120/math-algorithm-book/blob/main/editorial/chap4-5/chap4-5.pdf 問題5.4.8の解答を見てください。 782 名前：１３２人目の素数さん [2022/10/30(日) 10:30:05.71 ID:7xF2sv+k.net] 訂正します： >>747,751 github.com/E869120/math-algorithm-book/blob/main/editorial/chap4-5/chap4-5.pdf 問題4.5.8の解答を見てください。 783 名前：１３２人目の素数さん [2022/10/30(日) 10:31:32.58 ID:7xF2sv+k.net] #E = 10 * K - 1 ダイクストラのアルゴリズムを使います。 784 名前：１３２人目の素数さん [2022/10/30(日) 10:36:47.46 ID:7xF2sv+k.net] ダイクストラのアルゴリズムは、priority queueを使うバージョンです。

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef