問題概要 幅Dの川がある。途中には大きな石と小さな石がある。小さな石は1回乗ると壊れる。意志を中継して川を往復したい。利用する石の間隔の最大値の最小値を求める問題。 解法 二分探索+最大流。小さい石は対応する頂点に容量制限を付け加える。INFをあま…

問題概要 文字列S,T(長さ10^5以下)が与えられる。number {(i,j,k) | k>=K,S[i,k]=T[j,k]}を求める問題。 解法 f(X)をnumber {(i,j,k) | k>=K, i!=j, X[i,k]=X[j,k]}とする。このときf(S$T)-f(S)-f(T)を返せば良い。なのでf(X)について考える。 f(X)はLCPから…