AtCoder Beginner Contest 419 D - Substr Swap

AtCoder Beginner Contest 419 D - Substr Swap

問題はこちら

問題を解く時の思考の流れ

1. 一番無難な方法は問題文に記載されている文字列入れ替え操作を、そのまま $M$ 回行う。

   この方法だと、計算量が $O(NM)$ かかってしまう。

2. 上記の方針をもとに計算量を改善するためには、

   a. 問題文に記載されている文字列入れ替え操作の計算量を $O(N)$ から落とす

   b. 入れ替え操作を $M$ 回行うところを、なんとか工夫して減らす

   のいずれかを行わなければいけなそうだ。

3. 2の候補のうち、bの方が現実的だと思う。

   なぜなら、文字列入れ替え操作は $O(N)$ より減らせなさそうだから。

4. 実際に入力例1の操作を紙に書いてみると、

   i	s	t
   0	apple	lemon
   1	aemoe	lppln
   2	lppln	aemoe
   3	lpple	aemon

   上記を書いてみると、 $S$ 及び $T$ の $i$ 文字目は、$S$ の $i$ 文字目か $T$ の $i$ 文字目の2種類しかないことがわかった。

5. $i$ 文字目が2種類しかないということは、 $i$ 文字目について何回入れ替え操作が行われたかが分かれば、入れ替え操作を $M$ 回行う必要はないのではないか。

6. 入れ替え回数を管理する配列(この配列の長さは $N$ )を用意し、そこに入れ替え回数を蓄積していきたい。

   入れ替え回数を数えるためには、この配列の

   • 区間 $[L_1, R_1)$ に1を加える
   • 区間 $[L_2, R_2)$ に1を加える
   • ...
   • 区間 $[L_M, R_M)$ に1を加える

   という操作をする必要がある。
   これは、ナイーブに実装すると $O(NM)$ 回かかってしまうが、いもす法を使えば $O(M)$ で行うことができる。

7. ここまでの考察を踏まえると、

   • 入れ替え回数を管理する配列を作成するのに $O(M)$
   • $i$ 文字目を入れ替えた回数をもとに、実際に答えを作成するのに $O(N)$

   かかるので、計算量は $O(M + N)$ となり間に合う。

実装

pythonの命名規則に則り、問題文中で大文字となっている変数名も全て小文字にしているので注意してください。

n, m = map(int, input().split())
s = input()
t = input()
l = [0 for _ in range(m)]
r = [0 for _ in range(m)]
for i in range(m):
    tmp_l, tmp_r = map(int, input().split())
    l[i] = tmp_l
    r[i] = tmp_r

# 入れ替え回数を数える配列
swap_count = [0 for _ in range(n)]

# いもす法
tmp_array = [0 for _ in range(n+1)]
for i in range(m):
    tmp_array[l[i] - 1] += 1
    tmp_array[r[i]] -= 1

swap_count[0] = tmp_array[0]
for i in range(1, n):
    swap_count[i] = swap_count[i - 1] + tmp_array[i]

# 入れ替え回数が奇数の場合のみ、 i 文字目を T に変更する
ans = list(s)
for i in range(n):
    if swap_count[i] % 2 == 1:
        ans[i] = t[i]

print(''.join(ans))

教訓

• 実際に紙に書いてみる
• 配列の区間に特定の値を足すという行為を $N$ 回繰り返すとき、いもす法を使えば $O(N)$ で結果を求めることができる
• 最終的な状態から考える