単一始点最短経路問題で、すべての頂点に最短で到達するのに必要な辺だけを選ぶと木になることが知られている(最短経路木)。 なので、この問題では最短経路木を列挙すればいいことがわかる。根でない頂点vに最短距離で到達した時、直前の頂点をuとする。d(x)…

f(x) を「中央値をxとする部分文字列の数」とする。f(m)が解。 とおくと を得る。 あとは、g(y)を求めるだけ。g(y)の値は、中央値がy以上の部分文字列の数を表す。 部分文字列の中央値がy以上である必要十分条件は (y以上の値の数)>=(y未満の値の数) とわか…

数列なので中央値mはちょうど1つだけある。mの位置に注目すると、条件を満たす部分文字列は、mから左へ0以上、右へ0以上の長さだけ伸ばしたものに限られる。 部分文字列がmの左側へl, 右側へrだけ伸ばしたものであるとする。また、m以外の値はmとの大小関係…

ある非負整数が3の倍数かどうかは、各桁の値の和が3の倍数かどうかを調べればいい。なので dp[i][j] := 「もとの数字の上位i桁まで確定して、今作っている数の桁の和を3で割ったあまりがjであるときの最大の仕切りの数」 のようなDPを解く。 int dp[200005][…