naoya_t@hatenablog

いわゆるチラシノウラであります

Algorithm

拡張ユークリッド互除法の話

先日の連分数の計算と拡張ユークリッド互除法って少し似てるなと思ったというメモ。(連分数の計算で次の項を求める時にやっている操作ってユークリッドの互除法そのものだし当然か)拡張ユークリッド互除法というのは、 を満たす を求める方法。 を で割れば…

Crayfish Scrivener (IOI 2012, day 1)

6月は永続データ構造強化月間(そういうことにしました)、ということで qnighy先生の Re永続データ構造が分からない人のためのスライド で紹介されていた、IOI 2012の"Crayfish Scrivener"を解いてみたメモ。

連分数 (continued fraction)

連分数 - WipikediaこないだのJune Long ChallengeのEuler Sumを考えてる時に Mark Jason Dominus氏のスライド Arithmetic with Continued Fractions を読んだ時のメモ。連分数とかいじるのって多分昔SICPを読んだ時以来。

小さい数n(100万までとか)の素因数分解

CodeChefのフォーラムで June Challenge 2017の問題 Chef and Prime Queries (PRMQ) の解法を読んでいて discuss.codechef.com素因数分解をするのに This can be done by creating a Smallest Prime Factor array in the sieve function itself. とあって。…

2-SATと強連結成分分解

ふと2-SATの事が気になって、復習がてらPractice RoomでSRM464のDiv1 Medium問題を開いてみた。(ちなみにSRM464には出場している)SAT (充足可能性問題, SATisfiability problem) についてはここの読者の皆さんはご存知とは思います。NP完全問題でおなじみ…

Courseraレポート(〜9/23)

前回までのあらすじ(〜9/8)9/18からScalaで学ぶ関数型プログラミングのクラスが始まったけど、参加するかは未定。 参加中のクラス Quantum Mechanics and Quantum Computation (Umesh Vazirani, UCB) - 7/17開講; 全課程(8週)終了 Week 8 (最終週) Grover…

Courseraレポート(〜9/3)

前回までのあらすじ(〜8/26)現在、量子力学&量子計算のクラス(Umesh Vazirani先生)と、8/26に参戦したアルゴリズムのクラス(Robert Sedgewick先生+Kevin Wayne先生)を受講中。量子計算の方がメイン。 Quantum Mechanics and Quantum Computation (Um…

アルゴリズム勉強会に参加してきた

nokunoさん来るかな?と思って参加登録したアルゴリズム勉強会@芝浦四丁目 http://partake.in/events/b913f41d-5ec6-4310-89e4-342820616641 @viperlike のくのにうむ摂取しに行きましょうか!— naoya tさん (@naoya_t) 8月 24, 2012 「アルゴリズムイント…

GCD - cafelierさんのコードから

cafelierさんの500のコード見てたら LL gcd(LL a, LL b) { while(a) swap(a, b%=a); return b; } あ、そうか。swapってそう使えるのか。短くていいな。

Graphvizで描いたグラフをGIFアニメにする - 赤黒木を例に

皆さんの脳内でも赤西仁×黒木メイサが2-3-4木でいうところの3-節として内部表現されていることと存じますが、今日は赤黒木を題材にGraphvizで描いたグラフをGIFアニメにしてみたいと思います。というか単なる Graphviz入門です。いきなりGraphvizの本家ドキ…

三分探索と黄金分割探索

はい、毎度おなじみのグラフ描きたいだけのエントリですw今回のお題は「三分探索(ternary search)」。二分探索(binary search)は割とおなじみかと思うのですが、二分探索が単調増加(減少)関数fについてf(x)=kとなるxを求めるのに対し、三分探索(とか黄…