geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

AtCoder Beginner Contest 286 備忘録

ABC グラフ Warshall-Floyd 部分和DP Sliding Window Aggregation

コンテストページ: UL Systems Programming Contest 2023(AtCoder Beginner Contest 286) - AtCoder
コンテスト中AC: A〜E

D - Money in Hand

公式解説とは異なる方法で $O(NX)$ とする方法を書いておきます。

Sliding Window Agrregationを使います。

DP遷移の一例を示します。
$A_i = 4, B_i = 2, X=24$ の時、 $i-1$ 番目の $j\ mod\ 3 = 0$ のDP値を集めて配列とします。
$C=\{dp[i-1][0],\ dp[i-1][4],\ dp[i-1][8],\ dp[i-1][12],\ dp[i-1][16],\ dp[i-1][20],\ dp[i-1][24]\}$

同様に $i$ 番目の $j\ mod\ 3 = 0$ のDPテーブルの更新を考えると

$dp[i][0] \leftarrow C_0$

$dp[i][4] \leftarrow C_0 \vee C_1$

$dp[i][8] \leftarrow C_0 \vee C_1 \vee C_2$

$dp[i][12] \leftarrow C_1 \vee C_2 \vee C_3$

$dp[i][16] \leftarrow C_2 \vee C_3 \vee C_4$

$dp[i][20] \leftarrow C_3 \vee C_4 \vee C_5$

$dp[i][24] \leftarrow C_4 \vee C_5 \vee C_6$

このように、 $j\ mod\ A_i$ が等しいものだけを集めると、最初の方を除いては値を求めるための区間は、長さが一定のまま1つずつ右にずれていくだけということがわかります。

そのため、スライド最小値を一般化したSliding Window Agrregationが使えます。
半群やモノイドが乗せられるはずだったと思いますが、実装はモノイドにしました。モノイドの型はbooleanを、二項演算は論理演算のORを、単位元はfalseにしておけば良いです。

コンテスト中の実装: Submission #38204795 - UL Systems Programming Contest 2023(AtCoder Beginner Contest 286)
Sliding Window Agrregationの実装: Submission #38292225 - UL Systems Programming Contest 2023(AtCoder Beginner Contest 286)

E - Souvenir

$N$ が小さいので全点対間最短経路をワーシャル・フロイド法によって求めることが可能です。
お土産の価値も最短経路の求め方と似たような感じで求めることができます。
二次元配列 $C$ を、

$C[i][j]:=i,j$ 間のお土産の価値

とおきます。
初期値として、

頂点 $u,v$ 間に有向辺があるなら、 $C[i][j] \leftarrow A_v$
頂点 $u,v$ 間に有向辺が無いなら、 $C[i][j] \leftarrow 0$

このようにして求めていくと、ワーシャル・フロイド法の最短距離のテーブル $dist$ の更新の際、

$dist[i][j] \gt dist[i][k]+dist[k][j]$ なら、 $C[i][j]\leftarrow C[i][k] + C[k][j]$
$dist[i][j] = dist[i][k]+dist[k][j]$ なら、 $C[i][j]\leftarrow max(C[i][j], C[i][k] + C[k][j])$

と更新すれば良いです。
なお、このままだと始点の価値が足されていないので、 $s_i,\ t_i$ の始点の価値を足して、 $C_{s_i,\ t_i}+A_{s_i}$ が求める価値です。

実装: Submission #38211470 - UL Systems Programming Contest 2023(AtCoder Beginner Contest 286)