はまやんはまやんはまやん

hamayanhamayan's blog

2017-05-21から1日間の記事一覧

競技プログラミングにおける平衡二分木問題まとめ

平衡二分木 平衡二分木はただ順番が正しく守られている二分木 順番ってなんだって感じですが、「数列としての順番」「値の大小としての順番」のどちらでもよくて、このへんはinsertするときに自分でちゃんと合うようにやる 実装が色々あるが、求められるクエ…

競技プログラミングにおける分割統治法問題まとめ

分割統治法 「列の分割統治法」、「木の分割統治法」、「平面の分割統治法」 色んな分割統治法があるが、大体空間サイズが半分になってlogNくらいで解けるようになる 再帰的な定義がなされているやつを再帰的に処理して解決する問題もある 列の分割統治法は…

FourLamps [TopCoderOpen 2017 Round2A Div1 Hard]

https://community.topcoder.com/stat?c=problem_statement&pm=14597&rd=16929 問題概要 N個のランプがあり、on/offのどちらかの状態をとる。 最初はinitの状態になっている。 ここから、K回以下の操作を繰り返す時に最終的にランプが取りうる状態数は何通り…

DistanceZeroAndOne [TopCoderOpen 2017 Round2A Div1 Med]

https://community.topcoder.com/stat?c=problem_statement&pm=14596 問題概要 N頂点の連結な無向グラフがある。 これについて、頂点0から各頂点への距離dist0と頂点1から各頂点への距離dist1が分かっている。 2つの距離が満たされる無向グラフがあれば復元…

FoxAndCake2 [TopCoderOpen 2017 Round2A Div1 Easy]

https://community.topcoder.com/stat?c=problem_statement&pm=14609&rd=16929 問題概要 チェリーがC個、いちごがS個ある。 これを以下のルールでグルーピングする。 全てのチェリーといちごが何処かのグループに入る 何グループに分けてもいい 各グループ1…

競技プログラミングにおける中国剰余定理問題まとめ

中国剰余定理 中国風剰余問題、中国人剰余問題、CRT : Chinese Remainder Theorem 表記ゆらぎがむっちゃあるのでCRTで統一した方がいいんじゃないかと思ってる 解説 解ける問題 ある数m1,m2,...,mnとある数a1,a2,...,anがあり、 x ≡ a1 (mod m1) x ≡ a2 (mod…

競技プログラミングにおける永続データ構造問題まとめ

永続データ構造 persistent data structures 解説 色々ある「永続配列」「永続セグメントツリー」「永続Union-Find」「永続木」「永続平衡二分木」「永続WaveletMatrix」参考 部分永続。最新版のみ変更可能、Undoができる機構がある。履歴は一直線。 完全永…