[B! アルゴリズム] yunottinoatamaのブックマーク

ポケモンの最強タイプを考える【グラフ理論】 - Qiita

導入先日、ポケモンの最新作『Pokémon LEGENDS アルセウス』が発売されました。ポケモン愛好家の中で密かに話題を集めたのが、新たに登場したポケモン「ゾロア（ヒスイのすがた）」と「ゾロアーク（ヒスイの姿）」のタイプです。なんと驚くべきことに、両者のタイプは未だ登場したことのなかった「ノーマル・ゴースト」だったのです。ポケモンを知る人には説明不要ですが、これはノーマルタイプの唯一の弱点であるかくとう技をゴーストタイプで無効化しながら、ゴーストタイプの弱点であるゴースト技をノーマルタイプで無効化するという、非常にバランスのとれた、まさに夢のような複合タイプです。一部では、この「ノーマル・ゴースト」こそ最強の組み合わせなのではないかと噂されました。しかし、果たして本当にそうなのでしょうか？ポケモンのタイプは全部で18種類あり、一匹のポケモンは二つまでタイプを持つことができます。考

yunottinoatama 2022/02/08

最終評価では水地面に強い草は最弱では無くなっている。逆にノーマルが最弱に (ゴリランダーが140位、メタモンが171位)。飛行のダイジェットの強さを考慮できればサンダーはもっと高順位になりそう。

リンク

