コンテストでの時間切れや解けなかった過去問を振り返って供養していく 2/22: AtCoder Grand Contest 014 D - Black and White Tree 供養 問題 Difficulty: 2293 (記事作成時点) 解法 木 が完全マッチング可能な場合かつその限りにおいて後手が勝つ ある完全…

概要 あるパラメータをとったときの状態が2値で表せる 更新処理が比較的単純な論理演算で表せる 連続する複数の値を同時に更新できる 上記のようなDPをするときに、いくつかのbitをまとめて数値として計算してしまうことで高速化する、いわゆる定数倍高速化…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 2/15: AtCoder Regular Contest 090 E - Avoiding Collision 供養 問題 Difficulty: 2282 (記事作成時点) 解法 - 間の最短距離を取るパス全ての組み合わせから高橋君と青木君が遭遇する…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 2/8: AtCoder Regular Contest 025 C - ウサギとカメ 供養 問題 Difficulty: 2258(estimated) (記事作成時点) 解法 について、 を始点とする各点への最短路を探索し、 である各点への最…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 2/1: AtCoder Regular Contest 074 F - Lotus Leaves 供養 問題 Difficulty: 2205 (記事作成時点) 解法 最小カットに帰着する方法と、 間の局所点連結度を求める方法がある 解法1: 最小…

概要 各辺に容量を持ち、始点と終点のあるグラフが与えられたとき、始点から終点までの最大フローを求める 最大フロー最小カット定理により、グラフの最小カットを求めることとも同値 グラフ中の辺 の容量が で、 から に だけフローが流れているとき、 に …