SRM581Div1Easy
問題
N個のコンテナとM個の監視カメラを考える。監視カメラは連続したL個のコンテナを監視できる。コンテナが空の場合は"-"となり、何か入っている場合は"X"となる。カメラの位置は分からないが、カメラが監視している空でないコンテナの数は与えられる。
この時のコンテナの状態を求めよ。
ただし、コンテナの状態は必ず監視されている場合は"+"、監視されている可能性がある場合は"?"、監視されていない場合は"-"で表す。
解法
各コンテナを監視していないと仮定した時の与えられた条件を満たすかを確認することで、そのコンテナが"+"、つまり、必ず監視されているかどうかを判別できる。
必ず監視されているとは言い切れない場合は、そのコンテナを監視することができるかを調べる。これは、先ほどと逆で監視されていると仮定した時に条件を満たすかを調べればよい。
計算量
mapの挿入コストは無視している。
