コンテスト中AC:A〜E

D - Takahashi's Solitaire

コンテスト後に考え直したので、メモしておきます。

一旦modを無視します。
以下の問題を解けばこの問題に答えられます。

$A$ から要素を順に選び、 $B=\{B_1,\ B_2,\ \cdots ,\ B_m\}$ とする。但し、 $B$ は以下の条件を満たさなければならない。

$1\leq i\leq m-1$ について、 $B_{i+1} - B_i \leq 1$
要素の和が最大となる $B$ を求めよ。

ここで、 $A$ を昇順ソートしておくと、 $B$ は $A$ の連続部分列となります。

また、和を最大化したいので、連続部分列は条件を満たす限り伸長させた方が良いです。そのため、各要素は2つ以上の連続部分列に属する必要がありません。

そこで、 $A$ の連続部分列を探索する際、例えば、 $A_i,\ A_{i+1},\ \cdots ,\ A_j$ が可能な限り伸長した連続部分列であるなら、次の連続部分列の探索は $A_{j+1}$ から再開すれば良いです。探索範囲を右に進めるだけとなるので、 $O(N)$ となります。

modの部分ですが、これは $A_1 = 0$ かつ $A_{N} = M-1$ の場合に、これらを含む連続部分列を繋げるようにすれば解決になるわけですが、以下の2パターンで実装してみました。

解決方法1
配列が円環となることが想定される場合の常套手段ですが、 $A$ を昇順ソートしたものを2つ繋げます。これに対して連続部分列を探索すれば、modを考慮した場合と同様の結果が得られます。
但し、 $A$ に $0,\ 1,\ \cdots ,\ M-1$ の全てが含まれる場合は、 $A$ の要素の和を超えてしまうので注意が必要です。
実装例:Submission #36484745 - Daiwa Securities Co. Ltd. Programming Contest 2022 Autumn (AtCoder Beginner Contest 277)

解決方法2
Union-Findを用いた解法です。0-indexedとします。
$A$ を昇順ソートし、 $0\leq i \leq N-1$ について、 $A_i = A_{(i+1)\ mod\ N}$ または、 $(A_i +1) \ mod M = A_{(i+1)\ mod\ N}\ mod M$ が成り立つなら、Union-Findで同一連結成分とします。