第六回アルゴリズム実技検定 (バーチャル参加)

177:09 で完走．自己最速なので嬉しい．

f:id:suisen_kyopro:20210425084931p:plain

A - POSTal Code

実装 (Python)

import re
if re.compile(r'[0-9]{3}-[0-9]{4}').match(input()):
    print('Yes')
else:
    print('No')

B - PASTal Code

o の位置を探すのが楽だと思う．

実装 (Python)

X = input().find('o') // 4 + 1
print(X if X else 'none')

Python の find 関数は見つからなかった場合に $-1$ が返るので，この場合 $X=0$ となる．そのほかの場合は必ず $X\gt 0$ になっている．

C - 携帯電話の購入

$A _ i$ や $B$ を set で持って，intersection の要素数が $Q$ 以上のものを数えるとよい．

実装 (Python)

N, M = map(int, input().split())
A = []
for i in range(N):
   K, *X = map(int, input().split())
   A.append(set(X))
P, Q = map(int, input().split())
B = set(map(int, input().split()))
print(sum(Q <= len(B & X) for X in A))

Python では & 演算子で set 同士の intersection を取ることが出来て楽に書ける．

D - K項足し算

ここから計算量を意識しないといけなくなる．愚直にやると $\Theta(N ^ 2)$ となって厳しいので，累積和で高速化する．

つまり，

$\displaystyle S_i=\sum_{j=0}^{i-1}A_j$

とおくと，元の数列の区間和 $A _ l + \cdots + A _ {r - 1}$ は

$\displaystyle A_l+\cdots+A_{r-1}=\left(\sum_{j=0}^{r-1}A_j\right)-\left(\sum_{j=0}^{l-1}A_j\right)=S_r-S_l$

より $O(1)$ で計算できる．従って，全体 $\Theta(N)$ でこの問題を解くことが出来る．

実装 (Python)

N, K, *A = map(int, open(0).read().split())
S = [0] + A
for i in range(N):
    S[i + 1] += S[i]
for i in range(N - K + 1):
    print(S[i + K] - S[i])

E - 前から3番目

実装が辛いことに...

deque を知っていますか？という問題．deque は先頭および末尾要素の追加と削除がならし $O(1)$ でできるデータ構造．

実装 (Python)

from collections import deque
N = int(input())
A = deque()
S = input()
for i, c in enumerate(S):
    if 'L' == c:
        A.appendleft(i + 1)
    if 'R' == c:
        A.append(i + 1)
    if 'A' == c:
        if len(A) <= 0:
            print("ERROR")
        else:
            print(A.popleft())
    if 'B' == c:
        if len(A) <= 1:
            print("ERROR")
        else:
            v = A.popleft()
            print(A.popleft())
            A.appendleft(v)
    if 'C' == c:
        if len(A) <= 2:
            print("ERROR")
        else:
            u = A.popleft()
            v = A.popleft()
            print(A.popleft())
            A.appendleft(v)
            A.appendleft(u)
    if 'D' == c:
        if len(A) <= 0:
            print("ERROR")
        else:
            print(A.pop())
    if 'E' == c:
        if len(A) <= 1:
            print("ERROR")
        else:
            v = A.pop()
            print(A.pop())
            A.append(v)
    if 'F' == c:
        if len(A) <= 2:
            print("ERROR")
        else:
            u = A.pop()
            v = A.pop()
            print(A.pop())
            A.append(v)
            A.append(u)

F - 安全装置

場合分けを正しくするのが少し大変．現時点で何秒間連続で $L$ 以上の負荷がかかっているかを表す変数 $C$ を持っておく．はじめ， $C = 0$ である．

(可能な場合は) 各タスクの処理を開始する時点で必ず $C\lt T$ を満たすという仮定を置いて考えると良い．場合分けで破滅しそうな時はこういう仮定をちゃんと意識するのが結構大事だと思う (1WA したので偉そうに言えない)．

