2020年2月28日グラフDAG,トポロジカルソート,BFS,DFS,グラフ,有向グラフ

トポロジカルソートとは、閉路の無い有向グラフ DAG について行うソートです。

左図のDAGを右図のように頂点を一列に並べて、全ての辺の向きが左から右になるようにすることを言います。

閉路のないDAG

2020年2月27日データ構造完全二分木,区間,モノイド,更新,RMQ,RUQ,データ構造,RAQ,二分探索,RSQ

セグメント木とは

セグメント木とは、完全二分木（全ての葉の深さが等しい木）によって実装された、区間を扱うのに適したデータ構造のことです。

区間に対する操作を対数時間 O(log n) で行えることが特徴で、競技プログラミング ...

2020年2月24日AtCoder二項係数,操作,数え上げ,500点,重複組合せ,剰余

問題概要

n 個の部屋に 1 ずつ人がいる。以下を k 回行ったとき、考えられる状態は何通りあるか \(10^9+7\) で割った余りで答えよ。

ある部屋 \(i\) にいた人が、\(i \neq j\) を満たす任意の部屋 \( ...

2020年2月24日数学bit演算,剰余,競プロ,べき乗,ダブリング,繰り返し二乗法,2進数

多くのプログラミング言語でサポートされてる \(x^n\) を計算する関数のアルゴリズムです。

Input : pow(2,4) (x=2, n=4)
Output : 16

べき乗は非常に大きな数値に ...

2020年2月22日動的計画法テーマ記事,競プロ,bit演算,動的計画法,bitDP,DP

競技プログラミングで良く使われる動的計画法の1種、「ビットDP」と呼ばれるものについてまとめました。

ビットDPとは

ビットDP(bit DP) とは、ビットで表現した集合を添え字に持つ動的計画法(DP)のことです。 ...

2020年2月20日AtCoder最大値,二分探索,最小値

問題概要

問題へのリンク

風船に 1 から N までの番号が付けられていて、風船 i (1≦i≦N) は競技開始時に高度 \(H_i\) のとこ ...

2020年2月20日競技プログラミングテーマ記事,競プロ

競技プログラミングの問題を解くためには２つのステップがあります。

問題で要求されていることを言い換える
知っているアルゴリズムやデータ構造を組み合わせて解く

必要な（知っておくべき）アルゴリズムやデータ構造は色 ...

2020年2月17日AtCoderK番目,2つの積,400点,二分探索

ARC037 億マス計算 の上位問題です。

問題概要

問題へのリンク

N個の整数 \(A_1, A_2, A_3, \cdots, A_n\) がある。
2つを選んでその積を \(\frac{N(N-1) ...

2020年2月17日AtCoderDP,500点,桁ごと,お釣り,硬貨

問題へのリンク

問題概要

\(1, 10, 10^2, 10^3, \dots, 10^{(10^{100})}\) の紙幣で金銭のやり取りをする。

N 円払う時、支払うのに使う紙幣の枚数と、お釣りでもらう紙幣の ...

2020年2月15日グラフDFS,グラフ,競プロ,関節点,切断点,橋,lowlink

無向連結グラフにおいて、「取り除いたときにグラフ全体が非連結になるような辺」を橋と言います。

※「連結」とは任意の2頂点間を行き来できることを言い、「非連結」は逆に行き来できない頂点があることを言います。（くわしくはグラフ ...