D - Change Usernames

ユーザ名の重複を取り除き、番号を振り直したものを $s=\{s_0,\ s_1,\ \cdots\ ,\ s_m\}$ とします。

$s_i$ から $s_j$ に、 $s_j$ から $s_k$ に変更することを考えます。
配列の途中に要素を挿入する場合に末尾要素から順に後ろにずらしてスペースを作りますが、同じように、 $s_j$ を $s_k$ に変更してから $s_i$ を $s_j$ に変更すれば、2つの変更を達成できます。

達成できない場合を考えると、例えば、 $s_i$ から $s_j$ に、 $s_j$ から $s_k$ に、 $s_k$ から $s_i$ にする変更は不可能です。

これらの関係を有向グラフの問題にすると見通しが良くなります。

$s$ の各要素を頂点、 $s_i$ から $s_j$ に変更したい場合に $s_i$ を始点、 $s_j$ を終点として有向辺を張ります。ユーザ名の変更は、有向辺を一回辿ることと考えることができます。

この有向グラフに閉路があると、移動順を決められず、達成できないことがわかります。逆に閉路がない場合、トポロジカルソートして、末尾から順に移動すれば達成できます。

従って、このグラフに閉路存在するかを判定すればよいです。
コンテストでは、AtCoder Libraryの強連結成分分解を使いました。
実装: Submission #38053494 - AtCoder Beginner Contest 285

E - Work or Rest

連勤する日数に対して、得られる生産量は固定です。

例えば3連勤すれば $A_1+A_2+A_1$ が生産量です。
これは、 $A$ の累積和をとっておき、連勤する日数の偶奇で場合分けすることで $O(1)$ で計算できます。

この問題では、以下のように考えることができます。

$i$ 連勤に必要な日数を $w_i$ 、 $i$ 連勤で得られる生産量を $v_i$ とする。合計日数が $N$ 以下となるように選んで連勤する時、得られる生産量の最大値を求めよ。但し、各連勤は何度してもよい。

これは個数制限の無いナップサック問題と同じです。連勤日数は最大で $N-1$ 日なので、 $O(N^2)$ で解けます。

注意が必要なのは、 $i$ 連勤に必要な日数は $i$ 日ではないということです。
前か後ろの一方にのみに休日を入れておけば全体として矛盾がないので、 $i+1$ 日としておけば良いです。
実装: Submission #38131229 - AtCoder Beginner Contest 285

F - Substring of Sorted String

$S_l,\ S_{l+},\ \cdots ,\ S_r$ を、 $S_{l,r}$ と表現します。

$S_{l,r}$ が $T$ の連続する部分列であるための条件は以下の2つです。

$S_{l,r}$ が昇順に並んでいる
文字をabc順に並べた時に $S_{l}$ より後ろ、かつ、 $S_r$ より前の文字 $c_i$ について、 $S_{l,r}$ に含まれる $c_i$ の個数と $S$ 全体に含まれる $c_i$ の個数が等しい

1つ目は自明だと思うので、2つ目を具体例で示します。

$S_{l,r}=aabccdf$ とします。
まず、 $S_l = a,\ S_r = f$ は $S_{l,r}$ の先頭と末尾ですが、これは $S$ に何個含まれていても良いです。例えば、 $T$ の連続する部分列が、

$aaabccdfffff$

であったとしても、

$a|aabccdf|ffff$

という感じに分けることを考えれば $S_{l,r}$ に一致させることができることがわかります。

反対に $a$ と $f$ の間の文字、 $b,c,d,e$ は $S_{l,r}$ に含まれる個数と $S$ 全体に含まれる個数が一致しなければいけません。
もし、 $S_{l,r}$ 以外の箇所にこれらの文字が含まれていた場合、昇順ソートして $T$ にした時に、 $S_{l,r}$ の間に1文字以上挿入されることになり、一致しなくなります。