2023-06-10から1日間の記事一覧
AtCoder
AtCoder400点
ABC-D
緑色diff
BFS
パズル
文字列
最小回数・最小個数を求める
見積り大事
【問題集】DFS・BFSのステップアップ
操作
最短路問題
入力が定数個
【問題集】最短路問題
操作:circular_shift
最適化問題
操作:整数をreplaceしていく
最小回数を求めるには BFS!!(素振り) 問題へのリンク 問題概要 黒板に整数値 が書かれています。次のいずれかの操作を最小回数繰り返すことによって、整数値 の値を にしたいとします。 を 倍して にする を十進法表記したときに、末尾の値を先頭に持って…
AtCoder
AtCoder400点
茶色diff
ABC-D
最適解の数え上げ
最短路問題
【問題集】最短路問題
BFS
【問題集】DFS・BFSのステップアップ
グラフ
そのまま覚えたい典型問題
数え上げ問題
【問題集】グラフの入門
「最適解の個数」を求めるという超典型! 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられます。 頂点 から頂点 へと至る最短経路の本数を 1000000007 で割った余りを答えてください。 制約 解法 最短路を求めるだけならば、BFS を使うこ…
AtCoder
AtCoder500点
水色diff
ABC-F
BFS
グラフの辺数削減テク:スーパー頂点を用いてsparseに
グラフ
集合族に関する問題
値A[i]を頂点に持たせたグラフを考える
操作
最小回数・最小個数を求める
操作:2つのものを1つにマージ
典型要素を詰め合わせた教育的問題
【問題集】DFS・BFSのステップアップ
制約:複数系列の長さの合計が10^5以下
スーパー頂点を用意する
最適化問題
下手を打つと密なグラフになって TLE してしまう!! スーパーノードを作ることでグラフを sparse にするテク! 問題へのリンク 問題概要 以上 以下の整数値からなる 個の有限集合 が与えられる。 以下の操作を最小回数繰り返すことによって、「 と をともに…
AtCoder
ABC-Ex
橙色diff
Union-Find
木
差分更新
undoつきUnion-Find
データ構造
クエリ処理問題
クエリ:削除
二値パラメータ問題
種類数
高度典型
木の問題に対してパスの場合から考える
DFS
値A[i]を頂点に持たせたグラフを考える
各kに対して
解空間:O(2^N)通りの選択肢
最大スコア
AtCoder625点
最適化問題
undo 付き Union-Find! 問題へのリンク 問題概要 頂点数 の木が与えられる。各頂点には、数値 の書かれたボールと、数値 の書かれたボールがある。 各 に対して、次の問に答えよ。 パス - 上の各頂点から ボールを 1 個ずつ選んだときの ボールに書かれた数…