はじめに
ABC381の復習メモです。
D - 1122 Substring
使用言語：Python (PyPy 3.10-v7.3.12)
説明
この問題のポイントを2点考えます。
- 同じ数字が3個続く場合
1 1 2 2 2 3 3 4 4
のような数字のときに、
2の前半を含むようにすると、1 1 2 2で最長は4。
2の後半を含むようにすると、2 2 3 3 4 4で最長6。
この場合は、部分列が偶数項始まりか奇数項始まりかの2パターンに分けると解決できそうです。
偶数項始まり1 12 22 33 44
奇数項始まり1 22 23 34 4
- 2回目のペアが出現する場合
1 1 2 2 1 1 3 3 4 4
のような数字のときに愚直に先頭から探索してしまうと
1 1 2 2-> 次に2度目の1が出てくるから1度区切る ->1 1 3 3 4 4で最長は6。
しかし、実際は2 2 1 1 3 3 4 4の最長8。
この場合は、2度目のペアが出てきたときに部分列の末尾を1度目のペアの次に持ってくる必要があります
これは尺取り法で再現できそうです。
数列:1 1 2 2 1 1 3 3 4 4
先頭:↑
末尾:↑
数列:1 1 2 2 1 1 3 3 4 4
先頭: ↑
末尾:↑
数列:1 1 2 2 1 1 3 3 4 4
先頭: ↑
末尾: ↑
数列:1 1 2 2 1 1 3 3 4 4
先頭: ↑
末尾: ↑
コード全文
import sys
input = sys.stdin.readline
def main():
N = input_to_int()
A = input_to_int_list()
# 偶数始まり
start_even = calc_max_length_of_substring(A, 0)
# 奇数始まり
start_odd = calc_max_length_of_substring(A, 1)
print(max(start_even, start_odd))
def calc_max_length_of_substring(A, start):
n = len(A)
ans = 0
used = set()
left = start
right = start
while right + 1 < n:
# 一度も使われてないペアが出現 = substringを1つ伸ばす
if A[right] == A[right + 1] and A[right] not in used:
used.add(A[right])
right += 2
ans = max(ans, (len(used) * 2))
# ペアでない数字の組が出現 = リセット
elif A[right] != A[right + 1]:
right += 2
left = right
used = set()
# 2度目のペアが出現 = 1度目の出現個所の次までsubstringの起点を進める
else:
while A[left] != A[right]:
used.remove(A[left])
left += 2
used.remove(A[left])
left += 2
return ans
def input_to_int_list():
return list(map(int, input().split()))
def input_to_int():
return int(input())
if __name__ == "__main__":
main()
E - 11/22 Subsequence
使用言語：Python (PyPy 3.10-v7.3.12)
説明
この問題では3点のポイントを考えます
-
特定のスラッシュに対する、部分列の最大値
愚直に考えるとスラッシュから左右１つずつ探索となります。
しかし、C問題と違い部分列のため、スラッシュごとに区間の端まで探索しなくてはならず計算が間に合いません。
[1121/2121212]という連続する部分列について、作れる最長の11/22文字列は111/222。
11/22文字列は部分列のため、間に余計な文字が入っても関係がありません。
つまり、区間左端～スラッシュにある１，スラッシュ～区間右端にある２の数を比較すれば、求める11/22文字列の長さが分かりそうです。
ある区間の和を高速に求める際使えるのは、累積和です。
-
区間内のスラッシュの特定
愚直に探索をすると、O(NQ)で間に合いません
なのでスラッシュの位置を高速で求める必要があります
111/212/11/22/11/221
という連続する部分列についてスラッシュの位置をリストで持つと(1-indexed)
[4, 8, 11, 14, 17]
クエリで与えられるのは区間の左端と右端
単調増加の数列に対して位置の特定ということで2分探索が使えそうです。
-
どのスラッシュを使えば最大になるか
区間両端のスラッシュの位置が分かったとしても、結局全スラッシュを探索すると時間がかかります。
111/212/11/21/11/221
↑
という連続する部分列について真ん中のスラッシュを考えます
スラッシュの左側の1は6個
スラッシュの右側の2は3個
つまり、11/22文字列の最長は7
これより右側のスラッシュを探索しても、右側の2が減るだけなので長さは伸びません。
よって、今より左側のスラッシュだけを探索すればよいことが分かります。（公式解説の別解）
これを、再び2分探索法を使って実装します
コード全文
import sys
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
def main():
N, Q = input_to_int_list()
S = input_to_str()
count_one = [0] * (N + 2)
count_two = [0] * (N + 2)
for i in range(1, N + 1):
count_one[i] = count_one[i - 1] + (1 if S[i - 1] == "1" else 0)
count_two[i] = count_two[i - 1] + (1 if S[i - 1] == "2" else 0)
slash_position = [i + 1 for i, s in enumerate(S) if s == "/"]
for _ in range(Q):
left, right = input_to_int_list()
# leftより右にあるスラッシュを探したい
slash_left = bisect_left(slash_position, left)
# rightより左にあるスラッシュを探したい
slash_right = bisect_right(slash_position, right) - 1
one, two = 0, 0
ans = 0
while slash_right - slash_left >= 0:
mid = (slash_right + slash_left) // 2
# スラッシュより左側の1の数
one = count_one[slash_position[mid]] - count_one[left - 1]
# スラッシュより右側の2の数
two = count_two[right] - count_two[slash_position[mid] - 1]
ans = max(ans, min(one, two) * 2 + 1)
# 1のほうが多い場合は、今より左側のスラッシュを探索
if one > two:
slash_right = mid - 1
else:
slash_left = mid + 1
print(ans)
def input_to_str():
return input().strip()
def input_to_int_list():
return list(map(int, input().split()))
if __name__ == "__main__":
main()
感想
2分探索を使えることに気づけないし、気づいてもbisectを使わないセルフ実装がうまく出来ない...