問題atcoder.jp解法問題の言い換え答えで二分探索することを考えると、頂点 \(1\) から頂点 \(N\) への最短距離を \(d\) 以上にする場合に重みを変更する辺の本数の最小値を求めることになる。\(k\) 値 燃やす埋める\(d=1\) の場合頂点 \(1\) からの最短距離が \(0\) である頂点集合と \(1\) である頂点集合に分割し、異なる集合に属する頂点を結ぶ辺の本数を最小化する問題に帰着できる。これは最小カット問題そのものである。燃やす埋める問題は最小カット問題に帰着できるが、逆に最小カット問題を燃やす埋める問題に言い換えることを考える。頂点 \(1\) の値は …
問題文 https://atcoder.jp/contests/abc397/tasks/abc397_e 問題概要 正整数 $n, k$ と $nk$ 頂点の木グラフ $G = ( V, E )$ が与えられる．$G$ を互いに共通部分をもたない長さ $k$ のパス（パスの長さは含まれる頂点数で定義）に分解できるか？（厳密な問題定義は原文参照） 制約 $1 \leq n, k$ $nk \leq 2 \times 10^5$
問題文 https://atcoder.jp/contests/abc397/tasks/abc397_d 問題概要 正整数 $n$ が与えられる．正整数の組 $( x, y )$ であって，$x^3 - y^3 = n$ であるようなものを一つ報告せよ．存在しない場合はその旨を報告せよ． 制約 $1 \leq n \leq 10^{ 18 }$
