データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4 (105ﾚｽ)
上下前次1-新
50: 2021/10/12(火)07:51 ID:9oya6EGe(1) AAS
>>49
ありがとうございました。
『アルゴリズム実技検定』でのコードは、トップダウン方式ですので、「トポロジカルソート」などという言葉を出さなくても良かったわけですね。
51: 2021/10/15(金)14:52 ID:n9WPu0Ca(1/2) AAS
外部ﾘﾝｸ:atcoder.jp
↑の問題を↓のように解きました。
外部ﾘﾝｸ:ideone.com
コメントアウトしている行をアンコメントするとジェッジにパスしなくなります。
理由が分かりません。
理由が分かる方、教えて下さい。
52: 2021/10/15(金)15:11 ID:n9WPu0Ca(2/2) AAS
あ、わかりました。
53: 2021/10/15(金)15:13 ID:/Buyr3BY(1) AAS
よかったね、さようなら
54(1): 2021/10/24(日)20:12 ID:tzzO99P4(1) AAS
外部ﾘﾝｸ:atcoder.jp
この問題は貪欲法が適用できるとのことですが、適用できることの証明はどう証明するのでしょうか？
55: 2021/10/24(日)22:55 ID:340Kt+5N(1) AAS
>>54
k日間で得られるポイントの合計の最大値を P(k) と表し、k日目に解禁されるタスクが2つあってそれぞれのポイントを p, q (p < q) とする。
貪欲法でないやり方で求めた最適解P(k)*があるとする。--- (1)
貪欲法でないある方針に基づいてpポイントのタスクを選択したとする。
このとき、貪欲法に基づいてqポイントのタスクを選択したとすると、P(k) = P(k)* + q - p となる更に良い解が得られ、(1) の「貪欲法でなくても最適解」の前提条件に矛盾する。
毎回思うけどこの atcoder てあんまり良くないね。
日本語の問題文があるから重宝されてるのかもしれないけど、入力のサイズが小さすぎてブルートフォースでも瞬時に解けたり、解説ないからもっと良い解があるのかわからないし、leetcode あたりのが勉強になると思う。
56: 2021/10/25(月)11:24 ID:vmRZrQEp(1) AAS
まるちんこ
57: 2021/10/25(月)12:10 ID:Ex1ycVpJ(1/2) AAS
以下のような感じで証明できないですかね？
タスク 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})
58: 2021/10/25(月)16:58 ID:Ex1ycVpJ(2/2) AAS
Introduction to Algorithms 3rd Editionがくどすぎて読みにくい。
59: 2021/10/26(火)11:19 ID:CwYCZWUI(1/2) AAS
タスク 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})
が成り立つ。
60: 2021/10/26(火)11:33 ID:CwYCZWUI(2/2) AAS
このとき、長さ 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 は空集合である。
61(1): 2021/10/31(日)19:17 ID:BY7qrcrb(1) AAS
外部ﾘﾝｸ:atcoder.jp
↓途中の段階で最終的に得られる互いの幸福度の総和をどうやって彼らは知るのでしょうか？
ただし、彼らはともに、「最終的に自分が得る幸福度の総和」から「最終的に相手が得る幸福度の総和」を引いた値を最大化するように料理を選びます。
このとき、「最終的に高橋くんが得る幸福度の総和」から「最終的に青木さんが得る幸福度の総和」を引いた値はいくつになるでしょうか？
62: 2021/11/02(火)10:37 ID:px0qcy1y(1) AAS
>>61
動画ﾘﾝｸ[YouTube]
63: 2021/11/02(火)13:38 ID:RQoewYsN(1) AAS
『Introduction to Algorithms 3rd Edition』よりも『Algorithm Design』のほうがずっといい本だと思うのですが、どうですか？
64: 2021/11/03(水)18:42 ID:K+j19pQn(1/2) AAS
画像ﾘﾝｸ
↑は、Dijkstraのアルゴリズムの擬似コードですが、これって間違っていますよね？
Sに付け加えられるvに対してのみd[v]を計算しています。
65(1): 2021/11/03(水)19:10 ID:p70BP33u(1) AAS
追加される時点で最短距離が決定するから問題ないと思うが。
66: 2021/11/03(水)19:38 ID:K+j19pQn(2/2) AAS
>>65
ありがとうございました。
あ、d'[v]のほうは更新され続けるんですね。
そして、最後に、Sに入れられるときに、d[v]に確定したd'[v]の値を入れているんですね。
dなんて使わずにd'だけでいいのにと思います。
67(1): 2022/03/05(土)12:18 ID:c2cv6ICZ(1) AAS
画像ﾘﾝｸ
68: 2022/03/05(土)18:15 ID:2/qEYPh4(1) AAS
>>67
グロ
69: 2022/04/09(土)22:56 ID:NDf9sYGT(1) AAS
頭では分かってるつもりなんだけど
どうしても実際にはif , switchのオンパレードになっちゃんだよな
特に仕事だと、学術論的なことでぐずぐずハマってたら
なにやってんだってはなしになることが多い
70: 2022/08/31(水)20:45 ID:CIcCYvEQ(1/4) AAS
『アルゴリズム実技検定公式テキスト』という本に以下の最長パスの問題の出題と解答が書いてあります．
外部ﾘﾝｸ:atcoder.jp
解説を読むと，この問題を解くのに，トポロジカルソートが重要だと書いてあります．
71: 2022/08/31(水)20:52 ID:CIcCYvEQ(2/4) AAS
解答は以下のような感じです：
length(v)を点vからの最長パスの長さとします．
v → w_1
v → w_2
…
v → w_n
という辺があるとき，length(v) = max{length(w_1), …, length(w_n)}
とメモ化再帰により計算する．（深さ優先探索を使う．）
この解答のどこでトポロジカルソートの考えが使われているのかが分かりません．
72: 2022/08/31(水)20:55 ID:CIcCYvEQ(3/4) AAS
入次数が0の点達からメモ化再帰（深さ優先探索）を行っています．
73: 2022/08/31(水)20:58 ID:CIcCYvEQ(4/4) AAS
外部ﾘﾝｸ:ideone.com
例えば，上のプログラムのような感じです．
74: 2022/09/01(木)09:35 ID:NAQLmVKw(1) AAS
入字数0の点が最長パスの始点候補だから、トポロジカルソートしたら始点から終点までの経路上の辺の長さをを足し合わせていけばいい
75(1): 2022/09/04(日)06:43 ID:x0sSmgMe(1) AAS
でもトポロジカルソートしていないですよね．プログラムを見ると．
76(1): 2022/09/18(日)14:40 ID:suxGffYa(1) AAS
C++の連結リスト(list)の削除に必要な計算量がO(1)であると大槻の本に書いてあるのですが、
削除したい要素を探すのにO(N)必要だと思います。
これって単に、指定した位置の要素を削除するという操作だからO(1)ということですか？
77: 2022/09/18(日)15:28 ID:69Jy4am9(1) AAS
知らね。前後の文脈含めてなんて書いてあるの？
78: 2022/09/19(月)12:07 ID:yWkM0kBX(1) AAS
>>76
そう
指定した位置というか指定したノードだけど
79: 2022/09/20(火)01:12 ID:zbB+YFPz(1) AAS
>>75
トポロジカルソートが重要かはよくわからんけど
状態空間も遷移の考えもほとんど同じじゃん
上下前次1-新書関写板覧索設栞歴
あと 26 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ
ぬこの手 ぬこTOP 0.007s