清一色のシャンテン数を01BFSで計算する - yukinote
概要 清一色のシャンテン数は01BFSで計算できる。 機械的な計算なので、正当性が簡単に証明できる。 シャンテン数とは テンパイするまでに必要な牌の最小枚数のこと。 例えば 🀉🀊🀍🀎🀑🀒🀙🀚🀛🀜🀜🀀🀁 のとき、🀈🀌 を引いて🀀🀁を捨てればテンパイとなる。これより少ない枚数の入れ替えでテンパイすることはできないので、この手牌のシャンテン数は2となる。 この例のようにシャンテン数がわかりやすいケースがほとんどだが、清一色のような場合はシャンテン数を求めにくい。 特にプログラムでシャンテン数を計算する場合、正しいコードを書くことは難しい。また、正当性を保証するのも難しい。 考える問題 清一色だけを考える。以下では萬子🀇🀈🀉🀊🀋🀌🀍🀎🀏だけを扱う。 複数色ある場合や字牌を含む場合でも、清一色のシャンテン数さえ計算できていれば、軽いdpで解くことが
二分探索よりお得なオンライン価格戦略 - 麻辣坊主
オンライン価格設定で面白いと思った結果を紹介します． 「適正価格を二分探索するとそこそこ良い方法になるが， 二分探索に少し手を加えるとさらに良い方法になる」という話です． 出典は 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$ 日
2のべき乗サイズの配列は危ないという話 via 行列積 - elkurin’s blog
こんにちは。労働者です。とあるプログラムで学生さんの課題を添削していたら面白い話に出会いました。 僕は今、主に学部生向けのインターン研修的なプログラムでメンターなるものをやっています。メンターとしての仕事は、学生さんの課題へフィードバックを返し、Office Hourというセッションを毎週設けて質問受けやCSに関するトークを行うといった内容になっています。今回話題に取り上げるのはその中の課題の1つ、「行列積のプログラムを書いて時間を計測せよ」という何気ない話で、続く課題たちのいわば前座のようなものです。こういったところに沼は隠されているものですね。 担当している学生さんたちが細かい実験を行ってくれて以下のような疑問が提示されました。 「行列積の計算が N = 1024のときだけ N = 1023, 1025のときに比べて3倍遅いのはなぜ？」 配列のサイズが2のべき乗になるのは避けるべきとい
Red Blob Games: Hexagonal Grids
Mar 2013, updated in Mar 2015, Apr 2018, Feb 2019, May 2020, Oct 2021, Dec 2022, Feb 2023, Oct 2024, Mar 2025 This guide will cover various ways to make hexagonal grids, the relationships between different approaches, and common formulas and algorithms. I've been collecting hex grid resources[1] for over 25 years. I wrote this guide to the most elegant approaches that lead to the simplest code, st
ファミコンゲームについて
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
数あるソートアルゴリズムをビジュアル化し堪能できるサービス「SORTING」
大小の関係が決められたデータを小さい順や大きい順に並び替える作業はソートと呼ばれ、コンピュータには欠かせないプログラムです。そのため、ソートをより早く・確実に・効率良く実行できるように、さまざまなアルゴリズムが考案されてきました。そんなコンピュータの発展にかかせない役割を果たしてきたソートアルゴリズムをビジュアル化することで直感的に理解できるのが「SORTING」です。 SORTING http://sorting.at/ これがSORTINGのサイトページです。ソートアルゴリズムを選択してページ下の「PLAY」ボタンをクリックすると、そのソートアルゴリズムを使ってボールが並び替えられます。 たとえばアルゴリズム「クイックソート」でランダムに並んだ状態の大きさの異なるボールを左から小さいもの順に並び替えるとこんな感じです。 選べるソートアルゴリズムは、クイックソート・ヒープソート・スムース
過半数判定アルゴリズム（LeetCode / Majority Elementより） - Qiita
（ブログ記事からの転載） 過半数を獲得した候補者を効率的に特定するにはどんな方法が良いと思いますか？ 今日の問題は、そう読み替えてみるとなかなか奥が深いです。 [https://leetcode.com/problems/majority-element/] Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times. You may assume that the array is non-empty and the majority element always exist in the array. Example 1: Input: [3,2,3] Output: 3 Example 2: I
inversion counting
2018/10/31 勉強会 (文字が見えない方は、ダウンロードするかフルスクリーンにしてご覧ください)
ネットワークフロー問題たちの関係を俯瞰する - 私と理論
ネットワークフロー好き好きマンとして，フローを布教したくなったので記事を書きました． ただし，フローの解説資料は既に素晴らしいものがたくさんあるので，今回は今まであまり焦点が当てられてこなかった部分を推して話をしたいと思います． テーマは，数あるフローの問題の関係を整理することです． フローの問題たちには共通の歴史があり，共通の定式化があり，共通のアルゴリズムの思想があります． その「共通」の部分を理解することで，フローに対する理解が深まり，より面白いと感じられると僕は思っていて，そこについて書きます． かなり基本的な内容しか書いてないので，強い人が得るものはあまりないかもしれません． あとこの記事はおきもちを書いてる部分が多いです． また，この記事では問題の話だけをしてアルゴリズムの詳細の話をほとんどしません．この辺りは 保坂さんのスライド などが非常に分かりやすいので，そちらを参照して
安全で爆速なRollingHashの話 - Qiita
要約 ロリハ(RollingHash)のModを$2^{61}-1$にすると安全で爆速になってむちゃくちゃ幸せになれます。 前提知識 bit演算に関する基礎的な知識を要求します。 また、RollingHashについては以下で解説しますが、分からない場合は別の記事を読んだほうがいいかもしれません。 RollingHashとは? 開く 「文字列を一つの大きな整数として見る」というのがRollingHashのアイデアです。 まず、0-9のみの数字を含んだ文字列s = "1234567890"を考えてみます。 ここで、この文字列のHash値を文字列を10進数と解釈したときの数値と定義します。 また、$s$の$a$文字目から$b$文字目の前までの部分文字列を$s[a..b]$と書くことにします。 例えば、s = "1234567890"について、$s[1..3]$は1文字目から3文字目の前までの部分
Monge 行列と monotone minima について - Lorent’s diary
Monge 行列や monotone minima について何も知らない方でも理解できるよう, 一から丁寧に解説する記事を書きました. 計算量解析については多少の前提知識を要求しますが, その他の部分については式を追っていけば理解できると思います. 本記事の評判次第ではありますが, 続編として SMAWK algorithm についての記事もいずれ書きたいと考えております. Monge 行列の定義と性質 定義 補題 1 証明 補題 2 証明 補足 monotone minima アルゴリズムの解説 補足 実装例 例題 参考リンク 参考文献 謝辞 Monge 行列の定義と性質 定義 $ m \times n $ 型実数値行列 $ A $ が, $ 1 \leq i \lt k \leq m $ および $ 1 \leq j \lt l \leq n $ を満たすすべての $ i, j, k,
元情報商材屋 on Twitter: "YouTube王ヒカキンを超えたと話題のひろゆき氏。自分をフリー素材化して収益を分け合いにしちゃう発想も天才的に賢いんだけど、YouTubeのアルゴリズムを駆使して関連動画で埋めてきたり短い動画構成で再生数やコメント数を増やしまく… https://t.co/UE2KqPLICa"
YouTube王ヒカキンを超えたと話題のひろゆき氏。自分をフリー素材化して収益を分け合いにしちゃう発想も天才的に賢いんだけど、YouTubeのアルゴリズムを駆使して関連動画で埋めてきたり短い動画構成で再生数やコメント数を増やしまく… https://t.co/UE2KqPLICa
平衡二分探索木を使った2-optの効率化について - aspirator’s blog
こんにちは。 平衡二分探索木で2-optを高速化する方法について研究したので、本記事ではそれについて書こうと思います。 2-optとは 2-optは巡回セールスマン問題(TSP)の近似解を求めるヒューリスティックアルゴリズムです。 下図のように、サイクルに対してランダムに二つのパスを選び、パスを組み替えた方がサイクルの長さが短くなる場合、パスを組み替えます。具体的には、A→B + C→D > A→C + B→D の時、辺ABと辺CDを辺ACと辺BDに組み替えます。 しかし、辺を張り直すだけではサイクルにならないので、B~CまたはD~Aの間の順序を逆にする必要があります。 2-opt法では順路を配列などで管理することでこれを実現しています。 そしてこれが`測定で用いた2-optの実装です。 #include<iostream> #include<algorithm> #include<vec
画像の解像度を「2倍」にするPhotoshopの新機能「スーパー解像度」の使い方＆仕組みはこんな感じ
Photoshopには、RAWファイル現像プラグイン「Camera Raw」が付属しています。2021年3月にリリースされた「Camera Raw13.2」には、カメラで撮影した画像の解像度を2倍にする機能「スーパー解像度」が追加されているので、実際に使ってみました。 新機能「スーパー解像度」の活用方法 https://blog.adobe.com/jp/publish/2021/03/10/cc-photo-from-the-acr-team-super-resolution.html ◆「スーパー解像度」の使い方 実際に「スーパー解像度」を使って、画像の解像度を2倍にしてみます。まずは、Camera Rawで編集したい画像のRAWファイルを読み込みます。なお、「スーパー解像度」は記事作成時点では、最大で長辺6万5000ピクセル、あるいは総画素数500メガピクセルまでの画像に対応していま
グレイコード
グレイコード（Gray code）とは、２進数の表現で、隣り合う値でビットの変化が１ビットしかないようにしたものです。 たとえば、４桁の２進数（バイナリコード）で考えると、 １０進数の「７」から「８」に変化する場合、２進数では「０１１１」から「１０００」となり、 ４桁すべてのビットが０から１または、１から０へと変化します。 電気（電子）回路では、２進数の「０」、「１」を電圧の高い状態「Ｈ」と低い状態「Ｌ」で扱います。 入力回路は、「Ｈ」と「Ｌ」を検出する速度が異なります。 （Turn on time および Turn off time が異なる） 上記の「７」から「８」に変化する場合、入力回路の遅延により、 最悪「１１１１」または「００００」の値として読み込む可能性があります。 １０進数の「１５」または「０」となってしまいます。 ロータリエンコーダ（回転位置検出センサ）で、回転する軸の角度
Tsukasa #01 (4x vaccinated) on Twitter: "真偽はともかく、ちょっととんでもない論文が出てきたんだが。国際暗号学会の未査読論文だが、素因数分解を (RSA を破壊するレベルで) 劇的に高速化するアルゴリズムを開発したと主張している。 https://t.co/ApzLqRmjqR"
真偽はともかく、ちょっととんでもない論文が出てきたんだが。国際暗号学会の未査読論文だが、素因数分解を (RSA を破壊するレベルで) 劇的に高速化するアルゴリズムを開発したと主張している。 https://t.co/ApzLqRmjqR
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Gabriel Peyré on Twitter: "Oldies but goldies: R. Brockett, Dynamical systems that sort lists, diagonalize matrices, and solve linear programm… https://t.co/nFXh1FsgxH"
Karu_gamo on Twitter: "【麻雀：任天堂】任天堂初期の麻雀の中身を見てみたいと思います。とてもシンプルな二人打ち麻雀がどのようにできているのか？ メモリを除くと、自分の手牌と同じ数字の羅列が見つかります。そして、その上に相手の手牌が２列。これは配牌時ですが… https://t.co/1Tvgbu2NqV"
E869120@本発売 on Twitter: "今日は 3.11 ということで，地震対策に使われているアルゴリズムについて 4 枚の資料にまとめてみました．（自分でも気になったので，資料や論文を 2 時間くらい調べてみて，勉強になりました） https://t.co/d03B17THzG"
Miller-Rabin素数判定法 - Mister雑記
