ARC104 B

昨日惨敗したのであんまりちゃんと考えられてなかったARC104 Bを考えてみました。

AtCoder Regular Contest 104 B - DNA Sequence

サンプルを見るまでどういう状況かわかりづらかったけど、サンプルを見ながら考えたら状況はわかった。

サンプルにあるみたいに、ペアを考えていくと大変そうなので、別の方法を考えます。ざっくり考えて、A, T, C, G の個数を数えていけばよくて、ある場所からある場所まで見たときに、A, Tの個数とC, Gの個数が一致してれば、適当に並び替えれば条件を満たすことがわかります。

で、そもそもN^2が通るので、そのまま書けばOK。提出 #17196353