prime's diary

そすうの日々を垂れ流しちゃうやつだよ

ととりにゃあ あつめて早し 最上川 それにつけても 金の欲しさよ - あるいは、ととりにゃあの語感の良さについて 【ととりにゃあ Advent Calendar 2021 Day 19】

こんばんは、そすうぽよです。 この記事はととりにゃあ Advent Calendar 2021の19日目の記事です。 adventar.org 概要 まずは、こちらのツイートをご覧ください*1。 毎日懇親 pic.twitter.com/vQs05WMrZ3— 毎日進捗 (@totori_kpr) 2021年12月18日 2021年12月…

マナ回路設計と魔術アーキテクチャ 【存在しない技術 Advent Calendar 2021】

この記事は存在しない技術 Advent Calendar 2021 - Adventarの14日目の記事です。 この記事はあなたのお住まいの世界には存在しない技術をもとに記述されているため、あなたのお住いの世界ではご利用いただけません。 マナ回路前史 近代以前は、魔術を発動で…

『フカシギの数え方』の数え上げを、全探索のままGPGPUで高速化した 【KMCアドベントカレンダー 2021 4日目】

この記事はKMCアドベントカレンダー2021の4日目の記事です。 adventar.org 概要 元ネタ:『フカシギの数え方』 www.youtube.com 問題としてはN×Nマスのグリッド(頂点としては 頂点)を左上から右下まで移動する経路であって、同じところを二度通らないもの…

AtCoder Heuristic Contest 003で5位(2.921T点)を取りました

AtCoder Heuristic Contestは、最近始まったAtCoderの定期コンテストで、最適解を出すのが難しい問題に対し、出来るだけ良い解を作成するコンテストです。 1週間程度の長期コンテストと、数時間程度の短期コンテストが交互に行われます。 atcoder.jp 今回の…

AtCoder Heuristic Contest 001 解法メモ

最終スコア(システムテスト後)は980,823,067,375点で95位でした。 atcoder.jp 自明解の生成 広告の希望(x, y, r)に対して、長方形( (x, y), (x+1, y+1) )は解の条件を満たす スコア計算 解の条件を満たしているかを判定する 満たしていれば、各広告について…

AtCoder橙/Codeforces International Grandmasterになりました

この記事は色変記事アドベントカレンダー1日目の記事ではありません。 AtCoderで橙色、CodeforcesでInternational Grandmaster(IGM)になったので振り返り記事を書きます。 AtCoderのレーティング推移 Codeforcesのレーティング推移 まあ、Codeforcesの方はIG…

フラグメントシェーダを用いて、VRChatのワールドで計算機を作る 【KMCアドベントカレンダー 2日目】

この記事はKMCアドベントカレンダー 2日目の記事です adventar.org 概要 最近遊んでいるVRChatというゲームにはユーザーの作成したアバターやワールドをアップロードできる機能があります。さらに、アバターやワールドのバーテックスシェーダー*1/フラグメン…

競技プログラミングはISUCONの役に立つ 【ISUCON10予選参加記】