$B _ i\lt L$ の場合: $C = 0$ にリセットされ，答えに $A _ i$ を加算するだけでよい．
$B _ i \geq L$ かつ $C + A _ i \lt T$ の場合: $C\leftarrow C + A _ i$ とし，答えに $A _ i$ を加算するだけでよい．
$B _ i \geq L$ かつ $C + A _ i = T$ の場合: ちょうどタスク終了時に安全装置が起動するので，タスクのやり直しは発生しない．従って，答えに $A _ i + X$ を加算して $C = 0$ にリセットすればよい．
$B _ i \geq L$ かつ $C + A _ i \gt T$ の場合: タスクを $T - C\lt A _ i$ 秒処理した時点で安全装置が起動するので，タスクのやり直しが発生する．従って，答えに $T-C+A _ i +X$ を加算し， $C\leftarrow A _ i$ とすればよい．ただし， $A _ i \gt T$ であればタスクのやり直しが永遠に失敗するためここで forever を出力して終了する必要がある．また， $A _ i = T$ であればタスク終了時に再び安全装置が起動するので答えに更に $X$ を加算し， $C = 0$ にリセットする必要がある．

ここまで場合分けが出来れば，あとはそのまま実装すれば良い．

実装 (Python)

N, L, T, X = map(int, input().split())
C = 0
ans = 0
for i in range(N):
    A, B = map(int, input().split())
    if B < L:
        C = 0
        ans += A
    elif C + A < T:
        ans += A
        C += A
    elif C + A == T:
        ans += A + X
        C = 0
    else:
        ans += T - C + X + A
        C = A
        if C > T:
            print('forever')
            exit(0)
        elif C == T:
            ans += X
            C = 0
print(ans)

G - 一日一歩

突然難易度が上がった気がする．

動かないことが許されるので，一度到達可能になったらあとで到達不可能になることはない．そこで，頂点 $1$ から徐々に陣地を広げていくイメージで少しずつ辺を追加していくと考える．

「まだ使っていない辺のうち，到達可能な頂点の集合の要素を少なくとも一方の端点として持つもの」の集合を優先度付きキューに入れて管理すると，追加する $X _ i$ 以下の辺を効率的に探すことができる．優先度付きキューには合計で高々 $M$ 回 push され，合計で高々 $M$ しか pop されないので，優先度付きキューの操作にかかる計算量は全体 $O(M\log M)$ と評価される．

あとは，頂点 $1$ と連結な頂点の個数が高速に求まればよく，これは例えば Union Find 木によりクエリ当たり $O(\alpha(N))$ ( $\alpha$ はアッカーマン関数の逆関数) で計算できる．

