Othello is Solved 論文解説 (私見) - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 今朝起きたら、とんでもない論文を見つけました。 Othello is Solved ゲームの オセロが"解かれた(弱解決)" というのです。飛び起きました。それで、16時まで二度寝してから読みました。 注意すべきは、この論文が査読を経て公開されているわけではないこと、つまり形式上特にチェックを受けたものではないことです。ただ、タイトルからして非常に衝撃的ですので、個人的に読んでみました。この記事では、私がこの論文(およびソースコード)を読んでわかったことを、なるべくわかりやすくまとめます。随時更新します。 余談ですが、このタイトルはどう
リレーショナルデータベースシステムを趣味で開発している者です。 現在、開発中のシステムを並行トランザクションへ対応させることを検討しており、どのような手法があるのか調べたところ、SS2PLもしくはS2PLという手法が私と同じように自作をされている方々の中では多く採用されているようだと分かりました。 一方で、PostgreSQLやMySQLなどのプロダクションレベルで利用されているシステムではMVCCと呼ばれる手法が採用されているということも分かりました。 きっと後者の方が多くの場合で高いスループットが得ら
リレーショナルデータベースシステムを趣味で開発している者です。 現在、開発中のシステムを並行トランザクションへ対応させることを検討しており、どのような手法があるのか調べたところ、SS2PLもしくはS2PLという手法が私と同じように自作をされている方々の中では多く採用されているようだと分かりました。 一方で、PostgreSQLやMySQLなどのプロダクションレベルで利用されているシステムではMVCCと呼ばれる手法が採用されているということも分かりました。 きっと後者の方が多くの場合で高いスループットが得られるということなのだと思うので、可能であればMVCCを採用したいのですが、あまり初学者向けの実装例も見当たらず、どうしたものかと悩んでおります。 SS2PL/S2PLとMVCCの実装の難易度・工数はどの程度違うものなのでしょうか？ また、初めてリレーショナルデータベースシステムを開発する者
頭が痛くならない「ダメージ計算式」の基本の話｜だらねこ
戦闘のあるゲームを作るなら、考えないといけないのがダメージの計算式。でも、計算式のコツとか基本とか調べると、小難しそうな話が出てきて め、めんどくせぇ～ってなったりしませんか？私はなります。色んな計算式とその特徴を羅列されても、よくわかんなくなっちゃう。 とはいえ私もゲームデザイナーの端くれなので、ダメージ計算式を考える機会がそれなりにあります。そして他人の作った変な計算式に苦しめられることも、いっぱいあります。泣きたい。 大元の計算式が悪いと、それを利用してバランス調整しても苦労する事が多いんですよ。なので、そんな悲劇を少しでも食い止めるためにもですね。 この記事では 数字が苦手な文系の人でも、なんかいい感じに計算式を考る…とっかかりになることを目指して書いていこうかと思います。 ※こういう計算式がある！選んで使え！！という記事ではありません。 ※計算式を考える時、こういうのを把握して、
「量子」と組合せ最適化に関する怪しい言説 ―とある研究者の小言― - むしゃくしゃしてやった，今は反省している日記
最近，量子コンピュータの話題をニュースや新聞で見かけることが増えてきました． その中で気になってきたのが，組合せ最適化と量子コンピュータ（特に量子アニーリング）に関する怪しい言説．私自身は（古典コンピュータでの）組合せ最適化の研究をやってきて，量子コンピュータを研究しているわけではないのですが，さすがにこれはちょっと・・・と思う言説を何回か見かけてきました． 最近の「量子」に対する過熱ぶりは凄まじいので，こういう怪しい言説が広まるのは困りものです．すでにTwitter上には，“組合せ最適化は今のコンピュータでは解けない”とか“でも量子なら一瞬で解ける”という勘違いをしてしまっている人が多数見られます*1． さすがに危機感を覚えてきたので，この場できちんと指摘しておくことにしました． 今北産業(TL;DR) “古典コンピュータは組合せ最適化を解けない” → 古典コンピュータで組合せ最適化を解
東京大学、量子コンピューティング入門教材が無料公開 ゼロから自習できる教材目指す | Ledge.ai
画像は公式サイトより 東京大学素粒子物理国際研究センター（ICEPP）の研究者が選定・執筆した、量子コンピューティングを手を動かして学びたい人向けの入門教材「量子コンピューティング・ワークブック」が無料公開されている。SNS上では本教材について「面白そう！」「いい時代になったなぁ」などのコメントが見られる。 本教材は、量子力学や計算科学の前提知識を極力必要とせず、大学1年程度の数学とPythonプログラミングの知識があれば、ゼロから量子コンピューティングを自習できるような教材を目指しているという。 公式サイトより 内容は「量子コンピュータに触れる」「超並列計算機としての量子コンピュータ」「量子ダイナミクスシミュレーション」「ショアのアルゴリズム」「グローバーのアルゴリズム」「変分法と変分量子固有値ソルバー」「量子・古典ハイブリッド機械学習」「補足」で成り立っている。 公式サイトでは「私たち
現役高校生が、AtCoderでレッドコーダーになるまでにやってきたこと。プログラミング上達の秘訣を全て教えます - Findy Engineer Lab
こんにちは、はじめまして。筑波大学附属駒場高等学校 3 年生（今年 4 月から東京大学に入学予定）の米田優峻（@e869120）と申します。私は競技プログラミング（競プロ）が趣味で、AtCoder・情報オリンピック・パソコン甲子園などの大会に出場しています。2021 年 3 月時点で、AtCoder では赤色（レッドコーダー）です。また、国際情報オリンピックの 2018 年／2019 年／2020 年大会で金メダルを獲得しています。*1 とはいえ、決して簡単にこの記録を手に入れられたわけではありません。何度も挫折と失敗を経験しながら自分のスキルを磨いた結果、競プロを始めてから 3 年後にはレッドコーダーになることができたのです。 今回は「わたしの選択」というテーマで寄稿の機会を頂いたので、私が中学 1 年生の秋に競技プログラミングを始めてからレッドコーダーになるまで、そして国際情報オリンピ
アルゴリズム本、書きました！ - Qiita
最後に、17 章で PとNPに関する話題を解説し、世の中には「効率的に解くアルゴリズムを設計することができそうにない難問」が多数あることを見ます。18 章で、これらの難問に取り組むための方法論をまとめます。 競プロをやっている方向け 扱っている題材の難易度については、こんな感じのイメージです！ チーター本 < 本書 = 螺旋本 < 蟻本 難易度が近い螺旋本は、スタンスが異なる部分もありますので、よい形で共存できたら、という想いです。 螺旋本と比べると、「動的計画法」「貪欲法」「二分探索法」などの設計技法に関する話題をより重視しています 螺旋本は「ライブラリを揃えていく」という思想なので、設計技法よりもライブラリになるものを重視する立場です 本書では、紙面の都合で「計算幾何学」と「整数論」には触れられませんでしたが、これらは螺旋本には載っています 2-2. 本書の対象読者 本書は、「アルゴリ
超高速！多倍長整数の計算手法【前編：大きな数の四則計算を圧倒的な速度で！】 - Qiita
1. はじめに ～メインを読むための準備～ まず、大きな数の計算の話をする前に、少しコンピューターと計算回数について話しましょうか。 コンピューターは、現代ではソフトウェアやアプリケーションの開発に使われていますが、これには重要な背景があります。これは「計算がめっちゃ速いこと」です！人間なんかと比べたら、圧倒的な計算スピードを誇ります。 1-1. 人間の計算速度はどのくらい？ まず人間はどのくらいの速度で計算できるでしょうか？速い人も遅い人もいると思います。 例えば、$628 \times 463$ の計算を、今やってみましょう。10 秒以内で計算できたらかなり速い方でしょう。この計算では、次のように「単純計算」を合計 28 回もしていることになります。 9 回の 1 桁 × 1 桁の掛け算 6 回の 1 桁 × 1 桁の足し算 13 回の繰り上がり計算 もし $628 × 463$ が
競技プログラミングで頻出の「ダブリング」を解説する
競技プログラミングでは頻繁に出てくる「ダブリング」という手法について説明しようと思います。 競プロをはじめて間もない人や、競プロ外の人に向けて書きたいと思います。 最初に予防線を張っておきますが、内容が正しいかどうかは保証しません。 繰り返し二乗法繰り返し二乗法という有名なアルゴリズムがあります。 例えば、3の100億(10^10)乗を計算せよと言われた時に、 1回1回計算していたのでは時間がいくらあっても足りません。 しかし繰り返し二乗法を使えば、log(100億)くらいの計算量で計算出来るようになります。 具体的にどういう仕組みかを説明するために より小さな場合として3の11乗を計算するとした時に、 3^11 = (3^8) x (3^2) x (3^1) と3^(2^k)の積に分解出来るならば、 11を1011と2進数で表した時の1の数分だけで計算が終わることになります。 （a^bは
プラレールを使ったプログラミング的思考の話：テキシコー【2020/04/06】 | 何ゴト？
電動のプラレールを走らせる時に、レールの途中でゲートを付けると、 電車は先に進まず、レールの方が手前に向かって動く。 それを踏まえて、このような円の形にすると、どうなるか？ こうなります。 電車が走る → ゲートに当たる → レールが回る → 三角形がゲートを上げる → 電車が走る → （以降は繰り返し）
競技プログラミングで解法を思いつくための典型的な考え方 | アルゴリズムロジック
競技プログラミングの問題を解くためには２つのステップがあります。 問題で要求されていることを言い換える知っているアルゴリズムやデータ構造を組み合わせて解く 必要な（知っておくべき）アルゴリズムやデータ構造は色々なところで学ぶことができます。 しかし、「問題の言い換え」や「アルゴリズムを思いつく」というのは、非常に様々なバリエーションがあり、問題をたくさん解かないとなかなか身につきません。 そこで、この記事は以下のことを言語化し、練習のための例題を提示することを目標とします。 問われていることを、計算しやすい同値なことに置き換える方法アルゴリズムを思いつくための考え方競技プログラミングで「典型的」と思われる考え方 ※一部問題のネタバレを含むので注意 ※良く用いられるアルゴリズムやデータ構造については競技プログラミングでの典型アルゴリズムとデータ構造 を参考にして下さい。 入力の大きさ(制約)
動的計画法
動的計画法(Dynamic Programing)は、国内予選レベルではおそらく知らなくてもだいじょーぶです。しかし、４問以上を目指しているのなら、おさえておいた方がいいかもしれません。 というか、あまり上手く説明できないかも。 ここで言う動的計画法は、簡単に言うと、いつ計算しても同じになる値をどこかにとっておいて いつでも呼び出せるようにすることで、重複計算を避けようという考え方です。 私の経験から言わせてもらえば、次のような問題に適応することで効果的な場合が多いです。 ・元の問題を小さな部分問題に分割できる。 ・その部分問題の答えからもとの問題の答えを導ける。（小さいほうから順番に計算できる） ・一番小さな部分問題はすぐに解ける。 ・小さいほうの部分問題は何回も呼び出される。 ・状態数がそんなに大きくない。（大きくないの基準は問題による。） これについては後で述べるとして、例を見てみま
プログラミングできる人とできない人との間の深い溝 - masatoi’s blog
どうしてプログラマに・・・プログラムが書けないのか?を読んでいて出てきたので出展の一つを訳してみた。Separating Programming Sheep from Non-Programming Goatsの和訳。 プログラミングというものには向き不向きが強く出るということはわりと知られていると思うが、このエントリではプログラミングができるかできないかは比較的簡単なテストによって、プログラミングの訓練を始める前の段階で分かると主張している。どうしてプログラマに・・・プログラムが書けないのか?では、そもそもこの事前テストをパスしていないような人達までプログラマとして応募してくると言っており、その判定法として有名なFizzBuzz問題を挙げている。 追記（2019/2/28) 注意： なおこの論文はしばらく前に著者の一人によって撤回されたようです Camels and humps: a r
アルゴリズムとは何か！？ ～ 文系理系問わず楽しめる精選 6 問 ～ - Qiita
今の場合は A さんが 31 歳の場合のストーリーでしたが、A さんが 20 歳～ 35 歳のうちのどの年齢であったとしても、似たようなストーリーで必ず 4 回の質問で当てることができます！(他の例も是非考えてみてください。) ちなみに、このような「真ん中で切ってどちらかに絞って行く」タイプのアルゴリズムには二分探索法という名前がついています。応用情報技術者試験でも頻出のテーマですので馴染みのある方も多いと思います。 1-2. つまり、アルゴリズムとは 上の年齢当てゲームという問題では、相手の年齢を当てる「方法・手順」を二分探索法に基づいて導きました。このようにアルゴリズムとは、 問題を解くための方法・手順 のことです。さて、アルゴリズムと聞くと「コンピュータ上で実装されたプログラム」のことを思い浮かべる方も多いと思いますが、必ずしもコンピュータと関係がある必要はなく、日常生活でも多々登場
ソートアルゴリズムを極める！ 〜 なぜソートを学ぶのか 〜 - Qiita
NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。 今回はソートについて記します。 0. はじめに データ構造とアルゴリズムを学ぶと一番最初に「線形探索」や「ソート」が出て来ます。これらのテーマは応用情報技術者試験などでも頻出のテーマであり、アルゴリズムの Hello World とも呼ぶべきものです。 特にソートは、 計算量の改善 ($O(n^2)$ から $O(n\log{n})$ へ) 分割統治法 ヒープ、バケットなどのデータ構造 乱択アルゴリズムの思想 といった様々なアルゴリズム技法を学ぶことができるため、大学の授業でも、アルゴリズム関連の入門書籍でも、何種類ものソートアルゴリズムが詳細に解説される傾向にあります。本記事でも、様々なソートアルゴリズムを一通り解説してみました。 しかしながら様々な種類のソートを勉強するのもよいが、「ソートの使い方」や
x + 0.25 - 0.25 = xが成り立たないxとは何か｜Rui Ueyama
スタンフォードのコンピュータサイエンスの授業で、ときどきこれは良問と思う問題がテストで出ることがある。僕の印象に残っているのは「xをfloatとするとき、x + 0.25 - 0.25 = xが成り立たないxを求めよ」というものだ。浮動小数点数を理解していないと、両辺が同じにならないケースがあるほうが不自然に思えるだろうから、この問題は浮動小数点数の奇妙さを結構うまく突いていると思う。この問題を元に浮動小数点数についてちょっと説明してみよう。 まずコンピュータ上での数について少し考えてみよう。コンピュータにおける数と、数学の整数や実数は、よく考えてみると全然違う。コンピュータは有限の記憶領域しか持っていないので、無数にある数を表すことが根本的にできない。つまりコンピュータ上の数は「本物の数になるべく似せた別の何か」だ。現実的には、例えば32ビットの数なら2^32パターンしか表せないので、そ
エレベータに見るアルゴリズムの性能と公平性のバランス｜Rui Ueyama
現実世界でもコンピュータの中でも、何らかの性能指標だけを追求すると参加者にとって極端に不公平になってしまうことがある。例えばエレベータとHDDは共通点がありそうに思えないが、この2つは性能特性的にとてもよく似ていて、リーズナブルな性能と公平性を両立させるために同じ制御方法が使われている。これについてちょっと説明してみよう。 1基しかない場合のエレベータの動き方は単純だ。一度上に動き出すと、上で待ってる人や降りる人がいる限り上昇し続ける。同じように、一度下に動き出すと、下で待っている人や降りる人がいる限り下降し続ける。これ以外の動き方をするエレベータはまず存在しないので、これが唯一の制御方法のように思えるけど、別にこうしなければいけないというルールはない。 エレベータの平均待ち時間を最適化することを考えてみよう。そうすると、一方向に動き続ける代わりに、エレベータが現在存在する階に一番近い人の
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
https://utokyo-icepp.github.io/qc-workbook/welcome.html
Hyperskill
http://cslibrary.stanford.edu/105/LinkedListProblems.pdf