単なる普通のISUCON参加記です。 そんなに競技プログラミングの話はないので、そういう話を期待していた人はごめんなさい。 こういうのは忘れないうちに書かないと書けないがち。 isucon.net ISUCON10にチーム「:羽付きのお札:」で nana ( 久我山 菜々 (@non…

オンラインBrainf*ckインタプリタ・デバッガを作った【Brainf*ck Advent Calendar 2019とその他のAdCの17日目】

はじめに この記事はBrainf*ck Advent Calendar 17日目・KMC Advent Calendar 17日目・LeapMind Advent Calendar 17日目の記事です。 adventar.org adventar.org adventar.org 概要 難解プログラミング言語の一つであるBrainf*ckのオンラインデバッグ環境を…

いろいろなBrainf*ck処理系における値の0初期化、ムーブ、コピー、便利なイディオム 【Brainf*ck Advent Calendar 2019 5日目】

この記事はBrainf*ck Advent Calendar 2019 5日目の記事です。 adventar.org 4日目の記事はmatsu7874さんによる「RustでBrainfuckインタプリタを実装した話を書けるだろうか?」の予定です。 6日目の記事はあんでぃ@量産型テ徒???? /-500/さんによる unident…

メタプログラミング可能なBrainf*ck派生言語BFmeta 【Brainf*ck Advent Calendar 2019 3日目】

この記事はBrainf*ck Advent Calendar 2019 3日目の記事です。 adventar.org 2日目はみみねこさんによる mmnkblog.hatenablog.com でした。4日目はmatsu7874さんによる「RustでBrainfuckインタプリタを実装した話を書けるだろうか?」の予定です。 今回はBra…

「サイゼリヤで1000円あれば最大何kcal摂れるのか」を全探索で解いてみた

概要 qiita.com この記事や後述の先行研究に触発されて、「サイゼリヤで1000円あれば最大何kcal摂れるのか」を最も単純に全探索で解いてみました。 先行研究 先人たちがいろいろな方法で解決を試みています。 qiita.com qiita.com qiita.com qiita.com qiita…

LeapMind株式会社に入社しました

LeapMind株式会社に入社しました

PEZY-SC/SC2を使った話 【KMCアドベントカレンダー 2日目】

この記事はKMC Advent Calendar 2018 - Adventarの2日目の記事です。 adventar.org 概要 理研に設置されているスーパーコンピューター、菖蒲(Shoubu)・菖蒲SystemBでPEZY Computing社のPEZY-SC/SC2を使わせてもらいました。 性能とか使いやすさについて感想…

ビット演算マニアのためのAVX512入門 【KMCアドベントカレンダー 22日目】

この記事はKMCアドベントカレンダー22日目の記事です。 adventar.org この記事では全国一億三千万のビット演算マニアのために、AVX512命令セットからビット演算に使えそうなものを紹介します。 AVX512の基本 AVX512とは Advanced Vector Extensions(AVX)とい…

ICPC 2017 Tsukuba Asia Regional 参加記

2017/12/16-18に行われたICPC 2017 Tsukuba Asia RegionalにチームPrimeDragonとしてamano, nikuttoと参加してきました。 コンテスト前日まで 15日 生活リズム的に16日の朝早くから出られそうにないので徹夜することにした。Redbull飲んで徹夜する。 16日 徹…

オセロの着手可能位置生成 【ビット演算テクニック Advent Calendar 2016 23日目】

はじめに この記事はビット演算テクニック Advent Calendar 2016の23日目の記事です。 www.adventar.org オセロとビット演算 オセロは盤面サイズが8x8=64マスなので、64bit変数を2つ用意し、1つめを自分の石(あるいは黒石)の位置を、2つめを相手の石(ある…

GPGPUで爆速でオセロを解く 【KMC Advent Calendar 2016 19日目】

はじめに この記事はKMC Advent Calendar 2016の19日目の記事です。 www.adventar.org GPGPUとは GPGPU(General-purpose computing on graphics processing units; GPUによる汎用計算)とは、GPUの演算資源を画像処理以外の目的に応用する技術のことである…

Bit scan reverseをAVXで並列化する

Bit scan reverse (bsr) 00000001010100010100000100101101 <-clz->*<---bit scan reverse---> 1になっている最も高位のビットのインデックスを0-indexedで計算します。0に対する結果は未定義(不定)です。 似た処理にcount leading zero(clz)があり、こち…

pclmulqdqを用いたビット単位のunpack【ビット演算テクニック Advent Calendar 2016 11日目】

この記事はビット演算テクニック Advent Calendar 2016 www.adventar.org の11日目の記事です。 ビット単位のunpack C++の固定長ビット配列を扱うクラスstd::bitsetを例として解説します。 std::bitset<128> unpacklo(const std::bitset<128> &a, const std:…

Delta swapとその応用 【ビット演算テクニック Advent Calendar 2016 3日目】

この記事はビット演算テクニック Advent Calendar 2016 www.adventar.org の三日目の記事です。 ビット列の部分列を入れ替える操作を効率的に行えるDelta swapを紹介します。xorが好きなのでDelta swapも好きなテクニックの一つです。 行える操作 マスクとず…

ビット列による部分集合表現 【ビット演算テクニック Advent Calendar 2016 1日目】

はじめに この記事はビット演算テクニック Advent Calendar 2016 www.adventar.org の1日目の記事です。 この記事ではビット演算を使って有限集合の部分集合を表現、操作するテクニックを紹介します。 本文中で説明を省略した部分については、詳しい説明のあ…

CUDAで再帰するとき

CUDAではDynamic Parallelism(GPU側から新たなカーネルを起動する)以外に普通の(シリアル実行の)再帰が可能です(Compute Capability 2.0以上)。 しかし、再帰的に関数を呼び出す場合、必要なスタックサイズが静的に割り出せないことがあり、このときはデ…

コミックマーケット89記念!ANSI C89コンパイラを作る【KMCアドベントカレンダー12日目】

この記事はKMC Advent Calendar 2015 - Adventar12日目の記事です。 宣伝 サークル「京大マイコンクラブ」は、コミックマーケット89で「木曜日 東地区 "モ" 42b」に配置されました! コミケWebカタログにてサークル情報公開中です https://t.co/BtKSerlV6R #…

高速文字列処理ライブラリを作った

この記事はポエムアドベントカレンダー4日目の記事です。 www.adventar.org 大量の文字列データを扱うことの多くなった現代において、文字列処理ライブラリの高速化は重要である。 しかしながら、個人レベルで汎用的かつ高速な文字列処理ライブラリを作成す…

RubyからGoの関数をつかわなくても再帰をやめなくてもアルゴリズムを改善する→はやい

qiita.com mattn.kaoriya.net という記事を読んだのでアルゴリズムを改善して速くしました。 いわゆる行列累乗のテクニックを使うと(乗算部分を除けば)N番目のフィボナッチ数はで求まります。 実際にはフィボナッチ数は指数的に増大するので乗算にかかる時…

【failに】ISUCON5の決勝に出たけど記録を残せなかった【人権はない】

お金が欲しいので(直球)、優勝賞金100万円のISUCONの決勝に出ました。予選については primenumber.hatenadiary.jp を参照。 当日起きれるか不安だったので前日入りしてカプセルホテルに泊まった。 人生初のカプセルホテルだったが、あまり寝られなかった。…

ISUCON5の予選に出て学生枠1位で通過した(チーム名: 古典論理の犬)

お金が欲しいので(直球)、優勝賞金100万円のISUCONの予選に参加して、13609点、二日目全体で11位(?)学生枠1位で通過した(学生枠で登録した中では一般枠で通過したチーム学生自治についで2位)。 isucon.net チーム チーム名: 古典論理の犬 チームメン…

std::atan2

第一引数はy座標、第二引数はx座標

gccでSIMD命令等のIntrinsicsを使う時のメモ

やりたいこと Intel Intrinsics Guideに載っている組み込み関数を使いたい 具体的には今作っているオセロAIの高速化のため 調べた環境 GCC 5.1 (Arch Linux) 使い方と注意 だいたいの(実際の実行環境で使用出来る)命令の組み込み関数は各関数で指定されたヘ…