以上より，全体 $O(N+Q+M(\log M + \alpha(N))$ でこの問題を解くことが出来た．

実装 (Java)

一日に 2 歩歩くことをうまく禁止する必要があるので注意．

自作のクラスが色々出てきますが，詳細は省略します (私の Java コードは大体 20000 Byte とかで，全部貼ってしまうとえらいことになるのでご容赦を...)．

int n = sc.nextInt();
int m = sc.nextInt();
int q = sc.nextInt();
// 無向グラフ
Graph<SimpleEdge> g = new Graph<>(n);
for (int i = 0; i < m; ++i) {
    int u = sc.nextInt() - 1;
    int v = sc.nextInt() - 1;
    int w = sc.nextInt();
    g.addEdge(new SimpleEdge(u, v, w));
}
// Union Find 木
DisjointSetUnion dsu = new DisjointSetUnion(n);
PriorityQueue<SimpleEdge> pq = new PriorityQueue<>();
for (var e : g.getEdges(0)) pq.add(e);
// i 日目に追加する辺を一時的に保存するための List
ArrayList<SimpleEdge> l = new ArrayList<>();
for (int i = 0; i < q; ++i) {
    int x = sc.nextInt();
    while (pq.size() > 0) {
        var e = pq.peek();
        if (e.cost > x) break;
        pq.poll();
        int u = e.from;
        int v = e.to;
        if (dsu.same(0, v)) {
            int tmp = u; u = v; v = tmp;
        }
        if (dsu.same(0, v)) continue;
        dsu.merge(0, v);
        l.addAll(g.getEdges(v)); // ここで pq に追加すると 1 日に 2 歩歩くことを許してしまうので注意
    }
    pw.println(dsu.size(0));
    pq.addAll(l);
    l.clear();
}

H - カンカンマート

缶切りの条件がややこしいので，買う缶切りの個数を全探索できないかを考える．

以下， $S _ 0 = \{i\mid T _ i = 0\},\ S _ 1 = \{i\mid T _ i = 1\}$ とし，列 $A,\ B$ を $A = (P _ i) _ {i \in S _ 0},\ B = (P _ i) _ {i \in S _ 1}$ で定義する．

缶切りの個数 $X$ を固定したとき， $B$ からは最大 $KX$ 個の要素を選ぶことができる．一方， $A$ からはいくつでも要素を選んでよい．選択可能な要素の (多重) 集合が決まっている場合，明らかに小さい順に貪欲に選んでいくのが最適である．従って，予め $B$ を昇順にソートしておくと， $B _ 1, \ldots, B _ { \min (KX, |B| ) }$ が選択可能であるとしてよい．

以上より，多重集合および下位 $M$ 個の和を効率的に管理できるデータ構造があればこの問題を解くことが出来ることが分かった．これは， $2$ 本の優先度付きキューを持ち，片方に下位 $M$ 要素を，もう片方にその他の要素を入れることにすれば実現できる．

実装 (Java)

LongPrioritySum が多重集合の下位 $M$ 要素の和を管理するクラスである．

int n = sc.nextInt();
int m = sc.nextInt();
int k = sc.nextInt();
long q = sc.nextInt();
LongPrioritySum ps = new LongPrioritySum(m, false);
IntArrayList t = new IntArrayList();
for (int i = 0; i < n; ++i) {
    int p = sc.nextInt();
    if (sc.nextInt() == 0) {
        ps.add(p);
    } else {
        t.add(p);
    }
}
t.sort();
int cnt = ps.size();
long ans = cnt >= m ? ps.sum() : Long.MAX_VALUE;
int max = (n + k - 1) / k;

for (int x = 1; x <= max; ++x) {
    int l = k * (x - 1);
    int r = Math.min(l + k, t.size());
    for (int j = l; j < r; ++j) {
        ps.add(t.get(j));
    }
    if (ps.size() >= m) {
        ans = Math.min(ans, q * x + ps.sum());
    }
}
pw.println(ans);

今回は LongPrioritySum が本質的なので，実装を示しておく (LongPrioeityQueue 標準ライブラリには存在しないので注意)．

public final class LongPrioritySum {
    private final boolean isDescending;
    private final LongPriorityQueue topk;
    private final LongPriorityQueue other;
    private int k;
    private long sumK = 0;
    public LongPrioritySum(int k, boolean descending) {
        this.isDescending = descending;
        this.topk = new LongPriorityQueue(!descending);
        this.other = new LongPriorityQueue(descending);
        this.k = k;
    }
    public LongPrioritySum(int k) {
        this(k, false);
    }
    public int  getK()      {return k;}
    public void setK(int k) {this.k = k;}
    public void incrK()     {this.k++;}
    public void decrK()     {this.k--;}
    public void addK(int v) {this.k += v;}
    public void subK(int v) {this.k -= v;}
    public void add(long v) {
        if (topk.size() == 0 || topk.getFirst() < v ^ isDescending) {
            other.add(v);
        } else {
            topk.add(v);
            sumK += v;
        }
    }
    public long sum() {
        int size = topk.size();
        if (size > k) {
            int d = size - k;
            while (d --> 0) {
                long v = topk.removeFirst();
                sumK -= v;
                other.add(v);
            }
        } else if (size < k){
            int d = k - size;
            while (d --> 0 && other.size() > 0) {
                long v = other.removeFirst();
                sumK += v;
                topk.add(v);
            }
        }
        return sumK;
    }
    public int size() {
        return topk.size() + other.size();
    }
}

I - 魚釣り

典型的な DP の問題．

$\displaystyle \mathrm{dp0}[c][i][j]=\text{区画 $(i,\ j)$ に至るまでに $c$ 回釣っており，かつ区画 $(i,\ j)$ で魚を釣っていない場合の最大値}$

$\displaystyle \mathrm{dp1}[c][i][j]=\text{区画 $(i,\ j)$ に至るまでに $c$ 回釣っており，かつ区画 $(i,\ j)$ で魚を釣っている場合の最大値}$

と定義する． $2$ つのテーブルに分けたのは，同じ区画で高々 $1$ 回しか釣れないという制約を考慮するためである．遷移は実装を見るのが一番早いと思う．

実装 (Java)

int h = sc.nextInt();
int w = sc.nextInt();
long[][] a = sc.longs(h, w);
long[][][] dp0 = new long[h + w][h][w];
long[][][] dp1 = new long[h + w][h][w];
for (int c = 1; c < h + w; ++c) {
    for (int i = 0; i < h; ++i) for (int j = 0; j < w; ++j) {
        // 区画 (i, j) で釣る場合の遷移
        dp1[c][i][j] = dp0[c - 1][i][j] + a[i][j];
        if (i > 0) { // 区画 (i - 1, j) から移動してくる場合の遷移
            dp0[c][i][j] = Math.max(dp0[c][i][j], dp0[c][i - 1][j]);
            dp0[c][i][j] = Math.max(dp0[c][i][j], dp1[c][i - 1][j]);
        }
        if (j > 0) { // 区画 (i, j - 1) から移動してくる場合の遷移
            dp0[c][i][j] = Math.max(dp0[c][i][j], dp0[c][i][j - 1]);
            dp0[c][i][j] = Math.max(dp0[c][i][j], dp1[c][i][j - 1]);
        }
    }
    // k = c の時の答えは max(dp0[c][h - 1][w - 1], dp1[c][h - 1][w - 1])
    pw.println(Math.max(dp0[c][h - 1][w - 1], dp1[c][h - 1][w - 1]));
}

J - ポイントとコストと

まず， $p$ によらず $(Y _ i - C) ^ 2$ の和は一定であるので別で計算しておく．すると，あとは

$\displaystyle \min_p\sum_{i=1}^N (X_i-p)^2$

を求める問題となる．これはかなり有名な問題で， $\displaystyle\underset{p}{\mathrm{argmin}}\sum _ {i=1} ^ N (X _ i - p) ^ 2 = \dfrac{\sum _ {i = 1} ^ N X _ i}{N}$ という結果が知られている．従って，あとは決めた $p$ を用いて計算をすればよい．

ただ，この結果を知らなくても，展開すれば $p$ の $2$ 次式になるので平方完成すれば最適な $p$ の値を求めることが出来る．

$\displaystyle \begin{align} \sum_{i=1}^N (X_i-p)^2 &=Np^2-\left(\sum_{i=1}^NX_i\right)p+\sum_{i=1}^NX_i^2\\ &=N\left(p-\dfrac{\sum_{i=1}^NX_i}{N}\right)^2+C\quad (C\equiv \mathrm{const}) \end{align}$

あるいは最小値を持つことを仮定し， $p$ で微分して微分係数が $0$ となる位置を計算してもよい．

実装 (Python)

N, C = map(int, input().split())
ans = sx = 0
xs = []
for _ in range(N):
    x, y = map(int, input().split())
    sx += x
    ans += (y - C) ** 2
    xs.append(x)
mx = sx / N
for x in xs:
    ans += (x - mx) ** 2
print(ans)

K - 共通クーポン

$V _ i = U _ i - P _ i$ とする．次を求めたい．

$\displaystyle \max _ {S\subset\{1,\ldots,N\}} \sum_{i\in S} V_i+20\times\left\lfloor\dfrac{\sum_{i\in S}P_i}{100}\right\rfloor$

厄介なのは切り捨て処理なので， $\left(\sum_{i\in S}P_i\right)\bmod 100$ を状態に持って次のように DP テーブルを定義する．

$\displaystyle \mathrm{dp}[i][m]=\max_{S\subset\{1,\ldots,i\}}\left\{V_i+20\times\left\lfloor\dfrac{\sum_{i\in S}P_i}{100}\right\rfloor\;\middle|\; \sum_{i\in S}P_i\equiv m\;\left(\mathrm{mod}\;100\right)\right\}$

これも遷移は実装を見た方が早いと思う．

実装 (Python)

N = int(input())
items = []
for _ in range(N):
    P, U = map(int, input().split())
    V = U - P
    items.append((V, P))
inf = 1000000000
dp = [[-inf] * 100 for _ in range(N + 1)]
dp[0][0] = 0
for i, (v, p) in enumerate(items):
    for j in range(100):
        q, r = divmod(j + p, 100)
        # 商品を買う場合の遷移
        dp[i + 1][r] = max(dp[i + 1][r], dp[i][j] + v + q * 20)
        # 商品を買わない場合の遷移
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
print(max(dp[N]))

L - 都市計画

使う環状交差点を $2 ^ M$ 通り全探索し， $N$ 個のタワーと使うと決めた環状交差点を頂点とし，辺を適切に張ったグラフの最小全域木を求めればよい．辺の重みは $O(1)$ で計算できるので，全体 $O(2 ^ M (N + M) ^ 2)$ ．

と言うのは簡単だけど，位置関係によって距離の計算が変わるので面倒くさい...

manabitimes.jp

ここを見てください (丸投げ)

実装 (Java)

static long d2(long dx, long dy) {
    return dx * dx + dy * dy;
}

static double d(long dx, long dy) {
    return Math.sqrt(d2(dx, dy));
}

static class Edge implements Comparable<Edge> {
    int u, v;
    double c;
    Edge(int u, int v, double c) {
        this.u = u; this.v = v; this.c = c;
    }
    @Override
    public int compareTo(Edge o) {
        return Double.compare(c, o.c);
    }
}

public static void solve(ExtendedScanner sc, FastPrintStream pw) {
    int n = sc.nextInt();
    int m = sc.nextInt();
    int[] tx = new int[n];
    int[] ty = new int[n];
    for (int i = 0; i < n; ++i) {
        tx[i] = sc.nextInt();
        ty[i] = sc.nextInt();
    }
    int[] cx = new int[m];
    int[] cy = new int[m];
    int[] cr = new int[m];
    for (int j = 0; j < m; ++j) {
        cx[j] = sc.nextInt();
        cy[j] = sc.nextInt();
        cr[j] = sc.nextInt();
    }
    int[][] bits = BitUtil.bits(m);
    double ans = Double.MAX_VALUE;
    for (int s = 0; s < 1 << m; ++s) {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        int l = bits[s].length;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                pq.add(new Edge(i, j, d(tx[i] - tx[j], ty[i] - ty[j])));
            }
            for (int j = 0; j < l; ++j) {
                int p = bits[s][j];
                pq.add(new Edge(i, n + j, Math.abs(d(tx[i] - cx[p], ty[i] - cy[p]) - cr[p])));
            }
        }
        for (int i = 0; i < l; ++i) {
            for (int j = i + 1; j < l; ++j) {
                int p = bits[s][i], q = bits[s][j];
                int x1 = cx[p], y1 = cy[p], r1 = cr[p];
                int x2 = cx[q], y2 = cy[q], r2 = cr[q];
                if (r1 < r2) {
                    int tmp;
                    tmp = x1; x1 = x2; x2 = tmp;
                    tmp = y1; y1 = y2; y2 = tmp;
                    tmp = r1; r1 = r2; r2 = tmp;
                }
                double dc = d(x1 - x2, y1 - y2);
                double c;
                if (dc >= r1 + r2) {
                    c = dc - (r1 + r2);
                } else if (dc >= r1 - r2) {
                    c = 0;
                } else {
                    c = r1 - r2 - dc;
                }
                pq.add(new Edge(n + i, n + j, c));
            }
        }
        DisjointSetUnion dsu = new DisjointSetUnion(n + l);
        double sum = 0;
        while (dsu.size(0) != n + l) {
            var e = pq.poll();
            int u = e.u, v = e.v;
            if (dsu.same(u, v)) continue;
            dsu.merge(u, v);
            sum += e.c;
        }
        ans = Math.min(ans, sum);
    }
    pw.println(ans);
}

