8/8 解いた問題 - yamake's blog

こどふぉのバチャ一回です

A, Bの2完です

$case\quad 1$

$s_i=="YES"\quad(1\leq i\leq n-k+1)$

のときについて考えます。

これは $i$ 番目の人に辞書順で $i$ 番目に小さい名前をつければ満たすことができます。

$case\quad 2$

$s_j=="NO" \quad(1\leq i\leq n-k+1)$

の場合について考えます。

このとき、 $ans_{j+k-1}=ans_j$ とすれば良いです。

なぜなら、こうすることによって $s_{j-1}$ や $s_{j+1}$ に影響を与えること無く $s_j$ のみを"NO"の状態にできるからです。

したがって、 $1\leq i\leq k-1$ までは $case\quad1$ の通りに名付け、

それ以降は $s_i$ を見て、当てはまるやり方で名付ければ良いです。

全方位木DPをしました。これは想定解ではありません。

最初に想定解の解説をしてから全方位木DPでの解説をしようと思います。