データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4 (105ﾚｽ)
データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4 http://mevius.5ch.net/test/read.cgi/tech/1580131715/
上
下
前
次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
27: デフォルトの名無しさん [sage] 2021/02/27(土) 17:10:02.18 ID:cGuo4IiQ よく読んでなかったすまんかった http://mevius.5ch.net/test/read.cgi/tech/1580131715/27
28: デフォルトの名無しさん [sage] 2021/03/08(月) 16:54:28.07 ID:H4OoIpXQ 焼きなましに例えるんだからEnergyのEだろうね 線形計画法が流行ってた時代はとりあえず目標関数は最大化するものとしてた風潮があった(LPでは双対問題と厳密に等価) シュミレーション分野、最近の機械学習の流行りでとりあえずコスト関数を最小化する雰囲気 LPじゃないんで同じ点で極値を与える関数にも良し悪しがある点には気を付けねば 実数関数なら符号の反転と、並進に依らないアルゴリズムであれば並進を加えたもののみ等価 http://mevius.5ch.net/test/read.cgi/tech/1580131715/28
29: デフォルトの名無しさん [sage] 2021/03/17(水) 19:38:57.60 ID:DuV9YnX6 初歩的な質問かもしれず、恐縮ですがお願いいたします。 i Phoneを使って、端末が始点から終点まで移動した角度をx,y,z（オイラー角）で取得したいと考えています。 最初は、始点と終点の端末の位置をオイラー角で取得し、その差分を出してみたのですが、ジンバルロックによりpitchの値を正確に取得できませんでした。 ジンバルロックを回避するためクォータニオンを使うといいようなのですが、クォータニオンを使って目的の値を算出する方法が分からない状態です。 もし分かる方がおられましたら、ご助言いただると幸いです。 よろしくお願いします。 http://mevius.5ch.net/test/read.cgi/tech/1580131715/29
30: デフォルトの名無しさん [sage] 2021/05/19(水) 16:18:22.70 ID:7NWiu4qI Minimum Mean Cycleでこのスライドを見ているのですが 3ページでmaxをとっているのに正しい答えがでる理由ってなんでですか？ http://www.columbia.edu/~cs2035/courses/ieor6614.S16/mmc.pdf (d^n(v) - d^k(v)) / (n - k)はｖからスタートしたときのMean Cycleですよね d^k(v)が無限の場合を避けるためにmaxをとっていると思うのですが，なぜ正しい答えになるのでしょうか http://mevius.5ch.net/test/read.cgi/tech/1580131715/30
31: デフォルトの名無しさん [sage] 2021/05/22(土) 02:18:16.19 ID:/00w7bM8 >>29 取り敢えず理解はほっといて動けばいいのなら、ウィキペにでも公式載ってたと思うよ http://mevius.5ch.net/test/read.cgi/tech/1580131715/31
32: デフォルトの名無しさん [] 2021/10/03(日) 17:59:42.80 ID:nkudyinT 幅優先探索の計算量がO(N)ではなくO(N + E)なのはなぜ？ Nは頂点の数、Eは辺の数です。 http://mevius.5ch.net/test/read.cgi/tech/1580131715/32
33: デフォルトの名無しさん [sage] 2021/10/03(日) 20:36:41.51 ID:KyHKDHW1 辺の数だけ処理が増えるから 頂点の数を同じにして辺の数が異なる2つのグラフを比較してみればわかる http://mevius.5ch.net/test/read.cgi/tech/1580131715/33
34: デフォルトの名無しさん [sage] 2021/10/03(日) 22:55:23.59 ID:45cLxSS6 モートン順序によって当たり判定を一瞬で計算するというのがありました あれ特定の境目の上にオブジェクトがあるとすべてのオブジェクトとの衝突判定が発生するんですが 世の中のゲームってそんなふうにやってるんですか http://mevius.5ch.net/test/read.cgi/tech/1580131715/34
35: デフォルトの名無しさん [] 2021/10/04(月) 18:40:34.82 ID:N2yAdGNd 計算量がO(V + E)であるの定義は何ですか？ http://mevius.5ch.net/test/read.cgi/tech/1580131715/35
36: デフォルトの名無しさん [sage] 2021/10/04(月) 22:35:12.16 ID:qkBPKVDO それは計算量の定義をきいているのか？ http://mevius.5ch.net/test/read.cgi/tech/1580131715/36
37: デフォルトの名無しさん [sage] 2021/10/05(火) 00:11:45.95 ID:wQtjKuKa そのアルゴリズムの計算時間を f(n) とし、オーダーが O(g(n)) と表記される場合、定数cがあって、n がある程度大きくなれば常に f(n) <= c * g(n) が成り立つ。言い方を変えれば計算時間は最悪のケースでも c * g(n) を超えない g(n) が N (Nの1次式) なら計算時間は c * N を超えないし g(n) が N^2 (2次式) なら c * N^2 を超えない c はマシンのスペックや環境で変わるので具体的な数値は追求しない Nの入力サイズが10倍、100倍、...、1万倍となったときに計算時間がおおよそどのくらいのスピードで増えるか見積もれれば良い O(N) なら10倍、100倍、...、1万倍 O(N^2) なら100倍、1万倍、...、1億倍.. 詳しくはアルゴリズムの教科書か https://ja.wikipedia.org/wiki/ランダウの記号 http://mevius.5ch.net/test/read.cgi/tech/1580131715/37
38: デフォルトの名無しさん [] 2021/10/05(火) 02:13:06.84 ID:3IOuHtiP >>37 ありがとうございます。 ですが、O(V + E)の中に書かれている式であるV + Eは2変数の関数です。それでも1変数の場合と同じ定義でいいんですか？ http://mevius.5ch.net/test/read.cgi/tech/1580131715/38
39: デフォルトの名無しさん [sage] 2021/10/05(火) 03:31:33.71 ID:wQtjKuKa >>38 定義は同じ V個の頂点はそれぞれ1回キューに入れられて1回キューから取り出される E本の辺はある頂点から隣接する次の頂点を見つけるのに1度処理されるだけ 合わせてc0 * E + c1 * V の手間がかかるが、c0, c1 の大きい方を c として c0 * E + c1 * V <= c (E+V)、これは最悪でも計算量は c (E+V) を超えないことを意味し、E+V の部分が g(E+V) となる http://mevius.5ch.net/test/read.cgi/tech/1580131715/39
40: デフォルトの名無しさん [sage] 2021/10/05(火) 08:50:55.08 ID:3IOuHtiP >>39 なるほど。ありがとうございました。 http://mevius.5ch.net/test/read.cgi/tech/1580131715/40
41: デフォルトの名無しさん [] 2021/10/10(日) 18:05:52.24 ID:6QW0WSDe 以下のプログラミングコンテストの問題なのですが、『アルゴリズム実技検定』という本の解説では、これは動的計画法の問題であると書いてあります。 本当にこういうのも動的計画法と言いますか？ https://atcoder.jp/contests/abc026/tasks/abc026_c http://mevius.5ch.net/test/read.cgi/tech/1580131715/41
42: デフォルトの名無しさん [sage] 2021/10/10(日) 19:42:09.58 ID:CKYp8hS8 >>41 ツリーを作って再帰にもできそうだけど、番号の1番大きい社員から少ない社員に向かって1つずつ処理していけば動的計画法になるね 最初に各社員に部下の給料のリスト（最初は空）を持たせて、社員番号Nから2番に向かって部下の給料のリストに値があればそこから自分の給与を計算して上司のリストに加えることを繰り返す 社員N番を含めて部下がいない、自分の番が回ってきても部下の給料リストが空なら1を上司のリストに加えればいい http://mevius.5ch.net/test/read.cgi/tech/1580131715/42
43: デフォルトの名無しさん [sage] 2021/10/10(日) 20:02:45.11 ID:CKYp8hS8 部下の給与リストじゃなくて最大値と最小値だけ覚えとけばもっと賢いか http://mevius.5ch.net/test/read.cgi/tech/1580131715/43
44: デフォルトの名無しさん [sage] 2021/10/10(日) 20:08:58.53 ID:6QW0WSDe >>42-43 ありがとうございました。 『アルゴリズム実技検定』では、上司部下の関係を親子の関係と考えたツリーを考えて、再帰を使った深さ優先探索のような処理をしています。 そして、そのプログラムを動的計画法を使ったプログラムと書いています。 http://mevius.5ch.net/test/read.cgi/tech/1580131715/44
45: デフォルトの名無しさん [sage] 2021/10/10(日) 22:19:32.54 ID:shNjC7Q8 英語版Wikipedia（その出展として挙げられている『アルゴリズムイントロダクション』）の説明に従うと、この例は部分問題重複性が無いので、動的計画法ではなく分割統治アルゴリズムと呼ぶべきでしょうね https://en.m.wikipedia.org/wiki/Dynamic_programming 競技プログラミング界隈だとこのような例も動的計画法と呼ぶ人はいますが、書籍でそれが一般的であるかのように書かれているのはあまりよくないように思えますね http://mevius.5ch.net/test/read.cgi/tech/1580131715/45
46: デフォルトの名無しさん [sage] 2021/10/10(日) 22:22:05.61 ID:6QW0WSDe >>45 ありがとうございました。 http://mevius.5ch.net/test/read.cgi/tech/1580131715/46
47: デフォルトの名無しさん [] 2021/10/11(月) 16:16:04.73 ID:bJ9NE0N3 閉路を含まない有向グラフのすべての有向パスのうち長さが最長の有向パスの長さを計算せよという問題について質問があります。 AtCoderの出題ページは以下になります。 https://atcoder.jp/contests/dp/tasks/dp_g 『アルゴリズム実技検定』という本の解説を読みますと「トポロジカルソート」という考え方を使うと書いてあります。 私は「トポロジカルソート」について何も知りませんが、制限時間内に答えを出すPythonプログラムを書けました。 本当に「トポロジカルソート」というのが必要でしょうか？ なお、上記ページにリンクが貼ってある解説のページ（hamayanhamayanというユーザーの解説のページ）にも「トポロジカルソートを知っていれば一瞬だが、知らないと解けない。」 と書いています。 『アルゴリズム実技検定』という本の模範解答を見ても、「トポロジカルソート」によって頂点に番号を割り振ったりはしていません。 つまり「トポロジカルソート」など不要ではないかと思うんです。 以下がジャッジにパスした私のPythonのコードです。 https://ideone.com/iQIvcc http://mevius.5ch.net/test/read.cgi/tech/1580131715/47
48: デフォルトの名無しさん [] 2021/10/11(月) 16:25:53.01 ID:bJ9NE0N3 >>47 あともう一点。 この問題の出題カテゴリは動的計画法に属します。 『アルゴリズム実技検定』の模範解答も私のコードも、深さ優先探索 + 「メモ化再帰」で答えを計算しています。 >>45 確かにこの問題の場合部分問題重複性はあると思いますが、こういう単なる、いわゆる「メモ化再帰」も動的計画法と言っていいのでしょうか？ http://mevius.5ch.net/test/read.cgi/tech/1580131715/48
49: デフォルトの名無しさん [sage] 2021/10/12(火) 00:41:32.76 ID:mo6bbxTQ まず、動的計画法の実現方法にはトップダウン方式とボトムアップ方式があり、メモ化再帰はトップダウン方式の実現方法に当たります こちらは日本語版のWikipediaにも記載があります https://ja.m.wikipedia.org/wiki/%E5%8B%95%E7%9A%84%E8%A8%88%E7%94%BB%E6%B3%95 トポロジカルソートの知識が必須になるのは、ボトムアップ方式で実現する場合です メモ化再帰する場合にはトポロジカルソートを意識する必要はありません ここで行われているメモ化再帰の実装は、深さ優先検索を用いたトポロジカルソートの実装と類似しており、結果的にトポロジカルソートの逆順で計算結果が確定されていくことになります http://mevius.5ch.net/test/read.cgi/tech/1580131715/49
50: デフォルトの名無しさん [sage] 2021/10/12(火) 07:51:06.12 ID:9oya6EGe >>49 ありがとうございました。 『アルゴリズム実技検定』でのコードは、トップダウン方式ですので、「トポロジカルソート」などという言葉を出さなくても良かったわけですね。 http://mevius.5ch.net/test/read.cgi/tech/1580131715/50
51: デフォルトの名無しさん [] 2021/10/15(金) 14:52:49.77 ID:n9WPu0Ca https://atcoder.jp/contests/past201912-open/tasks/past201912_i ↑の問題を↓のように解きました。 https://ideone.com/osdCtN コメントアウトしている行をアンコメントするとジェッジにパスしなくなります。 理由が分かりません。 理由が分かる方、教えて下さい。 http://mevius.5ch.net/test/read.cgi/tech/1580131715/51
52: デフォルトの名無しさん [] 2021/10/15(金) 15:11:44.64 ID:n9WPu0Ca あ、わかりました。 http://mevius.5ch.net/test/read.cgi/tech/1580131715/52
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
ﾒﾓ帳
(0/65535文字)
上
下
前
次
1-
新
書
関
写
板
覧
索
設
栞
歴
あと 49 ﾚｽあります
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.005s