電波ビーチ

☆(ゝω・)v

Algorithm

「レッドコーダーが教える、競プロ・AtCoder上達のガイドライン」中級編の100問を解く vol2 No.18~No.33

E869120さんの超絶まとめQiitaが話題になっていました。 qiita.com 全三部作で、初級編は茶色、中級編は水色、上級編は黄色になるためのアルゴリズムやデータ構造のリンク、勉強法などがまとめられています。このうち中級編には「分野別 初中級者が解くべき…

「レッドコーダーが教える、競プロ・AtCoder上達のガイドライン」中級編の100問を解く vol1 ~No.17

E869120さんの超絶まとめQiitaが話題になっていました。 qiita.com 全三部作で、初級編は茶色、中級編は水色、上級編は黄色になるためのアルゴリズムやデータ構造のリンク、勉強法などがまとめられています。このうち中級編には「分野別 初中級者が解くべき…

ジェネレータで再帰的に組み合わせを返す

たとえば0 1からなるビット列の配列がほしいみたいなとき。組み合わせが少なければ愚直にやってもいいが、多いとき、ビット演算でやると文字列の扱いになって変換処理が時間的にボトルネックになり、リストで管理するとメモリ的にボトルネックになる。 ジェ…

ABC 028を解いた

tomerun.github.io これにあるやつで難易度低そうなABCの問題セットから解いていくシリーズ。界隈ではABC042以降を解けという声がありますが果敢に無視します A - テスト評価 数値が与えられるので値で分岐して答える n = gets.to_i if n<=59 puts "Bad" els…

重みつきUnion-Find木を解説

これを解こうとしてできなかったのでまとめた。 judge.u-aizu.ac.jp 重み付きUnion-Find 英語名はよくわかんなくてweighted union-find とか weighted union heuristic、weighted disjoint set dataみたいに言われてるっぽい。Union-Find木に「あるノードか…

AOJ ALDS1_6_C Quick Sort

ソートアルゴリズムの実装自体やったことないぜ!!!!!!!!!メリークリスマスイヴ!!!!!!!!! n 枚のカードの列を整列します。1枚のカードは絵柄(S, H, C, またはD)と数字のペアで構成されています。これらを以下の疑似コードに基づくクイック…

Goで順列を辞書順で

スライスのポインタで渡すところとスライスのコピーとスライスの任意のインデックスの要素を消すっていう実装が頭まわりませんでした… 実装 package main import "fmt" func main(){ test := []int{1, 2, 3, 4} perms := permuration(test, 3) fmt.Println("…

Atcoder Beginner SelectionをGoで解いた

qiita.com これですね。Qiitaのほうでは各言語で解いてみた記事がどんどん上がっています(さすがにもう勢いは終息した) 当然Goで解いた記事なんてとっくの昔に出ているのでn番煎じなんですがたまにはコードかかんと、ということで。n番煎じなのでとくにこ…

AOJ ALDS1_4 B BinarySearch

みんなだいすきバイナリサーチです。何度メモっても忘れる。 概要 二分探索 | アルゴリズムとデータ構造 | Aizu Online Judge ソート済み配列があったときそこにxが含まれているかどうか以外に、「xを最初に越える最小のy」とか「xを下回る最大のy」みたいな…

ポラード・ロー法で素因数分解

素因数分解をするアルゴリズムがあるようです。 ポラード・ロー素因数分解法 - Wikipedia こちらのqiita記事でも言及されております。フロイドの循環検出法に基づく素因数発見のための乱択式アルゴリズムとかいう意味不明な単語が並びますが、いくら読んでも…

最小公倍数を求めるやつ

ある2つの数x,yの最小公倍数は、それらをかけ合わせたものをそれらの最大公約数で割るとイケます。すなわち、x,yの最大公約数、最小公倍数をそれぞれgcd(x, y), lcm(x, y)とすると、 x*y = gcd(x, y) * lcm(x, y) が成り立ちます。 最大公約数はこの回でやっ…

最大公約数をユークリッドの互除法で求める

超有名どころ。最古のアルゴリズムらしいです。 ユークリッドの互除法 - Wikipedia 書いてあるとおりに素直に実装すればいいだけですね。 def gcd(x, y): if x

0-1ナップザック問題をメモ化再帰で思い出す

前回の続きというか書き忘れ or3.hatenablog.com DPは配列でやるのがよく入門でみかけるんだけど、最初に学習するときって順序的にはDFSからのメモ化再帰からのDPっていう感じのほうが理に適っている感じがある。なのでメモ化再帰バージョンを。 # 典型的ナ…

0-1ナップザック問題を思い出す

プログラマになりたいくせにしばらくプログラミングから離れていたらものの見事に忘れ果てていたので、基本に立ち返ることにした。まずはナップザック問題から。 0-1ナップザック問題 n, maxw = list(map(int, input().split())) v_lis, w_lis = [], [] # in…