M - 等しい数

今回の問題ではこれが一番難しかった．

まず， $A$ に現れる値 (クエリも含める) を座圧して $0,\ldots,M-1$ と番号を振りなおす．各クエリの時点における $A _ i$ の値を必要に応じて知れるようにするため，区間代入を載せた双対セグ木 (/遅延セグ木) を用意しておく．そして，各 $v$ に対して集合 $S _ v = \{i \mid A _ i = v\}$ を管理することを考える． $S _ v$ はそのまま set などで持つのではなく，区間の集合として持つ (いわゆる区間を set で管理するテク) ことにすると，愚直にやっても実はいい感じに計算量が償却される．

具体的には，次のような操作を行う．図中の left が指す値を取得するために双対セグ木が必要となっている．

f:id:suisen_kyopro:20210425082542p:plain — 図 1. クエリ処理前

f:id:suisen_kyopro:20210425082611p:plain — 図 2-1. クエリ $(L,\ R,\ x)=(1,\ 11,\ 2)$ の処理

図 2-1. クエリ $(L,\ R,\ x)=(1,\ 11,\ 2)$ の処理

f:id:suisen_kyopro:20210425082716p:plain — 図 2-2. クエリ $(L,\ R,\ x)=(1,\ 11,\ 2)$ の処理

