AtCoder Beginner Contest 324 F : Beautiful Path

問題文

　https://atcoder.jp/contests/abc324/tasks/abc324_f

問題概要

　$N$ 頂点 $M $ 辺の有向グラフ $G = ( V, E )$ があり，$i$ 番目 ($0 \leq i < M $) の辺*1は頂点 $u_i$ から $v_i$ を結び，その「美しさ」は $b_i$ で「コスト」は $c_i $である．
　頂点 $0$ から頂点 $N - 1$ へのパス $P$ で，$P$ に含まれる辺の美しさの総和を，$P$ に含まれる辺のコストの総和で割った値が最大のものについて，その値はいくらか？

制約

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $0 \leq u_i, v_i < N$
• $1 \leq b_i, c_i \leq 10^4$
• 頂点 $0$ から頂点 $N - 1$ へのパスが存在する
• 入力される値は整数

解法

　まず記法についてですが，辺 $e \in E$ がパス $P$ に含まれることを $e \in P$ と書きます．また，辺 $e$ の美しさとコストをそれぞれ（記号を濫用気味ですが）それぞれ $b( e ), c( e )$ と書くことにします．
　では本題ですが，最大化しようとしている値は，パス $P$ を固定すると定義から
\begin{equation}
\frac { \sum\limits_{ e \in P } b( e ) }{ \sum\limits_{ e \in P } c( e ) }
\end{equation}
となります．
　ここでやや天啓ですが（，というより実は蟻本*2に載っていますが），

• 上記の値をある値 $x$ 以上にできるか？

という質問を考えます．ある $x$ で上記質問の答えが真であるとき，$x' \leq x$ なる任意の $x'$ についても答えは真です．つまり，単調性があるので，うまくやれば二分法が適用できそうです．
　では，答え $x$ を固定したときの判定問題はどのようにすれば解けるでしょうか？　上記の式を元に $x$ が満たすべき条件を立式して変形すると，
\begin{align}
\frac { \sum\limits_{ e \in P } b( e ) }{ \sum\limits_{ e \in P } c( e ) } \geq x \\
\frac { \sum\limits_{ e \in P } b( e ) }{ \sum\limits_{ e \in P } c( e ) } - x \geq 0 \\
\sum\limits_{ e \in P } b( e ) - x \sum\limits_{ e \in P } c( e ) \geq 0 \\
\sum\limits_{ e \in P } ( b( e ) - x c( e ) ) \geq 0
\end{align}
となって，通る辺 $e \in P$ 毎に $b( e ) - x c( e )$ を足し上げ，それが $0$ 以上になれば上記質問への答えが真であるということが分かります．最適なパス $P$ というのはこの和が最大になるようなパスなので，
\begin{equation}
\mathit{ dp }[u] = \text{ 頂点 $u$ を終点とするパスにおける上記値の最大値 }
\end{equation}
という DP をすれば求められます．
　あとは外側で $x$ についての二分法をすれば，問題を解くことができます．
　計算量についてですが，実数に関する二分法なので，反復回数は初期値とする下界と上界の差を一回のイテレーションで $\frac 1 2$ 倍にしていって，差が許容誤差内に収まる程度の回数にする必要があります．すぐに分かる下界は $0$ で，上界は（細かいところを吸収すると）$\Theta( N \max b ) $ です．なので反復回数としては対数をとって $\Theta( \log ( N \max b ) )$ 回程度やれば，誤差が十分小さくなります．その反復それぞれについて上記 DP をしますが，この DP は $\Theta( N + M )$ 時間で走るので，全体では $\Theta( \log ( N \max b ) ( N + M ) )$ 時間となります．

コード

constexpr auto INF = 2'000'000'000;

bool possible( const auto &G, const double T )
{
	const int N = SZ( G );

	VEC( double, dp, N, -INF );
	dp[0] = 0;
	REP( u, N )
	{
		FOR( e, G[u] )
		{
			const int v = get< 0 >( e );
			const int b = get< 1 >( e );
			const int c = get< 2 >( e );
			chmax( dp[v], dp[u] + b - T * c );
		}
	}

	return 0 <= dp[ N - 1 ];
}

int main()
{
	cin.tie( nullptr );
	ios::sync_with_stdio( false );
	cout << setprecision( 12 ) << fixed;

	IN( int, N, M );
	using Edge = tuple< int, int, int >;
	VEC( Edge, G, N, 0, Edge() );
	REP( M )
	{
		IN( int, u, v, b, c );
		--u, --v;
		G[u].EB( v, b, c );
	}

	double lb = 0, ub = INF;
	REP( 128 )
	{
		const double mid = ( lb + ub ) / 2;
		( possible( G, mid ) ? lb : ub ) = mid;
	}

	cout << lb << endl;

	return 0;
}

*1:宗教上の理由で全て $0$-indexed になっています．原文と違うので注意．

*2:秋葉拓哉, 岩田陽一, and 北川宜稔. プログラミングコンテストチャレンジブック: 問題解決のアルゴリズム活用力とコーディングテクニックを鍛える. マイナビ出版, 2012.