ABC 401-500/ABC401D - Logical Filling - 競技プログラミング用 知識集積所

---

問題

ABC401D

必要知識

B以下レベルの内容は省略

• 特になし

考え方

まず、?のカタマリの前後がoか.か端かで対応が変わって面倒。
そこで、oの隣は必ず.になることを利用して、?の両サイドが必ず.か端であるようにしておく。

?が複数個所に分かれている場合、左のカタマリのo.の入り方が右のカタマリに（個数以外は）影響を及ぼさない。
そこで、1つのカタマリにoが入る個数とその入り方を研究すればよい。

• ?が1連続の場合

最大1個。
oが1個の場合はo、oが0個の場合は.

• ?が2連続の場合

最大1個。
oが1個の場合は??、oが0個の場合は..

• ?が3連続の場合

最大2個。
oが2個の場合はo.o、oが1個の場合は???、oが0個の場合は...

• ?が4連続の場合

最大2個。
oが1～2個の場合は????、oが0個の場合は....

• ?が5連続の場合

最大3個。
oが3個の場合はo.o.o、oが1～2個の場合は?????、oが0個の場合は.....

つまり、

• 奇数個連続の場合
  • 最大で(個数+1)/2個のoが入る可能性があり、その場合は奇数番目がoで偶数番目が.
  • 最小で0個のoが入る可能性があり、その場合は全部.
  • それ以外の個数、または個数不定の場合は全部?
• 偶数個連続の場合
  • 最大で(個数)/2個のoが入る可能性があり、その場合は全部?
  • 最小で0個のoが入る可能性があり、その場合は全部.
  • それ以外の個数、または個数不定の場合は全部?

あとは、

• 全部最大数入れなきゃいけない場合
• 全部最小数入れなきゃいけない場合
• どちらでもない

のいずれであるかを判断すればいい。

?の連続数は、

• 前から愚直に見ていく
• ?の左端と右端を検出する

などの方法がある。

解答例

解答例

注意点

別解