AGC037 A - Dividing a String

AGC037 A問題の解説と解答例です。問題文

問題の概要

• "aabbaa" といった文字列をN個に分割する。
• ただし、分割の仕方には条件があり、S = ["a", "a" "bb", "aa"]のように分割したとすると、S[i] == S[i+1]となる部分を作ってはいけない。(この場合、S[0] == S[1] となってるため条件を満たしていない。)
• このルールで分割するとき、最大のNを求める。

解き方

解答例に載っているように、Nが最大になるような分割では、分割した文字列の長さはそれぞれ1か2のどちらかになる。

• "aabbaa" → ["a", "ab", "b", "aa"] (N = 4)
• "aaaccacabaababc" → ["a", "aa", "c", "ca", "c", "a", "b", "a", "ab", "a", "b", "c"] (N = 12)

どの連続する2文字を連結して、分割するかをO(N)で求める必要があるため、動的計画法を用いて解く。
入力された文字列Sのi文字目までの最大分割数を記録していく。分割された文字列は1文字か2文字であるため、想定されるパターンは次の4通り。

• 直前の分割された文字列が1文字で、文字列Sのi文字目を1文字で分割する
• 直前の分割された文字列が1文字で、文字列Sのi文字目とi+1文字目の2文字で分割する
• 直前の分割された文字列が2文字で、文字列Sのi文字目を1文字で分割する
• 直前の分割された文字列が2文字で、文字列Sのi文字目とi+1文字目の2文字で分割する

よってi文字目における最大分割数を上記の4パターンで記録しておく必要があるため、下記のようなリストを用意しておく。

dp = [[0 for _ in range(4)] for _ in range(len(S))]

このリストと上記の4パターンを対応させると次のようになる。

• dp[i][0] : 直前の分割された文字列が1文字で、文字列Sのi文字目を1文字で分割する
• dp[i][1] :直前の分割された文字列が1文字で、文字列Sのi文字目とi+1文字目の2文字で分割する
• dp[i+1][2] : 直前の分割された文字列が2文字で、文字列Sのi文字目を1文字で分割する
• dp[i+1][3] :直前の分割された文字列が2文字で、文字列Sのi文字目とi+1文字目の2文字で分割する

ここで、文字列Sの1文字目を1文字で分割する場合、文字列Sの1文字目と2文字目で2文字に分割する場合はそれぞれi文字目までの分割数が1なので、次のように初期化する。 (1文字目に対応するリストのインデックスは0)

dp[0][0] = 1
dp[1][1] = 1

最後にfor文で1文字目から文字列Sの最後の文字まで、上記の4パターンをリストに記録していく。

for i in range(1, len(S)):

  # 直前は1文字で分割 次は1文字で分割
  if S[i-1] != S[i]:
    dp[i][0] = max(dp[i-1][0], dp[i-1][2]) + 1

  # 直前は1文字で分割 次は2文字で分割
  if i < len(S) - 1:
    dp[i+1][1] = max(dp[i-1][0], dp[i-1][2]) + 1

  # 直前は2文字で分割 次は1文字で分割
  dp[i][2] = max(dp[i-1][1], dp[i-1][3]) + 1

  # 直前は2文字で分割 次は2文字で分割
  if  2 <= i < len(S)-1 and (S[i-2] != S[i] or S[i-1] != S[i+1]):
    dp[i+1][3] =  max(dp[i-1][1], dp[i-1][3]) + 1

解答コード全文

S = input()

dp = [[0 for _ in range(4)] for _ in range(len(S))]

dp[0][0] = 1
dp[1][1] = 1
for i in range(1, len(S)):

  # 直前は1文字で分割 次は1文字で分割
  if S[i-1] != S[i]:
    dp[i][0] = max(dp[i-1][0], dp[i-1][2]) + 1

  # 直前は1文字で分割 次は2文字で分割
  if i < len(S) - 1:
    dp[i+1][1] = max(dp[i-1][0], dp[i-1][2]) + 1

  # 直前は2文字で分割 次は1文字で分割
  dp[i][2] = max(dp[i-1][1], dp[i-1][3]) + 1

  # 直前は2文字で分割 次は2文字で分割
  if  2 <= i < len(S)-1 and (S[i-2] != S[i] or S[i-1] != S[i+1]):
    dp[i+1][3] =  max(dp[i-1][1], dp[i-1][3]) + 1


print(max(dp[-1]))