f:id:suisen_kyopro:20210425082730p:plain — 図 2-3. クエリ $(L,\ R,\ x)=(1,\ 11,\ 2)$ の処理

f:id:suisen_kyopro:20210425082745p:plain — 図 2-4. クエリ $(L,\ R,\ x)=(1,\ 11,\ 2)$ の処理

f:id:suisen_kyopro:20210425082756p:plain — 図 2-5. クエリ $(L,\ R,\ x)=(1,\ 11,\ 2)$ の処理

f:id:suisen_kyopro:20210425082517p:plain — 図 3. クエリ処理後

区間が set に挿入される回数を考える．まず，初期状態に一致させるために $N$ 回挿入される．その後に挿入される回数は，クエリの個数 $Q$ に一致する．また，区間が部分的に削除される回数 (つまり，図 2-1, 2-5 のような状態になる回数) は，各クエリに対して高々 $2$ 回しか起こらない．

区間が set から削除される回数は挿入される回数と部分的に削除される回数の和で抑えられるので，結局 set の操作回数は全体で $O(N+Q)$ 回である．従って，set パートの計算量は全体で $O( (N+Q)\log(N+Q) )$ である．

また，双対セグ木に対するクエリ数は区間代入の回数と区間削除の回数の和であり，全体 $O((N+Q)\log N)$ である．

