algorithm

C++algorithmbinary_search2021年6月16日

二分探索の応用

皆さんご存知の二分探索。この応用について今回は書いていきたいと思う。二分探索の一般化二分探索とはつまり、範囲を特定することである。例億マス計算そこで今回は二分探索を使う下記問題を解いていく C - 億マス計算AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.AtCoderAtCoder Inc. [https://atcoder.jp/contests/arc037/tasks/arc037_c] 愚直に2重ループで解くと O(N²)になるため、時間が足りなくなる blog-binary_search_2blog-binary_search_2. GitHub Gist: instantly share code, notes, and snippets.Gist262588213843476 [https://gist.github.com/kooooohe/8cc33e0f1e

algorithmBITGo2021年4月23日

Signed bitとBITとGoと

目次 * きっかけ * Two’s complement(2の補数) * 累積和 * BIT(binary indexed tree) * 転倒数きっかけ先日友人から下記の結果についての質問がきた。 package main import ( "fmt" ) func main() { const a = ^0 fmt.Println(a) } 皆さんも予想してみてほしい。実行は↓から The Go Playground [https://play.golang.org/p/qpWRExXsJ8E] ^0 はNOTでbit反転なのだが、値はintegerのmax値になることなく `-1` となる。これは、ご存知Signed Integer で全bitが1の場合はTwo’s complement(2の補数)となり `-1`が出力される。そして、Goのconstは数値が右辺に来た場合はSigned Integer Typeとデフォルトで解釈する。では uintのmaxの値をbit反転で取りたい場合はというと package

DPVue.jsalgorithm2021年3月18日

区間DPのテーブルを可視化してわかりやすくしてみた

前回 DP(Dynamic Programming)をVue3.0 With TS & PrimeVUEで視覚化するやることMediumkooooohe [https://medium.com/@1211lta/dp-dynamic-programming-%E3%82%92vue3-0-with-ts-primevue%E3%81%A7%E8%A6%96%E8%A6%9A%E5%8C%96%E3%81%99%E3%82%8B-2c84c749f340] 区間DP DP(動的計画法)の中で区間を状態として表すものをいう。 [a,b,c,d]とあった際に、 * a→b cost 3 * a→c cost 10 * b→d cost 2 etc といったような条件が有り、適切に区切ったさいの最小、最大のコストを取るか見積もる際などに使われる ※なので今回の区切る個数は添字0~4の5つとなる dp[i][j] = (i,j] の最適解となるように計算していくイメージ図参考問題(応用) https://judge.u-aizu.ac.jp/onlinejudge/d

DPVuealgorithm2020年12月7日

DP(Dynamic Programming)をVue3.0 With TS & PrimeVUEで視覚化する

やること典型的な動的計画法（Dynamic Programming)を使うナップサック問題をVue3.0の学習がてら視覚化していく技術 * Vue3.0 * TypeScript * PrimeVUE PrimeVUE [https://primefaces.org/primevue/showcase/#/] PrimeVUEはVue3.0に対応しており、良さげだったので使用。あとせっかくなのでVueのCompositon APIで書いてみた。余談： Vue3.0のビルドが早くて驚いた。また、Compositon APIを使うことにより型が厳密に定義できとても良いなと感じた。ナップサック問題ナップサック問題 - Wikipediaウィキメディア財団Contributors to Wikimedia projects [https://ja.wikipedia.org/wiki/%E3%83%8A%E3%83%83%E3%83%97%E3%82%B5%E3%83%83%E3%82%AF%E5%95%8F%E9%A1%8C#:~:text=%E3%83%

fibonacci numberGogolang2020年8月23日

【高速】フィボナッチ数列をビネの公式を使いGoで実装する

結論 O(log (n))となり 1000項目めを求めるには0.000199s 10000項目めは0.000405sで求められました。完成品 https://github.com/kooooohe/fibonacci/blob/master/main.g [https://github.com/kooooohe/fibonacci/blob/master/main.go]o 通常の再帰を使った簡単な解き方 fib_blog_1.goGitHub Gist: instantly share code, notes, and snippets.Gist 262588213843476 [https://gist.github.com/kooooohe/17818f61bcfe287eb2709466eaccbf7f]func fib(num int) int { if num <= 1 { return num } return fib(num-2) + fib(num-1) } これだとO(2^n)となるためかなり遅い。 ※メモ化については今回は割愛