【連載】Let’s 競技プログラミング! E8さんが教える アルゴリズム発想のキホン競技プログラミング大会・AtCoderのレッドコーダーであるE8さんが、アルゴリズム発想のキホンをレクチャーします。
クリエイティブコーディングの教科書
ゲームエンジンや3Dソフトウェアを利用して高度な表現ができるこの時代でも、プリミティブな描画や動き、アルゴリズムから学べることは多い。それらをJavaScriptで書くクリエイティブコーディングという形で学べる手引書が本書となる。
できるだけ嘘を書かずに計算量やオーダーの説明をしようとした記事 - えびちゃんの日記
計算量についてのお話です。対象は、プログラミング経験はあるが計算量のことを知らない初心者から、計算量のことを知っているつもりになっている中級者くらいです。 数式を見たくない人にとっては読むのが大変かもですが、深呼吸しつつ落ちついて読んでくれるとうれしいです。 それから、この記事が自分には合わないな〜と思ったときは、（別の記事を Qiita とかで検索するよりも）この記事の一番下の 参考文献 にある本を読むことをおすすめします。Amazon の試し読みで無料で読めます*1。 TL; DR 関数の増加度合いのことをオーダーと呼ぶよ 計算量は、入力サイズ（など）を受け取ってアルゴリズムの計算回数（など）を返す関数だよ その関数のオーダーについての議論がよく行われるよ オーダーを上から抑えるときは \(O\)、下から抑えるときは \(\Omega\) を使うよ オーダーを上下両方から抑えたいときは
コンピューターはどうやって乱数を生み出しているのか？
テレビゲームやギャンブル、暗号は一見すると全く関係ないように思えますが、実はすべて「乱数」を利用しており、現代人の生活は乱数なくして成立しません。そんな乱数をコンピューターでどうやって生成させているのかを、プログラミング関連のブログ・BetterProgrammingが解説しています。 Generating Random Numbers Is a Lot Harder Than You Think | by Sunny Beatteay | Sep, 2021 | Better Programming https://betterprogramming.pub/generating-random-numbers-is-a-lot-harder-than-you-think-b121c3e75d08 プログラミングで乱数を使いたい場合、例えばRubyの場合は「rand」、Pythonの場合は
リバーシプログラムの作り方 サンプル
序章 はじめに リバーシのルール ソースコードの記述について 第１章 盤面の処理 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 終盤探索の
Binary search with modern processors
第16回 StringBeginners での発表資料
二分探索よりお得なオンライン価格戦略 - 麻辣坊主
オンライン価格設定で面白いと思った結果を紹介します． 「適正価格を二分探索するとそこそこ良い方法になるが， 二分探索に少し手を加えるとさらに良い方法になる」という話です． 出典は R. Kleinberg and T. Leighton (FOCS 2003) の Theorem 2.1 です． この記事自体は Haifeng Xu 先生の講義スライド の第 1 回をかなり参考にしてます． ゲーム理論と機械学習の様々な興味深いトピックが網羅されていておすすめです． 問題設定 戦略の評価尺度：リグレット 自明な $\mathrm{O}(N)$ リグレット戦略 二分探索による $\mathrm{O}(\log N)$ リグレット戦略 二分探索を改良した $\mathrm{O}(\log\log N)$ リグレット戦略 まとめ 問題設定 あなたは A さんに $N$ 個のリンゴ を，$1$ 日
ファミコンゲームについて
Karu_gamo★★☆☆☆ @Karu_gamo 『アトランチスの謎』のマップデータ、(16x16pixを１マスとして)縦８マス分の短冊状のデータをテーブル化してるっぽい。縦は240pix÷16pix=15マスなので、上下で別の短冊データということになる(1つ余る)。上下で別々に設定できるから、こういう上下分割されたステージが作りやすいようだ。 pic.x.com/PotOYMfPJm 2024-11-02 16:24:04 Karu_gamo★★☆☆☆ @Karu_gamo 屋外ステージでは、上半分は空白が続くので短冊データは１つで済む(たまに雲があるが)。凝る必要があるのは下半分だけなので効率良さそう。ちなみにこの背の高い木がちょうど半分になっている(下１マスあまる)。 pic.x.com/clsajkoc30 2024-11-02 16:24:05
ネットワークフロー問題たちの関係を俯瞰する - 私と理論
ネットワークフロー好き好きマンとして，フローを布教したくなったので記事を書きました． ただし，フローの解説資料は既に素晴らしいものがたくさんあるので，今回は今まであまり焦点が当てられてこなかった部分を推して話をしたいと思います． テーマは，数あるフローの問題の関係を整理することです． フローの問題たちには共通の歴史があり，共通の定式化があり，共通のアルゴリズムの思想があります． その「共通」の部分を理解することで，フローに対する理解が深まり，より面白いと感じられると僕は思っていて，そこについて書きます． かなり基本的な内容しか書いてないので，強い人が得るものはあまりないかもしれません． あとこの記事はおきもちを書いてる部分が多いです． また，この記事では問題の話だけをしてアルゴリズムの詳細の話をほとんどしません．この辺りは 保坂さんのスライド などが非常に分かりやすいので，そちらを参照して
アルゴリズム・AtCoder のための数学【前編：数学的知識編①】 - Qiita
こんにちは、大学 1 年生になったばかりの E869120 です。 私は競技プログラミングが趣味で、AtCoder や日本情報オリンピックなどに出場しています。ちなみに、2021 年 4 月 7 日現在、AtCoder では赤（レッドコーダー）です。 本記事では、アルゴリズムの学習や競技プログラミングで使える数学的な部分を総整理し、それらについて解説したいと思います。前編・中編では数学的知識、後編（2021/4/26 公開予定）では数学的考察の側面から書いていきます。 【シリーズ】 アルゴリズム・AtCoder のための数学【前編：数学的知識編①】 ← 本記事 アルゴリズム・AtCoder のための数学【中編：数学的知識編②】 アルゴリズム・AtCoder のための数学【後編：数学的考察編】 1. はじめに 21 世紀も中盤に入り、情報化社会（いわゆる「IT 化」）が急激に進行していく中、
ピーターソンのアルゴリズム - Wikipedia
/* * ANSI C89 source, KNF style implementation of Peterson's Algorithm. * * Copyright (c) 2005, Matthew Mondor * Released in the public domain (may be licensed under the GFDL). * * Please fix any bugs as needed, preserving the KNF style and this comment, * unless considered inconvenient in which case you can do whatever you want * with the code. */ #include <assert.h> #include <stdio.h> #include <
高速逆平方根(fast inverse square root)のアルゴリズム解説 - 滴了庵日録
高速逆平方根とは？ C言語のコード 検証 アルゴリズムの要点 [1] 逆平方根の計算を対数・指数の計算に置き換える [2] 浮動小数点型の内部表現を利用した対数・指数の近似計算 [2.1] 対数の近似 [2.2] σの最適値 [2.3] 整数型での解釈 [2.4] 逆平方根の計算とマジックナンバー0x5F3759DF [3] ニュートン法による収束で精度アップ 感想 高速逆平方根とは？ 高速逆平方根(fast inverse square root)とは、平方根の逆数 を高速に計算するアルゴリズムです。平方根の逆数は逆平方根とも呼ばれます。逆平方根はベクトルの正規化などに用いられるので、これを高速に計算できるアルゴリズムには大きなご利益があります。 参照： Fast inverse square root - Wikipedia C言語のコード 高速逆平方根の関数を示します。0x5F375
オブジェクト指向プログラミング入門
きしだൠ(K1S) @kis オブジェクト指向について、技術的には「オブジェクト指向は差分プログラミングとデータ分類をまぜて考えてややこしくなる。分離せよ。そして差分プログラミングにはラムダを使え。データ分類のときはオブジェクト指向じゃなく型を考えろ」っていう主張になった。 2022-02-28 12:22:33 きしだൠ(K1S) @kis 「オブジェクト指向は差分プログラミングとデータ分類を同時に行う手法」という見方。 もっといえば、継承の用途を差分プログラミングとデータ分類の2種類にわけた。その上でそれぞれについてのオブジェクト指向離れを考えた。 2022-02-28 12:25:12 きしだൠ(K1S) @kis ここから考えると、オブジェクト指向の技術的欠点は差分プログラミングとデータ分類を不可分に考えてしまったところか。 継承を使うと差分プログラミングとデータ分類が同時にできて
計算できるもの、計算できないもの
計算機による計算とは何か、計算できるものとできないものの境界はどこにあるのか―それを明らかにする計算理論は、計算機科学においてもっとも基本的、かつ重要なものです。本書では、概念の説明や、結果の証明にPythonプログラムを利用する実践的なアプローチにより、計算可能問題と計算不能問題、扱いやすい問題と扱いにくい問題があること、文章では簡単に表現できても計算機には解けない重要な問題が数多くあること、効率よく解ける問題と解けない問題があることなどを、計算理論の礎を築いたアラン・チューリングとリチャード・カープの論文の抜粋とともに解明します。チューリングマシン、有限オートマトン、万能計算、非決定性、チューリング還元、計算量クラス、NP完全性などのトピックをカバーしています。 謝辞 まえがき:教科書として使う方へ 全体像 1章 はじめに:計算できるもの, できないものとは 1.1 扱いやすい問題 1
Linuxを生み出したリーナス・トーバルズが考える「優れたコード」とは何か？
プログラミングをする上で、コメントをきちんと残したり、わかりやすい変数名をつけたりして「読みやすいコード」を目指す作業は重要です。しかし、「読みやすいコード」と「優れたコード」の間には、時として構造上の大きな違いがあるのも事実。そんな「優れたコード」に対するLinuxの開発者リーナス・トーバルズ氏の考え方について、エンジニアのmkirchner氏が説明しています。 mkirchner/linked-list-good-taste: Linus Torvalds' linked list argument for good taste, explained https://github.com/mkirchner/linked-list-good-taste Linus Torvalds: The mind behind Linux | TED Talk https://www.ted.co
2で割ることと3で割ること - Qiita
この記事でお題にするのはCPUレジスタ上の整数除算です。以下、単に除算とも書きます。 除算は非常に高コストな演算なため、コンパイラは最適化によって、できるだけ整数除算を別の計算に置き換えようとします。 最適化ができる場合の一つとして、割る数が定数である場合があります。頭のいいコンパイラは、除算を乗算とビットシフト等を駆使した演算に置き換えます。この記事では、そういった最適化の背景にある理屈を部分的に解説します。 計算機環境としてはモダンなx86 CPUを仮定します。したがってレジスタは32/64ビットであり、負数は2の補数表現になっています。ある程度は他の命令セットでも通用する話になっているかもしれません。 そもそも整数の除算とは プログラミングにおける整数の除算の定義について確認します。整数$n$を整数$d$で割るとき $$ n = q \times d + r $$ が成り立つように除
シンプルかつ高速な文字列照合アルゴリズムを紹介します - エムスリーテックブログ
こんにちは！ エンジニアリンググループ マルチデバイスチーム 新卒1年目の小林です。 エムスリーでは、2週間に1度、Tech Talkという社内LT会（現在はリモートで）が開催されています。これは、とある回の発表テーマリストです。 Tech Talkのとある回の発表テーマリスト このように、最近エムスリーでは文字列が流行っている（？）ようなので、その勢いに乗って私も文字列照合アルゴリズムについて書きたいと思います！（業務とは全然関係ない話です） Knuth-Morris-PrattやBoyer-Mooreアルゴリズムは解説記事がたくさん出ていると思うので、この記事ではシンプルかつ高速なQuick-SearchとQuite-Naiveアルゴリズムについて説明し、速度比較を行った結果についてご紹介します。 文字列照合アルゴリズムとは テキストとパターンという文字列が与えられたときに、中に出現す
マルチスレッド・プログラミングの道具箱
まえがき クラウド上の仮想サーバから手元のスマートフォンまで、いまや複数のCPUコアを搭載するマルチコアはどこにでもある環境になりました。ハードウェア側が並列(Parallel)・並行(Concurrent)処理に向けて急速に進化する一方で、ソフトウェア側つまりプログラミング言語の進化はさほど追い付いていません。並行処理記述の手軽さを求めた Go言語 や、マルチスレッド処理の安全性を重視する Rust言語 などが登場してはいるものの、「普通にプログラムを記述するだけで複数CPUコア環境で高速に走るプログラミング言語」は遠い夢物語のままです。 モダンなプログラミング言語や並列・並行処理ライブラリは、複雑で難解なマルチスレッド処理を直接記述しなくてすむよう、安全性・利便性の高い抽象化レイヤを提供します（例：Go言語のgoroutineとchannel、Rust言語の Rayonライブラリ）。し
「実用的でないPythonプログラミング」がよかった - Stimulator
はじめに 2020/8/12に発売されたImpractical Python Projects: Playful Programming Activities to Make You Smarterの日本語訳書である、「実用的でないPythonプログラミング」をひょんな事から献本していただく事になった。（訳者が同僚である） 実用的でないPythonプログラミング: 楽しくコードを書いて賢くなろう! 作者:ヴォーン,リー発売日: 2020/08/12メディア: 単行本 ありがちなプログラミング初学者向けの本から1段上がった中級者向けの良い本だと感じたので、当ブログでたまにやっている筆者、訳者に媚びを売るシリーズの一貫として、感想を記す。 書籍の概要 「実用的でないPythonプログラミング」は、想定する中級レベルのアルゴリズムの問題を例に取り、Pythonでの美しいコードの書き方や、コンピュ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
30 分でわかる！アルゴリズムの基本
