ARMERIA

Rubyと競技プログラミングの話　AtCoderやCodeforcesの問題解説記事が多め。

Educational Codeforces Round 89 F. Jog Around The Graph

Codeforces プログラミング 競技プログラミング

Problem - F - Codeforces

問題概要

n 頂点 m 辺の重み付き無向グラフが与えられる。グラフは単純かつ連結である。

正整数 x について f(x) を「頂点 1 から始まってちょうど x 回移動する経路の、通った辺の重み合計の最大値」と定める。この経路では同じ辺や頂点を複数回通っても良い。

与えられた正整数 q に対して、 \sum_{x=1}^{q} f(x) を \bmod 10^{9}+7 で求めよ。

制約

  • 2 \le n \le 2000
  • n-1 \le m \le 2000
  • m \le q \le 10^{9}
  • 各辺の重み w_{i} について 1 \le w_{i} \le 10^{6}
  • グラフは単純かつ連結

解法

最適経路についての考察

考えるべき経路は以下のようなものに限定することができます。

  1. 頂点 1 からスタートして、通る頂点・辺が重複することなく、ある頂点 v に移動する。
  2. その後、 v に接続しているある辺を往復し続ける。

これは以下のように証明できます。任意の経路について、その経路で最も重みが大きい辺に注目します。その辺に到達する前のサイクルを排除して、到達した後は元の経路と同じ合計ステップ数になるまでその辺を往復し続けるような新しい経路を考えます。これは上記の条件を満たし、重み合計が元の経路のもの以上になります。よって上記の条件を満たすものだけを考えれば十分であることが示されます。

f:id:betrue12:20200612144155p:plain

通る頂点・辺が重複しないということは、往復パートに入るまでに通る辺の本数は m 本以下です。よってまずは x \le m の範囲で以下のDPを回します。

  • dp\lbrack x\rbrack\lbrack v\rbrack = 頂点 1 からスタートして辺を x 回移動して頂点 v にいるような経路の、重み合計の最大値

このDPの計算量は O(nm+m^{2}) であり、これで f(1), ..., f(m) は求められます。あとは往復パートです。

このDPの dp\lbrack m\rbrack\lbrack v\rbrack から、各辺の重みについて「 m+1 ステップ目以降で重み w_{i} の辺を往復し続ける場合、それまでの m ステップで得られる利得の最大値は b_{i} である」という情報が得られます。

つまりやるべきことは、 f(x) = \max_{i} \left(w_{i}(x-m) + b_{i}\right) を x=m+1, ..., q について合計することです。これはCHT(Convex-Hull Trick)が使える形になっています。

CHTの活用

まずは先ほどの直線群をCHTに掛けて「要らない直線」を除外します。そうすると各直線が最大値を実現するような x の範囲は、傾きが小さいものから順に並ぶ区間になります。

q が大きいので全ての x を試すことはできません。なので最大値を実現する直線が切り替わる場所を二分探索で求めることにします。傾きが小さい順に見ていけば左端は分かるので、「今見ている直線が最大値を実現するか」を判定基準として右端を二分探索すれば良いです。

1つの直線が最大値を取るような区間において f(x) は等差数列になるので、両端が分かれば等差数列の和の公式で計算できます。

m 個の境界を探すのに1回あたり O(\log q) かかるので、後半パートの計算量は O(m\log q) になります。

CHTなしでも間に合う

CHTを使う方法のメリットは、上記の二分探索において「今注目している直線が、ある x に対して最大値を実現するか？」を効率的に判定できることです。ただし今回は直線の数が高々 m 本であり m \le 2000 なので、CHTを使わずに毎回全部の直線を計算しても良いです。

※ただ「各直線が最大値を実現するような x の範囲は、傾きが小さいほうから順に並ぶ区間になる」という性質は変わらず使うので、CHTの考え方は必要になります。

後半パートの計算量が O(m^{2}\log q) になりますが、これでも間に合います。

ACコード

Submission #83440717 - Codeforces