[#Unity] ComputeShaderで近傍探索の高速化 - Qiita

この記事は、Unity Advent Calender 2017 19日目の記事です。はじめに本記事では、かなり前に実装した ComputeShaderで格子探索を行うアルゴリズムを解説します。追記 : 卒論執筆で時間が取れずリポジトリの雑な説明になりそうです...すいません... 近傍探索とは、前もってデータ構造を最適化しておき、値の利用時に全数探索をしないことで計算速度を飛躍的に向上させるアルゴリズムのことを指します。主に使用される場面として、 Boids Simulation N-Body Simulation SPH Simulation があります。いずれも物理的な2点間の距離を算出する必要があるアルゴリズムですが、全数探索を行っていると、すべての要素毎にすべての要素との距離を計算する必要があります。 (俗に$O(n^2)$の実行時間を要すると言います) 当然この方

yunottinoatama 2019/05/30

リンク

その８ 4分木空間分割を最適化する！

ホーム＜ゲームつくろー！＜衝突判定編 2D衝突編その８ 4分木空間分割を最適化する！（理屈編）ゲーム空間に置いたオブジェクトを総当りで衝突判定する事ははっきりと非効率だと言えます。ちょっと計算してみましょう。60FPSのゲームの1フリップ約16.6ミリ秒の内衝突判定に10%の時間余裕（1.66ミリ秒）を与えられたとします。もし1000回の衝突判定に1ミリ秒かかるなら（1000回/msec）、判定回数は1660回以下に抑えないと間に合いません。総当りだとこれは58オブジェクトくらいで限界です。判定時間が200回/msecならオブジェクトはたった18個で限界。これはどう考えても節約が無いとゲームになりません。オブジェクトの全ての位置が決まった時、自分とぶつかる可能性があるのは自分の周りのオブジェクトだけです。遠い所にある物は判定する必要すらありません。そこで「空間をある程度制限してその中

yunottinoatama 2017/09/06

リンク

MIT、マルコフ連鎖モンテカルロ法を高速化するアルゴリズムを発表

印刷するメールで送るテキスト HTML 電子書籍 PDF ダウンロードテキスト電子書籍 PDF クリップした記事をMyページから読むことができますマサチューセッツ工科大学（MIT）の研究者らは、マルコフ連鎖モンテカルロ法（MCMC）を現在よりも最大で200倍高速化できるアルゴリズムを開発したと発表した。 MITのこのアルゴリズムは、ほとんどすべての計算モデルに適用できる。このアルゴリズムの目的は、問題中に存在する未知のパラメータの値を局所近似から推定することで、対象となる解を絞り込むというものだ。発表のなかで、MITはこのアルゴリズムについて以下のように述べている。このアルゴリズムは、モデルを複数回実行するなかで、いくつかの適切なデータ点を組み合わせていくことにより解、すなわち未知のパラメータそれぞれの確率分布をインクリメンタルなかたちで絞り込んでいくものだ。そういった点で、

yunottinoatama 2015/11/19

アルゴリズム

リンク

本当に実用的なたったひとつのソートアルゴリズム - CARTA TECH BLOG

コンテンツメディア事業本部の新卒エンジニア坂本がお送りいたします。突然ですが、皆さんの好きなソートアルゴリズムはなんですか？私は基数ソートのスマートでストイックな雰囲気に惹かれます。とはいえ、普段の開発では「どのソートアルゴリズムを使うか」を意識することは少ないのではないでしょうか。むしろ現実世界で「トランプが全部揃ってるか」を手作業で確認するときとかのほうが、実はソートアルゴリズムが必要なのかもしれません。ということで（？）、そのような現実的な場面で、本当に実用的なソートアルゴリズムを決める戦いが始まりました。選手紹介今回試したソートアルゴリズムは、独断と偏見で選んだ以下の5種類。 1 挿入ソートシンプル・イズ・ベスト！正直言ってベンチマークの噛ませ犬！ 2 クイックソート「クイック」の名前はダテじゃない！王者の貫禄を見せてやれ！ 3 マージソート安定感のある隠れた実

yunottinoatama 2015/08/20

リンク

多項式の計算で乗算を増やさない方法 - 更新しない備忘録改二

数値計算なんかをプログラムで書いてると、多項式の値を求めたいことがよくある。たとえば次の多項式これを計算するコードは、たとえば次のようになる。 // C/C++ f = x*x + 2*x + 3; もう少し一般的に、次の多項式について、と係数の配列からを計算する関数を考える。 double poly1(double x, double a[], int n) { double f = 0.0; for (int i = 0; i <= n; i++) { double g = a[i]; for (int j = 0; j < i; j++) g *= x; f += g; } return f; } これでもいいのだが、次数の高い多項式を計算しようとすると、この関数の計算量は非常に大きくなる。理由は簡単で、各を直接乗算で求めているからだ。たとえばこの関数で100次の多項式を計

yunottinoatama 2015/04/13

アルゴリズム

リンク

せっき～のゲーム屋さんドルアーガの塔　乱数の工夫の正体

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。ＣＥＤＥＣの講演「ゲーム世界を動かすサイコロの正体～往年のナムコタイトルから学ぶ乱数の進化と応用」より、乱数を使ったドルアーガの塔の迷路生成のアリゴリズムについて紹介です。講演内容は、こちらです http://sekigames.gg-blog.com/Entry/288/ 講演者の方も、「ナムコの乱数を取り上げるなら、ドルアーガの塔をせざるえない」という程、外せない内容との事です「このテーマだけで講演時間を全て使っても説明しきれない」（講演では、時間の関係で触りのみでしたのである程度、せっき～の解釈で補完しています） -------------------------------------------------------------------

yunottinoatama 2014/09/26

リンク

もし先輩女子エンジニアが『アルゴリズム』を図解で教えてくれるとしたら - paiza times

2014年7月30日より8月27日まで開催した、paizaオンラインハッカソン（略してPOH![ポー！]）Lite「天才火消しエンジニア霧島　もしPMおじさんが『丸投げ』を覚えたら」ですが、どのような解法が有ったのでしょうか。今回もPOH恒例の「解説図解」を、天才火消しエンジニア霧島が解説するとしたら、という体で書いてみたいと思います。(特に文体とか変えませんがｗ最後に霧島壁紙DLが有るので是非最後までお読みください。) ■どのような高速化ステップがあるのか？今回の問題ですが、実行時間に大きく影響する計算量別にみたアプローチでは、すべての組み合わせを出して、人数を満たして一番安い組み合わせを見つける全探索[計算量はO(2^N)]と、動的計画法[計算量はq = max(q_i) としてO(Nq) ]（やり方によってはO(NM)）による2種類があります。また全探索を改良し、効率的な枝刈