考察過程

  • 問題設定が簡潔なのに複雑だな
  • $\sum A_i = \sum B_i$ なので $A_1$ だけ数えて十分
  • $N \le 37$ って何？
  • $A_i, B_i \le 10^4$ なのも小さいね
  • 制約が半分全列挙してくださいって言ってる気がする。ふたつに分けた間の移動量とかを見る？
  • $A_1$ として有り得る値の集合は区間ですか？
  • $N = 2$ や $N = 3$ の場合の答えは何ですか？
  • $N = 2$ なら $A_1 = B_2$
  • $A_i, B_i$ は交換してよい。よって $\sum _ {i \ge 2} A_i \ge \sum _ {i \ge 2} B_i$ を仮定してよい
  • $N = 3$ なら $0 \le A_1 \le B_2 + B_3$ に見える
  • 嘘っぽい $A_2 = B_2 = 1$ かつ $A_3 = B_3 = 100$ とか
  • $A_1$ が区間になるのは正しそうな雰囲気ある
  • $A_1$ の最大値は明らかに $\sum _ {i \ge 2} B_i$ である
  • $A_1$ の最小値を考えよう。$A_1 = 0$ にできるか？
  • $A_i$ が一番大きいやつからぐるぐるループさせるように使ってみるのがよさそう (未証明)
  • 一番大きいやつから始める必要ある？ 複数あると面倒だし
  • (ここまで20分)
  • 最小値と最大値が出れば間は繋げられるのは証明できる。辺 $A_1 - B_1$ を含む閉路をひとつとって逆流させる感じでやる
  • 最小値が分からない。フローを張ればできるが、張りたくないので……
  • 「お前は地頭ないんだから道具に頼れや」って聞こえてきたので張ります
  • サンプルは通ったのに WA です。絶望
  • (ここまで31分)
  • ここまでの議論でなにか嘘はありますか？ すべて証明付いてるはず
  • 実装ミスでした。AC
  • (ここまで36分)

解法

  1. $A_1$ が定まれば $B_1$ は一意なので $A_1$ だけ数えればよい。
  2. 可能な $A_1$ の集合は区間になる。これは $A_1$ が最小の状態からすこしずつ変化させていけるため。
  3. $A_1$ の最大値は明らか。
  4. $A_1$ の最小値は自明でないが、フローを流せばよい。

Dinic で $O(EV^2) = O(N^4)$。

メモ

  • 想定解はフロー流してない
  • editorial のこれは自明ですか？ 必要性は明らかだけど十分性の証明は必要だと思うのですが

    A1≥0, B1≥0 です。 駅 i で入った人は駅 i 以外のどこかで出るはずなので Ai≤(B1+⋯+BN)−Bi です。 入った人数と出た人数は同じはずなので A1+⋯+AN=B1+⋯+BN です。 これらの条件を満たす (A1,B1) はすべてありえます。

リンク