Xorshift を用いた Zobrist hashing を衝突させる方法 - noshi91のメモ
概要 Xorshift によって生成された乱数列について、いくつかの場所の xor を取ると seed に依存せずに になる。 Xorshift Xorshift - Wikipedia 説明は Wikipedia に丸投げする。 本記事では簡略化のため、実装例の一番上にある周期 の実装について議論する。 Zobrist hashing 個の要素があるとして、要素 に乱数 を割り当てる。 このとき、集合 の hash を で定める。 ただし は bitwise xor とする。 この hashing の方法を Zobrist hashing と呼ぶ。 hash の衝突 異なる集合 について となることを衝突と呼ぶ。 Zobrist hashing の場合 であるから、 かつ となるような が分かれば衝突を引き起こすことができる。 結論から言うと、 を Xorshift が 番目に出力した値
atoi関数のかしこい実装 - yohhoyの日記
C標準ライブラリ Muslのatoi関数実装 では、符号付き整数オーバーフロー回避のため負数範囲で10進数値を減算してゆき最後に符号反転を行っている。 int atoi(const char *s) { int n=0, neg=0; while (isspace(*s)) s++; switch (*s) { case '-': neg=1; case '+': s++; } /* Compute n as a negative number to avoid overflow on INT_MIN */ while (isdigit(*s)) n = 10 * n - (*s++ - '0'); return neg ? n : -n; } C言語の符号付き整数型(int)では “2の補数” 表現が用いられるため*1、最大値INT_MAXより最小値INT_MINの絶対値が 1 だけ大き
アルゴリズムの世界地図 - Qiita
こんにちは、square1001 です。 現在は東京大学の学部 1 年生をしています。私は中学 1 年の頃からプログラミングをやっていて、特にアルゴリズムが大好きです。AtCoder をはじめとする 競技プログラミング にも取り組んでいて、中高生のときは 情報オリンピック にも参加していました。 本記事では、アルゴリズムや競技プログラミングに興味がある方、あるいはプログラミングをやっているけどアルゴリズムをよく知らない方に アルゴリズムはどんなもので アルゴリズムを使うとどんな問題が解けて アルゴリズムが地球のように広く、多様で、奥深く、そして楽しいこと を知ってもらおうと思っています。 アルゴリズムの世界へようこそ 時代は 2020 年代に突入し、急速に IT 化 や DX が進んでいく中で、問題を効率的に解くアルゴリズム技術の重要性が、ますます高まっています。そして、アルゴリズムは、世
1次元ランダムウォーク - ei1333の日記
初心者向け 1 次元ランダムウォーク 数直線があって、原点 に点 がある。 時刻が 進むごとに、点 の位置が確率 で 、確率 で 動く。 この確率モデルを (対称な) 次元ランダムウォークと呼ぶ。 パスの個数 横軸を時間軸、縦軸を点 の位置を表すこととすると、以下のような折れ線グラフで表すことができる。 を、原点から点 までのパスの個数（言い換えると、時刻 に位置 に至る経路数）とする。 と から、ランダムウォークで した回数 と した回数 をそれぞれ計算できる。 より、 となる。("45度回転"に相当する) したがって と の偶奇が一致しているとき と二項係数を用いて表せる。 auto L = [&](int t, int x) -> modint { if(t % 2 != abs(x) % 2) { return 0; } else { return beet.C(t, (t + x
Git を永続データ構造として見る - koyumeishiのブログ
競技プログラミングは役に立つ、 というかアルゴリズムとデータ構造は身の回りで役に立ってるよ案件なんですが、 バージョン管理システム Git のコア部分の仕組みは永続データ構造です。 ブラックボックスとして使うより簡単な仕組みを知ってる方が 親しみやすいと思うので雑に解説します。 "git データ構造" とかでググると同様の話結構出てくる N 番煎じです (というか公式ドキュメントに書いてあるまんまのことを競プロer的に見るとこうなっているよという話。 Git の使い方を解説する記事ではありませんし、まして GitHub は何の関係ありません)。 ソースコードや公式ドキュメントを読み込んだわけじゃないのでテキトーなことが書かれているかもしれません。 公式ドキュメントを読んでください。 ざっくり "commit" は登録したファイルを含むディレクトリツリーのスナップショットを保存している "c
50分で学ぶアルゴリズム / Algorithms in 50 minutes
本スライドでは、有名なアルゴリズムを概観し、アルゴリズムに興味を持っていただくことを目標にします。 第 1 部：アルゴリズムとは 第 2 部：学年を当ててみよう 第 3 部：代表的なアルゴリズム問題 第 4 部：コンピュータとアルゴリズム
d.y.d.
22:43 21/11/09 ヒープソートが好きである ranha さんが、 Approaching Heapsort via Lazy Mergesort という記事を公開していらして、 遅延評価の言語で書くマージソートの計算過程で何が起きているかを見ていくと、 だんだんヒープソートが見えてきた…！という大変面白い記事なのですが、 その話の枕に「稲葉さんというヒープソート大好き人間がいるがいったいどこが良いのか」 という形で私が登場していたので、 思わず何故私がヒープソートが好きであるかをしたためた長文をTwitterのDMで ranhaさんに送りつけてしまいましたという経緯があります。 元ネタの @pi8027 さんの発表 が公になったのに合わせてranhaさんの記事も公開されたみたいなので、 自分の脳内出力もついでにここに書き留めておこうかと思いました。 お二方のように技術的にしっか
ヒューリスティックコンテスト(マラソン)、ゲームAIコンテストで使う武器まとめ｜にゃにゃん(山名琢翔)
ものづくりとプログラミングとルービックキューブが大好きなにゃにゃんです。今回は競技プログラミングに関する内容です。 この記事の執筆時点ではもうすぐAHC002というヒューリスティックコンテストが開かれます。 これに向けて過去問を解いて準備をしていて、ヒューリスティックコンテストやゲームAIコンテスト(基本的にまとめて「ヒューリスティックコンテスト」と言うことにします)における様々な武器やTIPSがわかってきました。それを自分のメモも兼ねてまとめます。なお、深さ優先探索や幅優先探索など、アルゴリズムコンテストでもよく出てくるアルゴリズムについては省きました。ただでさえ記事の文字数が結構多くなってしまったので… この記事は私が今後精進していく中で新たな発見があったら随時追記していこうと思います。 ヒューリスティックコンテストとは ヒューリスティックコンテストは、ある問題が与えられて、それに対す
リトルの法則-待ち時間の推定－この行列は、あと何分、待たなくてはならないのか?
人気のあるものには、すぐに行列ができる。遊園地のアトラクション、有名なレストラン、駅の窓口、病院の受付、…と、至るところで行列ができる。ワクワクするような楽しいことを待つために、行列に並ぶのは、大して苦痛ではない。しかし、嫌なことを待つときや、急いでいるとき、待つ環境が厳しいときなどには、大変な苦しさを味わうこともある。 行列に並んでいると、誰もが考えるのは、「あと何分、待たなくてはならないのか?」ということだろう。待ち時間を知りたいという思いは、行列を待つ人に、つきものと言える。特に、待つことが苦痛に感じられる場合には、イライラ感も手伝って、その思いが強くなる。 行列の長さが比較的短ければ、待ち時間の推定はしやすい。例えば、ある駅の窓口で、自分の前に10人が並んでいて、1分間で1人ずつ窓口で用を済ませているとしよう。この場合は、待ち時間は10分と推定できる。ただし、窓口で1人にかかる時間
【競プロer向け】FFT を習得しよう！
i+j=k の条件を x の指数にすることで、xi と xj を掛けたときに xi+j と足し算ができて、同類項が足されて畳み込みになるというわけですね。 多点評価と多項式補間 グラフ上で、1 点を通る 0 次多項式、2 点を通る 1 次多項式、3 点を通る 2 次多項式、… は一意に定まりますね。 fC(x) は ∣A∣+∣B∣−2 次多項式なので、∣A∣+∣B∣−1 個の点でのfC(x) の値が分かれば fC(x) が分かるということになります。 N=∣A∣+∣B∣−1 と置きます。 N 個の点 ζN0,ζN1,…,ζNN−1 を選び、fC(ζN0),fC(ζN1),…,fC(ζNN−1) を求めて C を復元することを考えます。これが畳み込みを高速にする秘訣です。 fA(x)×fB(x)=fC(x) であることを思い出すと、fA(ζN0),fA(ζ
遅延伝播セグメント木の使い方，ACLPC: K – Range Affine Range Sum の解説
処理したい更新クエリが条件 5 を満たしていない，つまり，$h$ が「同種の」クエリではなくなってしまう場合もあります．その場合，更新クエリの意味をより広く解釈すると上手くいくこともあるのですが，これは少し高度な話なのでこの記事では扱いません． 例題: ACLPC: K - Range Affine Range Sum実際にどのような思考過程で遅延セグ木の問題を解くのか，例題で解説します．AtCoder Library の lazysegtree を使って実装します． 問題ページ: AtCoder Library Practice Contest: K - Range Affine Range Sum $s_{[l, r)}$ の素朴な構成まず，$a_{[l, r)}$ から抽出する情報 $s_{[l, r)}$ を構成し，上で説明した $3$ つの条件を満たすかどうかを確認します． 取得
最小共通祖先を求めるアルゴリズムの形式検証 | Wantedly Engineer Blog
競技プログラミングには概念を知っておかないと解きようがない、いわゆる覚えゲーのような問題が存在します。典型的な例が 10^9+7 といった素数で割った余りを求めろといったもので、普段業務で日常的に素数で割った余りを求めている人でもなければ、割り算がしたければフェルマーの小定理や拡張ユークリッドの互除法を使えば良いと直ぐには思い付けないのではないでしょうか。 最小共通祖先も覚えゲーで必要な概念の一種と言えます。これは読んで字のごとく、与えられた根付き木の下で2頂点に共通する祖先のうち、最も根から遠い頂点を指す概念で、例えば木の2頂点が与えられて、頂点間の経路について何かを求めろといった問題で威力を発揮することが多いです。これを用いて解ける例を挙げるとすると次の問題でしょうか。 https://atcoder.jp/contests/abc014/tasks/abc014_4 最小共通祖先を求
セマフォとは 【 semaphore 】 - 意味/解説/説明/定義 ： IT用語辞典
概要 セマフォ（semaphore）とは、コンピュータで並列処理を行う際、同時に実行されているプログラム間で資源(リソース)の排他制御や同期を行う仕組みの一つ。当該資源のうち現在利用可能な数を表す値のこと。 セマフォはコンピュータ上の共有資源について、利用可能な資源の数を指し示している。プログラムが資源を占有するときはセマフォの値から1を減じ、処理が終わって解放する際には1を加える。セマフォが0のときは空いている資源がないため正の値になるまで待機する。セマフォの値を同じ資源に同時にアクセスできるプロセスの数として扱う場合もある。 資源を獲得しセマフォを減じる処理を「P操作」、資源を解放しセマフォを加える処理を「V操作」という。関数名などではP操作を「down」「wait」「acquire」「pend」などの語で、V操作を「up」「signal」「release」「post」などの語で表すこ
sangmin.eth @ChoimiraiSchool on Twitter: "これは、子供たちにプログラミングを教える上でも大変効果的な方法✨。面白いし、結果を見てどんな改善が必要なのか考えるのでアルゴリズムの基礎が学べる。 https://t.co/JoCJcINg9u"
これは、子供たちにプログラミングを教える上でも大変効果的な方法✨。面白いし、結果を見てどんな改善が必要なのか考えるのでアルゴリズムの基礎が学べる。 https://t.co/JoCJcINg9u
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
書泉グランデMATH【営業時間11時～20時】 on Twitter: "1月中旬新刊予定 『計算科学講座 20世紀のトップ10アルゴリズム 』 監修：金田 行雄/笹井 理生 編集：張 紹良（共立出版） 10個のアルゴリズムそれぞれの代表的な研究者に執筆を依頼し，その黎明から今日までの発展の歴史や理論の… https://t.co/6jrksJ2ajd"
™ on Twitter: "クイックソートの実装で，データを 1:1 に分けるのを目指すより 1:4 みたいに偏らせたほうが *分岐予測ミスが減るので* 早い，という話を聞いた（まじか）"
あるエンジニアの面接で、ソートについて聞かれたら
千葉の高専生、ハッカソンで最優秀賞 「量子コンピューターでお手軽機械学習」とは：朝日新聞GLOBE＋
杏仁まぜそば on Twitter: "理系なのでこういう図と式のある記事好き フェイクの姿が見えた SNS蝕む誤情報のすみか：日本経済新聞 https://t.co/Gs8BzyMMc7 https://t.co/4fDAgu6LKK"
Mori on Twitter: "「きたまさ法」という名前を使わないで「Fiduccia のアルゴリズム」と呼んで欲しいんですけどね。無知を文化と言うな、ということで。"