以上より，全体 $O( (N+Q)\log(N+Q) )$ でこの問題が解けた．

実装 (Java)

int n = sc.nextInt();
int[] a = sc.ints(n);
int q = sc.nextInt();
int[] vals = Arrays.copyOf(a, n + q);
IntPair3[] qs = new IntPair3[q];
for (int i = 0; i < q; ++i) {
    int l = sc.nextInt() - 1;
    int r = sc.nextInt();
    int v = sc.nextInt();
    qs[i] = new IntPair3(l, r, v);
    vals[n + i] = v;
}
IntCompress cmp = new IntCompress(vals, false);
for (int i = 0; i < n; ++i) {
    a[i] = cmp.compress(a[i]);
}
for (int i = 0; i < q; ++i) {
    qs[i].trd = cmp.compress(qs[i].trd);
}
int m = cmp.compressedSize();
long[] num = new long[m];
IntDualSegmentTree seg = new IntDualSegmentTree(
    a, (f, x) -> f, (f, g) -> f, -1
);
IntRangeSet[] rs = new IntRangeSet[m];
for (int i = 0; i < m; ++i) rs[i] = new IntRangeSet();
for (int i = 0; i < n; ++i) {
    rs[a[i]].add(i);
    ++num[a[i]];
}
long ans = 0;
for (long c : num) {
    ans += c * (c - 1) / 2;
}
for (var query : qs) {
    int l = query.fst, r = query.snd;
    int v = query.trd;
    int cur = l;
    while (cur < r) {
        int u = seg.get(cur);
        int nxt = rs[u].getInclusingRange(cur).getRight();
        long rem;
        if (nxt < r) {
            rem = rs[u].removeAll(cur, nxt);
            cur = nxt + 1;
        } else {
            rem = rs[u].removeAll(cur, r - 1);
            cur = r;
        }
        long x = num[u], y = num[u] - rem;
        ans -= x * (x - 1) / 2 - y * (y - 1) / 2;
        num[u] -= rem;
    }
    long add = rs[v].addAll(l, r - 1);
    long x = num[v] + add;
    long y = num[v];
    ans += x * (x - 1) / 2 - y * (y - 1) / 2;
    num[v] = x;
    seg.apply(l, r, v);
    pw.println(ans);
}

