C++

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