Codeforces Round #339 (Div. 1) A. Peter and Snow Blower - pekempey's blog
※問題をエスパーしたので問題を勘違いしています。 問題文 codeforces.com 問題概要 点P と 多角形 S が与えられる。 点 P を中心とした円を 2 つ描き、多角形 S がその円の間に挟まれるようにする。 この 2 つの円に囲まれる領域の面積の最小値を求めよ。 解法 点と多角形の距離の最小値・最大値を求めれば面積の最小値が求められる。 点と多角形の距離の最小値は、点と多角形のそれぞれの辺の距離の最小値になる。 そのため、点と線分の距離を求めたい。 点と線分の距離は、点が緑色の領域内部にあるかどうかで求め方が変わる。 以降、直線の単位方向ベクトルを $d=(q-p)/|q-p|$ とする。 緑色の領域の内部にある場合 図でいうと r1 がこのケースになる。これは点と直線の距離を求めればいい。 点と直線の距離は外積を用いて、 $$ | d \times (r-p) | $$ で
競技プログラミング頻出アルゴリズム攻略
【DL輪読会】Hyena Hierarchy: Towards Larger Convolutional Language Models
CodeIQについてのお知らせ
2018年4月25日をもちまして、 『CodeIQ』のプログラミング腕試しサービス、年収確約スカウトサービスは、 ITエンジニアのための年収確約スカウトサービス『moffers by CodeIQ』https://moffers.jp/ へ一本化いたしました。 これまで多くのITエンジニアの方に『CodeIQ』をご利用いただきまして、 改めて心より深く御礼申し上げます。 また、エンジニアのためのWebマガジン「CodeIQ MAGAZINE」は、 リクナビNEXTジャーナル( https://next.rikunabi.com/journal/ )に一部の記事の移行を予定しております。 今後は『moffers by CodeIQ』にて、 ITエンジニアの皆様のより良い転職をサポートするために、より一層努めてまいりますので、 引き続きご愛顧のほど何卒よろしくお願い申し上げます。 また、Cod
visualising data structures and algorithms through animation - VisuAlgo
VisuAlgo.net/en visualising data structures and algorithms through animation VisuAlgo is a trilingual site. Try visiting the other versions of VisuAlgo other than the default English version, e.g., Chinese or Indonesian. Users can see the translation statistics for these three pages. We aim to make all three has near 100% translation rate. Unfortunately the translation progress with other language
Reservoir sampling - Wikipedia
Reservoir sampling is a family of randomized algorithms for choosing a simple random sample, without replacement, of k items from a population of unknown size n in a single pass over the items. The size of the population n is not known to the algorithm and is typically too large for all n items to fit into main memory. The population is revealed to the algorithm over time, and the algorithm cannot
There’s Math.random(), and then there’s Math.random() · V8
Show navigation Math.random() returns a Number value with positive sign, greater than or equal to 0 but less than 1, chosen randomly or pseudo-randomly with approximately uniform distribution over that range, using an implementation-dependent algorithm or strategy. This function takes no arguments. — ES 2015, section 20.2.2.27 Math.random() is the most well-known and frequently-used source of rand
どせい on Twitter: "2^32-1 乗で単位行列になるか実際に計算してみた https://t.co/NmYvnzgHNY https://t.co/m3yY8zvCqm"
2^32-1 乗で単位行列になるか実際に計算してみた https://t.co/NmYvnzgHNY https://t.co/m3yY8zvCqm
Google Chromeが採用した、擬似乱数生成アルゴリズム「xorshift」の数理
2015年12月17日、Google Chrome の JavaScript エンジン（処理系）である V8 の公式ブログにて、 JavaScript の標準的な乱数生成APIである Math.random() の背後で使われているアルゴリズムの変更がアナウンスされました。 Math.random() 関数は JavaScript を利用する際には比較的よく使われる関数ですので、親しみのある方も多いのではないかと思います。 新たなバグの発見や、従来より優秀なアルゴリズムの発見によってアルゴリズムが変更されること自体はそれほど珍しくはないものの、 技術的には枯れていると思われる Math.random() のような基本的な処理の背後のアルゴリズムが変更されたことに驚きを感じる方も少なくないかと思いますが、 それ以上に注目すべきはその変更後のアルゴリズムです。 実際に採用されたアルゴリズムの原
最小完全ハッシュ函数 - epii's physics notes
最小完全ハッシュ函数 ハッシュ函数のうち、可逆で、かつ、生成するハッシュ値の値域が最小である函数のことを、最小完全ハッシュ函数と言います。 その作り方を解説していきたいと思います。
連載やねうら王miniで遊ぼう！7日目 | やねうら王 公式サイト
今回は、局面のhash値の計算について説明します。 局面に対応するhash値の取り出し 局面に対して、StateInfo::key()からhash値が得られる。 このhash値は、局面に対応する固有の値である。 しかし通例、hash値は64bitしかないので、異なる局面であっても、たまたま同じhash値になることがある。これをhash衝突と言う。 やねうら王miniにはこのhash値を128bitにしたり256bitにしたり出来る無駄機能があるが、その話は次回にしよう。 さて、このkeyを取り出してみよう。その局面固有の内容を格納しておくのはStateInfoであった。Positionクラスのstate()を呼び出すとStateInfoの参照が得られる。StateInfoのkey()を呼び出すとこのhash値が得られる。 実際にやってみよう。 void user_test(Position
ハッシュは頻繁に参照する値を最後に入れると高速 - まめめも
明日から RubyKaigi なので、ちょっとした小ネタを一つ。 例えば、0 から 9999 までをハッシュに順に入れます。 h = {} 10000.times do |n| h[n] = true end このとき、h[9998] や h[9999] は、h[0] や h[1] より高速です。 どのくらい高速かというと、 1_000_000_000.times { h } # 40.8 sec (ループ自体の速度) 1_000_000_000.times { h[9999] } # 57.2 sec 1_000_000_000.times { h[0] } # 89.1 sech[0] は 89.1 - 40.8 = 48.3 nsec 、h[9999] は 57.2 - 40.8 = 16.4 nsec ということになります。なんと 3 倍も速い。*1 なぜこんなことが起きるのか ハ
Google、量子コンピュータでPCの1億倍高速な解析に成功と発表
今回の実験では、「量子ビット」を1000個以上搭載するD-Wave 2Xでの「量子アニーリング」とシングルコアのコンピュータの「シミュレーテッドアニーリング」とで、約1000個の変数の「組み合わせ最適化問題」の解決速度を比較した。 Googleは2013年、NASAと共同でエイムズ研究所に量子コンピュータラボ「Quantum Artificial Intelligence Lab」を立ち上げ、実験を重ねてきた。Googleが取り組んでいるディープラーニングなどの機械学習ではビッグデータを高速に処理するシステムが必要であり、量子コンピュータが実用化できれば研究が飛躍的に前進するだろう。 Googleは、この実験結果は非常に興味深いし有望なものだとしながらも、実用化するまでにはまだ多くの課題を乗り越える必要があるとしている。 関連記事 Google、NASAと共同で量子コンピュータラボを立ち上
最適化アルゴリズムを評価するベンチマーク関数まとめ - Qiita
更新履歴 最適解と探索範囲を追記しました。 2016/11/29 @fimbulさん 編集リクエストありがとうございました。修正しました。 2017/7/10 @tomochiiiさん 編集リクエストありがとうございました。Easom functionを引用元の数式に修正、Schaffer function N. 2とN. 4の数式の修正 2018/5/9 @applicative62045 さん 編集リクエストありがとうございました(編集リクエストの確認遅くなりました。2019/12/31記載) Griek functionを修正 2019/12/31 @okamoto6496 さん 指摘ありがとうございました。Five-well potential functionの数式を修正。 2020/01/20 @higedura さん 指摘ありがとうございます。Bukin function N
文字列検索のいろいろ
Bruteforce(力まかせ) ● 完全に名前負けしている。 ● 誰でも思いつく以下のような手法である。 ① 文中での比較開始位置を決める。 ② そこからパターンと一致しているか比較する。 不一致が確定した時点で打ち切り。 ③ ①，②を文中の全ての位置に行う。 例) パターン : kyubuns 文: x k y u r i k y u b u n s k y u b u n s ↑ Bruteforce(力まかせ) ● 完全に名前負けしている。 ● 誰でも思いつく以下のような手法である。 ① 文中での比較開始位置を決める。 ② そこからパターンと一致しているか比較する。 不一致が確定した時点で打ち切り。 ③ ①，②を文中の全ての位置に行う。 例) パターン : kyubuns 文: x k y u r i k y u b u n s k y u b u n s ↑ 最初の文字で不一致し
実験計画法と組合せ最適化 - Qiita
これは、アルゴリズム Advent Calendar 2015の3日目の記事です。 はじめに 実験計画法の簡単な紹介と、その発展として組合せ最適化によるアプローチを紹介します。 背景 センサー情報からある解析をしたいとします。 センサーは、1万円のものと3万円のものがあり、置かないこともあるので、3種類の選択があります。 センサーの設置場所は、20カ所の候補があります。 全センサーの総購入費用は5万円以下に抑えないといけません。 どこにいくらのセンサーを置いたら、効率よく検証できるのかを知りたいものとします。 ケースの例としては、「A地点とB地点に1万円のセンサー、C地点に3万円のセンサーを配置」となります。 用語 下記の用語を使います。 要因：水準を決めたい検討対象。今回は、センサーの配置候補。 水準：要因の取り得る値。今回は、センサーの費用で、0万円、1万円、3万円の3種類。 交互作用
A* (1968) - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 東京大学大学院 総合文化研究科、福永研究室の浅井です。 続いて、探索の高速化に必須の手法、A* (エースター) を紹介します。 Aは「ヒューリスティック探索」とか「発見的探索」と呼ばれます。この名前が悪くて、おかげで、酷い誤解を受けています。例えばあるスライドでは、Aは「近そうなところから探索」と書かれています。なんか適当に探索するかのような印象ですね。A*は、ダイクストラ法を拡張し、 理論的裏付けを持った下界を用いてグラフを探索するための手法 です。 Dijkstra法 の何がタコか Dijkstra法は、最適解を見つけることができる
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
bitset.js
アルゴリズム - Qiita Advent Calendar 2015 - Qiita
15种姿势让女人最深-男女洞房最刺激的姿势-性知识大全姿势
PFIセミナー2015/12/3: More Modern GPU
