チェスにおける思考｜antilles
「チェス(将棋、囲碁、その他任意のボードゲーム)をやると頭がよくなる」。これは、様々なところで言われていることです。それでは、チェスを行う上での思考とはどのようなものかを考えてみたいと思います。 誤りの指摘、コメント等歓迎します。 1. アルゴリズムとヒューリスティクスいきなり用語を出してしまいましたが、アルゴリズムとヒューリスティクスとは、人間がものごとを思考するときに用いる2つの方略のことを指す心理学用語です。 アルゴリズムとは「「計算可能」なことを計算する、形式的な（formalな）手続きのこと、あるいはそれを形式的に表現したもの。(出展: https://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0)」であり、ヒューリスティクスは「必ず正しい答えを導けるわけではないが、ある程
【競プロ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」などの語で表すこ
「膨大な桁数の素因数分解が可能なアルゴリズム」を開発したら政府機関に殺されてしまうのか？
代表的な公開鍵暗号の1つであるRSA暗号は、「桁数が大きい合成数の素因数分解が困難である」ということを安全性の根拠とした暗号方式です。そのため、「膨大な桁数の素因数分解を可能にするアルゴリズム」が開発されてしまえば、その安全性は揺るぎます。もし、「膨大な桁数の素因数分解を可能にするアルゴリズム」を開発した場合に何が起きるのかについて、実名制Q＆AサイトのQuoraでさまざまな人々が独自の見解を発表しています。 If I solve integer factorization, will I get killed because I would have broken cryptography? - Quora https://www.quora.com/If-I-solve-integer-factorization-will-I-get-killed-because-I-would-ha
カルマンフィルターについて - Qiita
#はじめに 千葉大学/Nospareの米倉です．今回はカルマンフィルターについて解説していきたいと思います． #カルマンフィルターで何が出来るの？ フィルターとあるように，カルマンフィルターが出来る基本的なことは線形ガウス状態空間モデルのフィルタリング密度を逐次的に求めることです．ここで２つのキーワード，「線形ガウス状態空間モデル」と「フィルタリング密度」という単語が出てきましたので，まずはそれらについて解説します． #線形ガウス状態空間モデルとは 状態空間モデルとは2つの確率過程からなります．1つは潜在変数・状態変数・隠れ変数といわれるもので，これは直接観測できないがマルコフ連鎖に従う変数だとモデリングされます．例えば景気の良し・悪し等，概念として存在するけれど直接は観測できないものを想像してください．2つめは観測値で，これは直接観測できるもの，つまりデータです．ただし変数に依存して観測
Nospare on Twitter: "カルマンフィルターについて解説します！ https://t.co/HCtnAo6KJZ"
カルマンフィルターについて解説します！ https://t.co/HCtnAo6KJZ
コラム - グーグルのクラウドを支えるテクノロジー | 第108回 Googleのサーバークラスターのメモリー圧縮機能（パート2）｜CTC教育サービス 研修/トレーニング
[IT研修]注目キーワード Python UiPath(RPA) 最新技術動向 Microsoft Azure Docker Kubernetes 第108回 Googleのサーバークラスターのメモリー圧縮機能（パート2） (中井悦司) 2021年7月 はじめに 前回に続いて、2019年に公開された論文「Software-defined far memory in warehouse-scale computers」に基づいて、Googleのサーバークラスターで用いられる独自のメモリー圧縮機能について解説していきます。これは、長期間アクセスされていないデータをメモリー上で圧縮することにより、利用可能なメインメモリーを増加するというもので、「far memory」と呼ばれるメモリーアーキテクチャーから着想を得た仕組みになります。 プロモーションレートのSLO設定 前回の記事では、「長期間アク
sangmin.eth @ChoimiraiSchool on Twitter: "これは、子供たちにプログラミングを教える上でも大変効果的な方法✨。面白いし、結果を見てどんな改善が必要なのか考えるのでアルゴリズムの基礎が学べる。 https://t.co/JoCJcINg9u"
これは、子供たちにプログラミングを教える上でも大変効果的な方法✨。面白いし、結果を見てどんな改善が必要なのか考えるのでアルゴリズムの基礎が学べる。 https://t.co/JoCJcINg9u
Le Algorithm: 高速な全点対最短経路アルゴリズム
理論計算機科学 (Thoerotical Computer Science) の色んな定理やアルゴリズムを紹介していきます. 基本的には日本語の資料がほとんどないような知見を解説していきます. 執筆者: 清水 伸高 https://sites.google.com/view/nobutaka-shimizu/home 1. 全点対最短経路問題の計算量の外観 グラフ $G$ が与えられたときに全点対最短経路(APSP : all pair shortest paths)を求めたいときがあります. そんなときはほとんどの人がワーシャル・フロイド法または各点ダイクストラなどを使うかと思います. しかしこれらのアルゴリズムは頂点数 $n$ に対して最悪 $O(n^3)$ 時間かかってしまうので, $n=1000$くらいでもちょっと厳しい感じがあります. 実は辺重み付きグラフのAPSPの計算量には多
All Pairs Shortest Paths のアルゴリズムさんたち - koyumeishiのブログ
前書き 全点対最短経路問題 (APSP : All Pair Shortest Path) を解くアルゴリズムを 4 つ紹介します。 $V$ 頂点 $E$ 辺の非負重み有向グラフ $G$ を考えます。 負の重みがあるときは一回 Bellman-Ford か何かを使ってポテンシャルを計算すれば非負に直せると思います。 お品書き Warshall-Floyd 法 Dijkstra 法を $V$ 回 Hidden Path Algorithm SHORT Algorithm 1,2 はお馴染み。 3,4 は資料も全然ないし使われてない印象。 どちらも Dijkstra を何度も回すのは無駄が多いから使いまわせるところを使いまわそうって発想のアルゴリズム。 1,2 を押さえておけば大抵の場合 (特に競プロ(非マラソン)) は問題なくて、 3,4 は少しでもいいから高速化したいときに使う可能性がある
リバーシプログラムの作り方 サンプル
序章 はじめに リバーシのルール ソースコードの記述について 第１章 盤面の処理 1.1 定数と関数の定義 1.2 盤面の生成、初期化 1.3 石を返す処理 1.4 返せる石数を調べる処理 1.5 盤面をコピー、反転させる処理 1.6 その他の盤面処理 1.7 盤面の操作と表示 第２章 ゲーム木と探索 2.1 コンピュータ思考の関数定義 2.2 各関数の実装 2.3 ゲーム木 2.4 MinMax法とNegaMax法 2.5 αβ法 第３章 盤面の評価 3.1 評価関数の定義 3.2 パターンによる局面評価 3.3 評価クラスの構造 3.4 評価クラスの生成とファイルの読み書き 3.5 評価関数の実装 3.6 評価パラメータの更新 3.7 中盤の探索 3.8 自己対局による学習 第４章 性能改善 4.1 石数取得の高速化 4.2 着手の高速化 4.3 候補手リストの導入 4.4 終盤探索の
How to leverage optimal transport
大幅な加筆改訂を加えた最新版はこちらです： https://speakerdeck.com/eumesy/optimal-transport-for-natural-language-processing --- 最適輸送の使い方 〜最適輸送の直感的理解のための単語埋込入門 兼 最適輸送入門〜 【これは何？】 自然言語処理を中心に多くの利用例を挙げながら、最適輸送の直感的な理解を目指すスライドです。 「こんな風に使うことができるんだ… 面白い道具じゃん」「こういう使い方をしたかったらこういうキーワードで調べれば良いのね」と知識にアンカーを張ることが目的です。より深く知りたい人のための参考文献もできるだけ潤沢に加えました。 また、例として頻繁に活用する自然言語処理に馴染みがないかたのために、最初に単語埋め込みのチュートリアルをつけてあります。 【コンテンツ】 1. 単語埋込入門 … 「分布仮
AGC018: C – Coins を離散凸解析（L 凸関数最小化）で解く
頂点集合が $U = \set{1,\dots,N},$ $V = \set{1,2,3}$ である完全二部グラフ $G = (U, V; E)$ を考える．以下が与えられる: 正整数 $b_1, b_2, b_3$（ただし $b_1 + b_2 + b_3 = N$），各辺 $(i, j) \in E$ の正整数重み $c_{ij}$．以下の $2$ 条件を満たすように辺部分集合 $S \subseteq E$ を選ぶとき，重みの和 $\sum_{(i, j) \in S} c_{ij}$ の最大値を求めよ: 二部グラフ $(U, V; S)$ において各頂点 $i \in U$ の次数は $1$，二部グラフ $(U, V; S)$ において各頂点 $j \in V$ の次数は $b_j$． 入力に対する制約$3 \leq N \leq 10^5$$1 \leq c_{ij} \leq
Binary search with modern processors
第16回 StringBeginners での発表資料
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
杏仁まぜそば on Twitter: "理系なのでこういう図と式のある記事好き フェイクの姿が見えた SNS蝕む誤情報のすみか：日本経済新聞 https://t.co/Gs8BzyMMc7 https://t.co/4fDAgu6LKK"
Mori on Twitter: "「きたまさ法」という名前を使わないで「Fiduccia のアルゴリズム」と呼んで欲しいんですけどね。無知を文化と言うな、ということで。"
kinaba on Twitter: "広告で出てきたゲームなんかアルゴリズム的に面白そうだったので始めてしまった。同じ色の上、または空のところになら色水を注ぎ換えられる。全部の試験管を単色にできたらクリア。これ多項式時間で解けるかなNP完全かな…と考えたいのだが、つい… https://t.co/j0u9Vo5Dr8"
Hal Tasaki on Twitter: "遅ればせながら早水さん @hayamizu_lab のグラフ理論入門講義を仕事の合間に順に聴講してようやく連載（？）に追いつきました！ それにしても、みなさんおっしゃるように、これは本当に素晴らしい。YouTube 上の最高級の文… https://t.co/738Eahx1wk"
