データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4 (105ﾚｽ)
データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4 http://mevius.5ch.net/test/read.cgi/tech/1580131715/
上
下
前
次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
53: デフォルトの名無しさん [sage] 2021/10/15(金) 15:13:27.96 ID:/Buyr3BY よかったね、さようなら http://mevius.5ch.net/test/read.cgi/tech/1580131715/53
54: デフォルトの名無しさん [] 2021/10/24(日) 20:12:12.31 ID:tzzO99P4 https://atcoder.jp/contests/past202004-open/tasks/past202004_f この問題は貪欲法が適用できるとのことですが、適用できることの証明はどう証明するのでしょうか？ http://mevius.5ch.net/test/read.cgi/tech/1580131715/54
55: デフォルトの名無しさん [sage] 2021/10/24(日) 22:55:10.72 ID:340Kt+5N >>54 k日間で得られるポイントの合計の最大値を P(k) と表し、k日目に解禁されるタスクが2つあってそれぞれのポイントを p, q (p < q) とする。 貪欲法でないやり方で求めた最適解P(k)*があるとする。--- (1) 貪欲法でないある方針に基づいてpポイントのタスクを選択したとする。 このとき、貪欲法に基づいてqポイントのタスクを選択したとすると、P(k) = P(k)* + q - p となる更に良い解が得られ、(1) の「貪欲法でなくても最適解」の前提条件に矛盾する。 毎回思うけどこの atcoder てあんまり良くないね。 日本語の問題文があるから重宝されてるのかもしれないけど、入力のサイズが小さすぎてブルートフォースでも瞬時に解けたり、解説ないからもっと良い解があるのかわからないし、leetcode あたりのが勉強になると思う。 http://mevius.5ch.net/test/read.cgi/tech/1580131715/55
56: デフォルトの名無しさん [] 2021/10/25(月) 11:24:00.83 ID:vmRZrQEp まるちんこ http://mevius.5ch.net/test/read.cgi/tech/1580131715/56
57: デフォルトの名無しさん [] 2021/10/25(月) 12:10:28.14 ID:Ex1ycVpJ 以下のような感じで証明できないですかね？ タスク T のポイントを p(T) で表すことにする。 貪欲法によって選ばれたタスク列を T_1, T_2, …, T_n とする。 S := {(S_1, S_2, …, S_k) | 1 ≦ k ≦ n, S_i は第i日に行うタスク, p(S_1 + … + S_k) > p(T_1 + … + T_k)} S が空集合ではないとして矛盾を導く。 (S_1, S_2, …, S_l) を長さが最小の S の元とする。 p(S_1) + … + p(S_{l-1}) ≦ p(T_1) + … + p(T_{l-1}) http://mevius.5ch.net/test/read.cgi/tech/1580131715/57
58: デフォルトの名無しさん [sage] 2021/10/25(月) 16:58:37.64 ID:Ex1ycVpJ Introduction to Algorithms 3rd Editionがくどすぎて読みにくい。 http://mevius.5ch.net/test/read.cgi/tech/1580131715/58
59: デフォルトの名無しさん [] 2021/10/26(火) 11:19:31.94 ID:CwYCZWUI タスク T のポイントを p(T) で表すことにする。 貪欲法によって選ばれたタスク列を T_1, T_2, …, T_n とする。 S := {k | 1 ≦ k ≦ n, 第1日目から第k日目の間に得られるポイントの合計の最大値 > p(T_1) + … + p(T_k)} が空集合ではないと仮定して矛盾を導く。 k_0 := min S とおく。 第1日目から第k_0日目の間に得られるポイントの合計の最大値を達成するタスク列を S_1, S_2, …, S_{k_0} とする。 仮定により、 p(S_1) = p(T_1) p(S_2) = p(T_2) … p(S_{k_0-1}) = p(T_{k_0-1}) p(S_{k_0}) > p(T_{k_0}) が成り立つ。 http://mevius.5ch.net/test/read.cgi/tech/1580131715/59
60: デフォルトの名無しさん [] 2021/10/26(火) 11:33:36.58 ID:CwYCZWUI このとき、長さ n のタスク列 S_1, S_2, …, S_{k_0-1}, R_{k_0}, R_{k_0+1}, …, R_{n} で p(R_{k_0}) = p(T_{k_0}) p(R_{k_0+1}) = p(T_{k_0+1}) … p(R_{n}) = p(T_{n}) を満たすようなものが存在することは明らかである。 このタスク列 S_1, S_2, …, S_{k_0-1}, R_{k_0}, R_{k_0+1}, …, R_{n} も貪欲法によって選ばれうるタスク列である。 ところが、タスク列 S_1, S_2, …, S_{k_0-1}, R_{k_0}, R_{k_0+1}, …, R_{n} は第k_0日において、 p(S_{k_0}) > p(T_{k_0}) = p(R_{k_0}) であるにもかかわらず、 タスク S_{k_0} を選択しないタスク列であるから、このタスク列は貪欲法によって選ばれうるタスク列ではない。 これは矛盾である。 よって、 S は空集合である。 http://mevius.5ch.net/test/read.cgi/tech/1580131715/60
61: デフォルトの名無しさん [] 2021/10/31(日) 19:17:33.86 ID:BY7qrcrb https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_c ↓途中の段階で最終的に得られる互いの幸福度の総和をどうやって彼らは知るのでしょうか？ ただし、彼らはともに、「最終的に自分が得る幸福度の総和」から「最終的に相手が得る幸福度の総和」を引いた値を最大化するように料理を選びます。 このとき、「最終的に高橋くんが得る幸福度の総和」から「最終的に青木さんが得る幸福度の総和」を引いた値はいくつになるでしょうか？ http://mevius.5ch.net/test/read.cgi/tech/1580131715/61
62: デフォルトの名無しさん [] 2021/11/02(火) 10:37:08.97 ID:px0qcy1y >>61 https://www.youtube.com/watch?v=SsB8VfxgZwQ http://mevius.5ch.net/test/read.cgi/tech/1580131715/62
63: デフォルトの名無しさん [] 2021/11/02(火) 13:38:39.49 ID:RQoewYsN 『Introduction to Algorithms 3rd Edition』よりも『Algorithm Design』のほうがずっといい本だと思うのですが、どうですか？ http://mevius.5ch.net/test/read.cgi/tech/1580131715/63
64: デフォルトの名無しさん [] 2021/11/03(水) 18:42:32.00 ID:K+j19pQn https://i.imgur.com/EqwQfdx.jpg ↑は、Dijkstraのアルゴリズムの擬似コードですが、これって間違っていますよね？ Sに付け加えられるvに対してのみd[v]を計算しています。 http://mevius.5ch.net/test/read.cgi/tech/1580131715/64
65: デフォルトの名無しさん [sage] 2021/11/03(水) 19:10:00.22 ID:p70BP33u 追加される時点で最短距離が決定するから問題ないと思うが。 http://mevius.5ch.net/test/read.cgi/tech/1580131715/65
66: デフォルトの名無しさん [sage] 2021/11/03(水) 19:38:24.24 ID:K+j19pQn >>65 ありがとうございました。 あ、d'[v]のほうは更新され続けるんですね。 そして、最後に、Sに入れられるときに、d[v]に確定したd'[v]の値を入れているんですね。 dなんて使わずにd'だけでいいのにと思います。 http://mevius.5ch.net/test/read.cgi/tech/1580131715/66
67: デフォルトの名無しさん [sage] 2022/03/05(土) 12:18:28.50 ID:c2cv6ICZ https://i.imgur.com/SLWsXcA.jpg http://mevius.5ch.net/test/read.cgi/tech/1580131715/67
68: デフォルトの名無しさん [sage] 2022/03/05(土) 18:15:22.85 ID:2/qEYPh4 >>67 グロ http://mevius.5ch.net/test/read.cgi/tech/1580131715/68
69: デフォルトの名無しさん [sage] 2022/04/09(土) 22:56:02.65 ID:NDf9sYGT 頭では分かってるつもりなんだけど どうしても実際にはif , switchのオンパレードになっちゃんだよな 特に仕事だと、学術論的なことでぐずぐずハマってたら なにやってんだってはなしになることが多い http://mevius.5ch.net/test/read.cgi/tech/1580131715/69
70: デフォルトの名無しさん [] 2022/08/31(水) 20:45:30.79 ID:CIcCYvEQ 『アルゴリズム実技検定公式テキスト』という本に以下の最長パスの問題の出題と解答が書いてあります． https://atcoder.jp/contests/dp/tasks/dp_g 解説を読むと，この問題を解くのに，トポロジカルソートが重要だと書いてあります． http://mevius.5ch.net/test/read.cgi/tech/1580131715/70
71: デフォルトの名無しさん [] 2022/08/31(水) 20:52:44.34 ID:CIcCYvEQ 解答は以下のような感じです： length(v)を点vからの最長パスの長さとします． v → w_1 v → w_2 … v → w_n という辺があるとき，length(v) = max{length(w_1), …, length(w_n)} とメモ化再帰により計算する．（深さ優先探索を使う．） この解答のどこでトポロジカルソートの考えが使われているのかが分かりません． http://mevius.5ch.net/test/read.cgi/tech/1580131715/71
72: デフォルトの名無しさん [] 2022/08/31(水) 20:55:47.47 ID:CIcCYvEQ 入次数が0の点達からメモ化再帰（深さ優先探索）を行っています． http://mevius.5ch.net/test/read.cgi/tech/1580131715/72
73: デフォルトの名無しさん [] 2022/08/31(水) 20:58:25.24 ID:CIcCYvEQ https://ideone.com/LvMx0h 例えば，上のプログラムのような感じです． http://mevius.5ch.net/test/read.cgi/tech/1580131715/73
74: デフォルトの名無しさん [sage] 2022/09/01(木) 09:35:46.60 ID:NAQLmVKw 入字数0の点が最長パスの始点候補だから、トポロジカルソートしたら始点から終点までの経路上の辺の長さをを足し合わせていけばいい http://mevius.5ch.net/test/read.cgi/tech/1580131715/74
75: デフォルトの名無しさん [] 2022/09/04(日) 06:43:45.43 ID:x0sSmgMe でもトポロジカルソートしていないですよね．プログラムを見ると． http://mevius.5ch.net/test/read.cgi/tech/1580131715/75
76: デフォルトの名無しさん [] 2022/09/18(日) 14:40:45.95 ID:suxGffYa C++の連結リスト(list)の削除に必要な計算量がO(1)であると大槻の本に書いてあるのですが、 削除したい要素を探すのにO(N)必要だと思います。 これって単に、指定した位置の要素を削除するという操作だからO(1)ということですか？ http://mevius.5ch.net/test/read.cgi/tech/1580131715/76
77: デフォルトの名無しさん [sage] 2022/09/18(日) 15:28:50.46 ID:69Jy4am9 知らね。前後の文脈含めてなんて書いてあるの？ http://mevius.5ch.net/test/read.cgi/tech/1580131715/77
78: デフォルトの名無しさん [sage] 2022/09/19(月) 12:07:14.08 ID:yWkM0kBX >>76 そう 指定した位置というか指定したノードだけど http://mevius.5ch.net/test/read.cgi/tech/1580131715/78
79: デフォルトの名無しさん [sage] 2022/09/20(火) 01:12:54.08 ID:zbB+YFPz >>75 トポロジカルソートが重要かはよくわからんけど 状態空間も遷移の考えもほとんど同じじゃん http://mevius.5ch.net/test/read.cgi/tech/1580131715/79
80: デフォルトの名無しさん [] 2022/09/26(月) 15:08:47.03 ID:cqAm7B1L 比較に基づくソートの最悪の入力に対する実行時間の下限がΩ(n * log(n))であることの証明が分かりません。 http://mevius.5ch.net/test/read.cgi/tech/1580131715/80
81: デフォルトの名無しさん [] 2022/09/26(月) 15:13:01.77 ID:cqAm7B1L 決定木で説明しますが、その説明が分かりません。 http://mevius.5ch.net/test/read.cgi/tech/1580131715/81
82: デフォルトの名無しさん [sage] 2022/09/26(月) 15:53:07.65 ID:Dh3HDIpo そうか http://mevius.5ch.net/test/read.cgi/tech/1580131715/82
ﾒﾓ帳
(0/65535文字)
上
下
前
次
1-
新
書
関
写
板
覧
索
設
栞
歴
あと 23 ﾚｽあります
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.005s