https://atcoder.jp/contests/abc244/tasks/abc244_d
以下の３つの方法で解きます
- 全列挙で考察
- 転置数
- 乱択
1:全列挙で考察
R,G,Bの並び替えは6つしかないです。以下の解説のように図を書いて考えます。
https://atcoder.jp/contests/abc244/editorial/3594
コードは割愛します。(解説に書いてある通りです。
長さがNだとするとハッシュをO(N)でとれるとして
- 時間計算量はO(N)
- 空間計算量はO(N!)と極めて大きな数になります
2:転置数
これも上記の解説に書いてある通りです。ある1,2,3,4,...,nという数列が昇順で並んでいた時、異なるi, jを選んでswapするとその転置数は奇数になります。もう一度、適当なswapをすると転置数は偶数になります。
今回の場合、操作の回数が十分なので、偶数回の移動で両者の転置数の偶奇が一致するものに絶対遷移できます。なので、偶奇を判定します。
転置数の実装は典型通りにBITで頑張ります。
- 時間計算量: O(NlogN)
- 空間計算量: O(N)
実装(Python)
# https://ikatakos.com/pot/programming_algorithm/data_structure/binary_indexed_tree
class Bit:
def __init__(self, n):
self.size = n
self.tree = [0] * (n + 1)
def sum(self, i):
s = 0
while i > 0:
s += self.tree[i]
i -= i & -i
return s
def add(self, i, x):
while i <= self.size:
self.tree[i] += x
i += i & -i
############################################
# 転置数を求める
# 1,2,3...のリスト。0はダメ版
def transposes(s):
n = len(s)
bit = Bit(n)
ans = 0
for i in range(n):
assert s[i] != 0
ans += i - bit.sum(s[i])
bit.add(s[i], 1)
return ans
a = input().replace("R", "1").replace("G", "2").replace("B", "3").split()
b = input().replace("R", "1").replace("G", "2").replace("B", "3").split()
a = list(map(int, a))
b = list(map(int, b))
if transposes(a)%2 == transposes(b)%2: print("Yes")
else: print("No")
3: 乱択
実はsample-1を読むと、場面: 偶数回のSWAPの回数が残っていても、今、正解と同じ順番になっていればYesになることが分かります。
Nが3と小さいので以下のように考えます。
- ある瞬間、あと偶数回swapできるなら2回適当にswapする
- もし、
場面であればYes。Noならもう一度swapを繰り返す - 十分な数これを繰り返してもダメならNo
ここで、あり得る並び方は1の通り高々6通りのため、十分な数(例えば1000回など)swapすれば、まず、十分に判定できそうです。
このように、適当な試行回数で、全パターンを（ほぼ間違いなく=100%ではない）列挙しきれる場合、乱択は条件の考慮漏れなどの心配がなく、有効な手段です。
今回は愚直に比較をしているので時間計算量は試行回数をkとしてO(kN)ですが、工夫すれば(例えば、異なる数字の数を持っておけば)、O(k)になります。
実装(Python)
from random import sample
import sys
s = input().split()
t = input().split()
for i in range(100000):
if s == t and i%2==0:
print("Yes")
sys.exit(0)
i, j = sample([0,1,2], 2)
s[i], s[j] = s[j], s[i] # 適当な2つをswap
print("No")