データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4 (105ﾚｽ)
上下前次1-新
27: 2021/02/27(土)17:10 ID:cGuo4IiQ(2/2) AAS
よく読んでなかったすまんかった
28: 2021/03/08(月)16:54 ID:H4OoIpXQ(1) AAS
焼きなましに例えるんだからEnergyのEだろうね
線形計画法が流行ってた時代はとりあえず目標関数は最大化するものとしてた風潮があった(LPでは双対問題と厳密に等価)
シュミレーション分野、最近の機械学習の流行りでとりあえずコスト関数を最小化する雰囲気
LPじゃないんで同じ点で極値を与える関数にも良し悪しがある点には気を付けねば
実数関数なら符号の反転と、並進に依らないアルゴリズムであれば並進を加えたもののみ等価
29(1): 2021/03/17(水)19:38 ID:DuV9YnX6(1) AAS
初歩的な質問かもしれず、恐縮ですがお願いいたします。
i Phoneを使って、端末が始点から終点まで移動した角度をx,y,z（オイラー角）で取得したいと考えています。
最初は、始点と終点の端末の位置をオイラー角で取得し、その差分を出してみたのですが、ジンバルロックによりpitchの値を正確に取得できませんでした。
ジンバルロックを回避するためクォータニオンを使うといいようなのですが、クォータニオンを使って目的の値を算出する方法が分からない状態です。
もし分かる方がおられましたら、ご助言いただると幸いです。
よろしくお願いします。
30: 2021/05/19(水)16:18 ID:7NWiu4qI(1) AAS
Minimum Mean Cycleでこのスライドを見ているのですが
3ページでmaxをとっているのに正しい答えがでる理由ってなんでですか？
外部ﾘﾝｸ[pdf]:www.columbia.edu
(d^n(v) - d^k(v)) / (n - k)はｖからスタートしたときのMean Cycleですよね
d^k(v)が無限の場合を避けるためにmaxをとっていると思うのですが，なぜ正しい答えになるのでしょうか
31: 2021/05/22(土)02:18 ID:/00w7bM8(1) AAS
>>29
取り敢えず理解はほっといて動けばいいのなら、ウィキペにでも公式載ってたと思うよ
32: 2021/10/03(日)17:59 ID:nkudyinT(1) AAS
幅優先探索の計算量がO(N)ではなくO(N + E)なのはなぜ？
Nは頂点の数、Eは辺の数です。
33: 2021/10/03(日)20:36 ID:KyHKDHW1(1) AAS
辺の数だけ処理が増えるから
頂点の数を同じにして辺の数が異なる2つのグラフを比較してみればわかる
34: 2021/10/03(日)22:55 ID:45cLxSS6(1) AAS
モートン順序によって当たり判定を一瞬で計算するというのがありました
あれ特定の境目の上にオブジェクトがあるとすべてのオブジェクトとの衝突判定が発生するんですが
世の中のゲームってそんなふうにやってるんですか
35: 2021/10/04(月)18:40 ID:N2yAdGNd(1) AAS
計算量がO(V + E)であるの定義は何ですか？
36: 2021/10/04(月)22:35 ID:qkBPKVDO(1) AAS
それは計算量の定義をきいているのか？
37(1): 2021/10/05(火)00:11 ID:wQtjKuKa(1/2) AAS
そのアルゴリズムの計算時間を 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億倍..
詳しくはアルゴリズムの教科書か
外部ﾘﾝｸ:ja.wikipedia.orgランダウの記号
38(1): 2021/10/05(火)02:13 ID:3IOuHtiP(1/2) AAS
>>37
ありがとうございます。
ですが、O(V + E)の中に書かれている式であるV + Eは2変数の関数です。それでも1変数の場合と同じ定義でいいんですか？
39(1): 2021/10/05(火)03:31 ID:wQtjKuKa(2/2) AAS
>>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) となる
40: 2021/10/05(火)08:50 ID:3IOuHtiP(2/2) AAS
>>39
なるほど。ありがとうございました。
41(1): 2021/10/10(日)18:05 ID:6QW0WSDe(1/3) AAS
以下のプログラミングコンテストの問題なのですが、『アルゴリズム実技検定』という本の解説では、これは動的計画法の問題であると書いてあります。
本当にこういうのも動的計画法と言いますか？
外部ﾘﾝｸ:atcoder.jp
42(1): 2021/10/10(日)19:42 ID:CKYp8hS8(1/2) AAS
>>41
ツリーを作って再帰にもできそうだけど、番号の1番大きい社員から少ない社員に向かって1つずつ処理していけば動的計画法になるね
最初に各社員に部下の給料のリスト（最初は空）を持たせて、社員番号Nから2番に向かって部下の給料のリストに値があればそこから自分の給与を計算して上司のリストに加えることを繰り返す
社員N番を含めて部下がいない、自分の番が回ってきても部下の給料リストが空なら1を上司のリストに加えればいい
43(1): 2021/10/10(日)20:02 ID:CKYp8hS8(2/2) AAS
部下の給与リストじゃなくて最大値と最小値だけ覚えとけばもっと賢いか
44: 2021/10/10(日)20:08 ID:6QW0WSDe(2/3) AAS
>>42-43
ありがとうございました。
『アルゴリズム実技検定』では、上司部下の関係を親子の関係と考えたツリーを考えて、再帰を使った深さ優先探索のような処理をしています。
そして、そのプログラムを動的計画法を使ったプログラムと書いています。
45(2): 2021/10/10(日)22:19 ID:shNjC7Q8(1) AAS
英語版Wikipedia（その出展として挙げられている『アルゴリズムイントロダクション』）の説明に従うと、この例は部分問題重複性が無いので、動的計画法ではなく分割統治アルゴリズムと呼ぶべきでしょうね
外部ﾘﾝｸ:en.m.wikipedia.org
競技プログラミング界隈だとこのような例も動的計画法と呼ぶ人はいますが、書籍でそれが一般的であるかのように書かれているのはあまりよくないように思えますね
46: 2021/10/10(日)22:22 ID:6QW0WSDe(3/3) AAS
>>45
ありがとうございました。
47(1): 2021/10/11(月)16:16 ID:bJ9NE0N3(1/2) AAS
閉路を含まない有向グラフのすべての有向パスのうち長さが最長の有向パスの長さを計算せよという問題について質問があります。
AtCoderの出題ページは以下になります。
外部ﾘﾝｸ:atcoder.jp
『アルゴリズム実技検定』という本の解説を読みますと「トポロジカルソート」という考え方を使うと書いてあります。
私は「トポロジカルソート」について何も知りませんが、制限時間内に答えを出すPythonプログラムを書けました。
本当に「トポロジカルソート」というのが必要でしょうか？
なお、上記ページにリンクが貼ってある解説のページ（hamayanhamayanというユーザーの解説のページ）にも「トポロジカルソートを知っていれば一瞬だが、知らないと解けない。」
と書いています。
『アルゴリズム実技検定』という本の模範解答を見ても、「トポロジカルソート」によって頂点に番号を割り振ったりはしていません。
つまり「トポロジカルソート」など不要ではないかと思うんです。
以下がジャッジにパスした私のPythonのコードです。
外部ﾘﾝｸ:ideone.com
48: 2021/10/11(月)16:25 ID:bJ9NE0N3(2/2) AAS
>>47
あともう一点。
この問題の出題カテゴリは動的計画法に属します。
『アルゴリズム実技検定』の模範解答も私のコードも、深さ優先探索 + 「メモ化再帰」で答えを計算しています。
>>45
確かにこの問題の場合部分問題重複性はあると思いますが、こういう単なる、いわゆる「メモ化再帰」も動的計画法と言っていいのでしょうか？
49(1): 2021/10/12(火)00:41 ID:mo6bbxTQ(1) AAS
まず、動的計画法の実現方法にはトップダウン方式とボトムアップ方式があり、メモ化再帰はトップダウン方式の実現方法に当たります
こちらは日本語版のWikipediaにも記載があります
外部ﾘﾝｸ:ja.m.wikipedia.org
トポロジカルソートの知識が必須になるのは、ボトムアップ方式で実現する場合です
メモ化再帰する場合にはトポロジカルソートを意識する必要はありません
ここで行われているメモ化再帰の実装は、深さ優先検索を用いたトポロジカルソートの実装と類似しており、結果的にトポロジカルソートの逆順で計算結果が確定されていくことになります
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
まるちんこ
上下前次1-新書関写板覧索設栞歴
あと 49 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ
ぬこの手 ぬこTOP 0.006s