N - 活動

活動の順序さえ決まれば簡単な DP で求まるので，順序を一意に定められないかを考える．体力が $X$ のときに，活動 $i,\ j$ を行うとする．このとき，

$i,\ j$ の順で活動した場合: 得られる得点は $X\cdot a _ i + (X - b _ i)\cdot a _ j$
$j,\ i$ の順で活動した場合: 得られる得点は $X\cdot a _ j + (X - b _ j)\cdot a _ i$

である． $i,\ j$ の順で活動する方がよいのは $X\cdot a _ i + (X - b _ i)\cdot a _ j\gt X\cdot a _ j + (X - b _ j)\cdot a _ i$ が成り立つ場合で，これを整理すると次のようになる．

$\displaystyle \begin{align} & X\cdot a _ i + (X - b _ i)\cdot a _ j\gt X\cdot a _ j + (X - b _ j)\cdot a _ i\\ \Leftrightarrow & -b_ia_j\gt -b_ja_i\\ \Leftrightarrow & \dfrac{a_i}{b_i}\gt\dfrac{a_j}{b_j}\quad(\because b_i,\ b_j\gt 0)\\ \end{align}$

従って， $a _ i/b _ i$ の大きい順に使うかどうかを決めていけばよいことが分かった．あとは， $a _ i/b _ i$ の降順に活動をソートし，

$\displaystyle \mathrm{dp}[i][j]=\text{活動$i$までで残りの体力が$j$であるような選び方における得点の最大値}$

として DP をすればよい．

実装 (Java)

体力が負になることを許容する点に注意しながら実装する必要がある．負の index に対応するために添え字に下駄を履かせることもあるが，今回は直接終了状態に遷移するのが最適なのでその必要はない．

