ARC108 B - Abbreviate Fox

備忘録

問題

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")

    N = ii()
    S = iss()

    ret = ''
    for i in range(N):
        ret += S[i]
        if len(ret) > 2 and ret[-3:] == 'fox':
            ret = ret[:len(ret)-3]
    print(len(ret))


if __name__ == '__main__':
    main()

考え方

基本的には文字列の先頭からfoxが存在するか否かを確認する。
ただし、foxの出現後に残りの文字列を結合するため、スタックを用いる。

与えられた文字列の先頭から文字を取り出し、スタックに文字を入れる。
スタックが３つ以上たまっている場合には、最後に入れられた3文字がfoxであるか否かを判定する。
foxである場合にはスタックから文字を３つ取り出す。

あとは上記の処理を繰り返し行うことで、最終的にスタックに残った文字列が回答となる。