AGC037 A - Dividing a String

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array
import time
import numpy as np
from numpy import linalg as LA

# 時々使う
# import numpy as np
# from decimal import Decimal, ROUND_HALF_UP
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from collections import defaultdict, deque

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


# MOD = 10 ** 9 + 7
MOD = 998244353
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    S = iss()

    pre = ''
    now = ''
    ret = 0
    for i in range(len(S)):
        now += S[i]
        if now != pre:
            pre = now
            now = ''
            ret += 1
    print(ret)


if __name__ == '__main__':
    main()

回答

前後の文字列が異なるように、文字列の分割を行います。
一つ前の分割した文字列と、次の分割する文字列を保持して、
異なる文字列とすることができれば、分割を終了させます。

分割を行った後の文字列は必ず一文字または二文字のどちらかになります。
つまり、長さ３以上の文字列（区間）は存在しないという制約を利用して動的計画法でも回答を求めることが出来ます。

AtCoder AGC 037 A - Dividing a String (灰色, 300 点) - けんちょんの競プロ精進記録