2019-12-01から1ヶ月間の記事一覧
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 12/28: AtCoder Beginner Contest 147 E - Balanced Path 供養 問題 Difficulty: 1656 (2019/12/28現在) 解法 各マス について とする マス の時点で偏り のパスを作れるか、というBool…
概要 組合せ数 の素数 による剰余を求める なので、それぞれの による剰余を求めればよい と帰納的に求めていくことで を求めることができる フェルマーの小定理より なので、両辺を で割ると が言える であることから残りは帰納的に求められる もしくは、 …
概要 要素の更新がありうる数列について、任意区間におけるあらかじめ定義した演算が高速にできる 最大値/最小値 一定値以上/以下の要素数 区間和 数列の各要素が葉となるような木構造をとる 木を構成する各nodeは自身の子node(葉の場合は自分自身)が表現…
概要 グラフの連結成分について調べるために使用する Union()関数とFind()関数からなる 連結成分同士の結合をUnion()関数で実施する 同じ連結成分に属する頂点はFind()関数で同じ代表点が返ってくる Find()関数で経路圧縮すると、ならし計算量がAckerman関数…
概要 通常のキューは最初にPushしたアイテムを最初にPopする(FIFO) 優先度付きキューの場合、あらかじめ指定した任意の優先度に基づく順番でPopさせることができる 優先度はキューにPushされる任意のアイテム2つについて、その二者間に順序付けができるもの…