int n = sc.nextInt();
int h = sc.nextInt();
IntPair[] p = new IntPair[n];
for (int i = 0; i < n; ++i) {
    int a = sc.nextInt();
    int b = sc.nextInt();
    p[i] = new IntPair(a, b);
}
Arrays.sort(p, (p1, p2) -> {
    long a1 = p1.fst, b1 = p1.snd;
    long a2 = p2.fst, b2 = p2.snd;
    return Long.signum(a2 * b1 - a1 * b2);
});
long ans = 0;
long[][] dp = new long[n + 1][h + 1];
dp[0][h] = 0;
for (int i = 0; i < n; ++i) {
    long gain = p[i].fst;
    int damage = p[i].snd;
    for (int j = 0; j <= h; ++j) {
        dp[i + 1][j] = Math.max(dp[i + 1][j], dp[i][j]);
        if (j >= damage) {
            dp[i + 1][j - damage] = Math.max(dp[i + 1][j - damage], dp[i][j] + j * gain);
        } else { // 一旦体力が負になるとあとは活動しないのが最適なので，直接答えに遷移する．
            ans = Math.max(ans, dp[i][j] + j * gain);
        }
    }
}
pw.println(Math.max(ans, LongArrays.max(dp[n])));

O - 最短距離クエリ

制約が明らかに変なのでこれを活かす．入力を全域木とその他の $K:=M-N+1\leq 11$ 本の辺に分けておく．

木の場合，ダブリングなどにより LCA を $O(\log N)$ で求めることができるので，各頂点の深さを持つことで任意の $u,\ v$ に対し距離 $\mathrm{dist}(u,\ v)$ を $O(\log N)$ で計算することが出来る．

各クエリ $u,\ v$ に対し， $u,\ v$ および $K$ 本の余剰辺の端点以外の頂点を潰して考える．このとき高々 $2K+2\leq 24$ 頂点のグラフになるので，LCA による距離の計算によって適切に辺の重みを設定すれば，Dijkstra 法などによりクエリを $O(K ^ 2 \log N)$ で処理できる．ダブリングにより LCA を求める場合，全体の計算量は $O(N\log N + Q K ^ 2 \log N)$ となる．

実装 (Java)

int n = sc.nextInt();
int m = sc.nextInt();
DisjointSetUnion dsu = new DisjointSetUnion(n);
int k = m - (n - 1);
IntPair[] edges = new IntPair[k]; 
TreeBuilder tb = new TreeBuilder(n);
for (int i = 0, j = 0; i < m; ++i) {
    int u = sc.nextInt() - 1;
    int v = sc.nextInt() - 1;
    if (dsu.same(u, v)) {
        edges[j++] = new IntPair(u, v);
    } else {
        dsu.merge(u, v);
        tb.addEdge(u, v);
    }
}
TreeSet<Integer> need = new TreeSet<>();
int[] ids = new int[n];
Tree t = tb.build();
EulerTourLCA lca = new EulerTourLCA(t);
int q = sc.nextInt();
while (q --> 0) {
    int u = sc.nextInt() - 1;
    int v = sc.nextInt() - 1;
    need.add(u);
    need.add(v);
    for (var e : edges) {
        need.add(e.fst);
        need.add(e.snd);
    }
    int c = need.size();
    int[] vs = new int[c];
    for (int i = 0; i < c; ++i) {
        vs[i] = need.pollFirst();
        ids[vs[i]] = i; 
    }
    long[][] g = new long[c][c];
    for (long[] r : g) Arrays.fill(r, Dijkstra2.UNREACHABLE);
    for (int i = 0; i < c; ++i) {
        g[i][i] = 0;
        for (int j = i + 1; j < c; ++j) {
            int x = vs[i], y = vs[j];
            g[i][j] = g[j][i] = lca.dist(x, y);
        }
    }
    for (var e : edges) {
        int x = e.fst, y = e.snd;
        int i = ids[x], j = ids[y];
        g[i][j] = g[j][i] = 1;
    }
    long ans = new Dijkstra2(g, ids[u]).getDistance(ids[v]);
    pw.println(ans);
}