トヨタ自動車プログラミングコンテスト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

n, m = map(int, input().split())
links = [set() for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add(v)
    links[v].add(u)

www = list(map(int, input().split()))
aaa = list(map(int, input().split()))

bbb = [(w, i) for i, w in enumerate(www)]
bbb.sort()
value = [1] * n
ans = 0
for wu, u in bbb:
    dp = [0] * wu
    for v in links[u]:
        wv = www[v]
        if wu <= wv:
            continue
        vv = value[v]
        for i in range(wu - wv - 1, -1, -1):
            dp[i + wv] = max(dp[i + wv], dp[i] + vv)
    value[u] = max(dp) + 1
    ans += aaa[u] * value[u]

print(ans)

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

from itertools import accumulate

n = int(input())
aaa = list(map(int, input().split()))

acc = [0] + list(accumulate(aaa))
ans = [0] * n
stack = [n]

for i in range(n - 1, -1, -1):
    a = acc[i]
    while len(stack) >= 2:
        j = stack[-1]
        k = stack[-2]
        b = acc[j]
        c = acc[k]
        ave1 = (b - a) / (j - i)
        ave2 = (c - a) / (k - i)
        if ave1 <= ave2:
            stack.pop()
        else:
            break
    j = stack[-1]
    b = acc[j]
    ave = (b - a) / (j - i)
    ans[i] = ave
    stack.append(i)

print('\n'.join(map(str, ans)))