2019-01-13から1日間の記事一覧
DFS
連結成分
二次元グリッド
パリティ
Union-Find
BFS
AtCoder300点
AtCoder
水色diff
ABC-like
連結成分ごとに分解して考える
【問題集】DFS・BFSのステップアップ
二部グラフ
二部グラフであることを活かした変数変換
市松模様・塗り分け
解空間:O(N^2)通りの選択肢
DP とかメモ化再帰とか考え出すとドツボにはまる...素直な考察が大事だね。 問題へのリンク 問題概要 のグリッドが与えられる。各マスは白か黒で塗られている。「黒」マスと「白」マスのペアであって、 黒マスから出発して、隣接するマスを辿っていくことで…
連結性に着目する
累積和
二分探索
しゃくとり法
最適化テク:端点のみを考える
数列
AtCoder500点
AtCoder
二分探索:lower_bound
青色diff
ABC-like
最適化テク:最適解の形を考える
K飛ばしで累積和
累積和の亜種
累積和テク:累積和や累積結果を前処理しておく
ができた。本番中に解き切りたかった 問題へのリンク 問題概要 個の整数 がある。整数 を 1 つ固定したとき、先手と後手は以下のようにしてゲームを進める: 先手は現在残っている整数のうち、最大のものを取って足す 後手は現在残っている整数のうち、 に最…
DP
二乗の木DP
木
木DP
DP値を利用して状態復元
ナップサックDP
木DPのノード更新にDP
グラフ
AtCoder600点
AtCoder
ABC-like
橙色diff
【問題集】木DPのステップアップ
二乗の木DPの問題にようやく出会えました! 問題へのリンク 問題概要 頂点のツリーがあって、各頂点には値 が割り振られている。今ツリーのエッジを何本か取り除いて何個かの連結成分に分けたとき 連結成分内に含まれる全ノードの頂点の重みの和が負の値 連…