トヨタ自動車プログラミングコンテスト2024#2（AtCoder Beginner Contest 341）F,G問題メモ

トヨタ自動車プログラミングコンテスト2024#2（AtCoder Beginner Contest 341）

F - Breakdown

• $N$ 頂点 $M$ 辺の単純無向グラフ
• 頂点 $i$ には整数 $W_i$ が書かれていて、また、$A_i$ 個のコマが置かれている
• 以下の操作を繰り返す
  • 好きな頂点を選び（$x$ とする）、そこに置かれているコマを1つ取り除く
  • $x$ に隣接する頂点の集合 $S$ を好きなように選ぶ。ただし、選んだ頂点の $W_i$ の和が $W_x$ より小さくないといけない
    • $\sum_{y \in S} W_y \lt W_x$
  • $S$ に含まれる頂点にコマを1つずつ置く
• 最大何回操作をすることができるか
• $2 \le N \le 5000$
• $1 \le M \le 5000$
• $1 \le W_i \le 5000$
• $0 \le A_i \le 10^9$

1つのコマが、生涯（そのコマから派生した全てのコマがなくなるまで）で 何回分の操作に相当するか、というのは、そのコマがどこに置かれているかで一意に決まる。

• $DP[x]=$ 頂点 $x$ に置かれたコマ1つが、最大何回分の操作に相当するか

⑥←⑨→③→①
↓  ↓  ↓      W_i が 大→小 の方向にしかコマは流れないので、
③←④→②      辺は有効辺と見なす
    ↓
    ①

上記の①や②など、流出辺（自分より $W_i$ が小さい隣接頂点）がなければ、 そのコマを取り除いた後は新たなコマを置けないので、可能な操作は1回のみ。

⑨や④など流出辺がある場合は、「和が自身の $W_i$ を超えないように、隣接頂点から、1個あたりの操作回数が大きいものを選ぶ」ことになる。

これは、まさしくナップサック問題で、 ナップサックの容量を $W_i$、各隣接頂点 $j$ につき $W_j$ を重さ、$DP[j]$ を価値とした問題を解けばよい。

$W_i$ の小さい方からDPを埋めていけば、$W_i$ を求めるときには、必要な $DP[j]$ は埋まっている。

1回当たり $m$ 個の荷物で容量 $w$ のナップサック問題を解くとして、$O(mw)$、 これを各頂点に対して合計して、$O(M W_{max})$ となる。

Python3

G - Highest Ratio

• 長さ $N$ の数列 $A=(A_1,...,A_N)$
• $l=1,2,...,N$ について、以下を求めよ
  • $r$ を $l \le r \le N$ の範囲で自由に動かせるとき、区間 $(A_l,A_{l+1},...,A_r)$ の平均値として取り得る最大値
• $1 \le N \le 2 \times 10^5$
• $1 \le A_i \le 10^6$

区間の平均は、割る数が長さによって異なってくるため、$[l,r)$ の時の結果を $[l-1,r)$ や $[l,r+1)$ に活用しづらい。

平均が、「累積和の傾き」によって表現できることを利用する。

14 |             *          A = (   1, 1, 4, 5, 3)
   |
   |                  累積和C = (0, 1, 2, 6,11,14)
11 |          *
   |
   |
   |
   |
 6 |       *
   |
   |
   |
 2 |    *
 1 | *
   +---------------
     1  2  3  4  5

• $A[2:4]=(1,4,5)$ の平均: $\dfrac{C[4]-C[1]}{4-1}=\dfrac{11-1}{4-1}=3.333...$

傾きで考えると、上側凸包に含まれない点を考える必要がなくなる。

|                *
|             ,-'
|          ,-'
|       ,-' *         ← j は i より左の点を l とした時の r にはなり得ない
|     *'                 必ず i か k を r とした方が傾きが大きくなる
=
|
+-||----------------
      i     j    k 

$i$ の大きい方から凸包を構成していけば、$O(N)$ で求まる。

Python3