CODE FESTIVAL 2017 Final B - Palindrome-phobia

AtCoder Python3

備忘録

問題

atcoder.jp

回答

import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

# import fractions

sys.setrecursionlimit(10000000)

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

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

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


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

    S = iss()
    cnt = collections.Counter(S)
    if abs(cnt['a'] - cnt['b']) > 1 or abs(cnt['a'] - cnt['c']) > 1 or abs(cnt['b'] - cnt['c']) > 1:
        print('NO')
    else:
        print('YES')


if __name__ == '__main__':
    main()

考え方

文字列が回文になり得るか否かを判定して回答する。

この問題では使用される文字が'a', 'b', 'c'の3種類。
この3種類で回文となり得るパターンを考える。

まず、対象が2文字以上のため、2文字から始めると、
'aa', 'bb', 'cc'の場合。同じ文字が2つ使われている場合には回文となる。
3文字の場合には、
'a〇a', 'b〇b', 'c〇c'の場合（〇はどの文字でもよい）。
3文字中に1種類の文字が2つ存在している場合には、入れ替えても'aa〇', 'bb〇'など、
2文字の回文が発生してしまう。
4文字の場合には、
'a〇aa', 'bb〇b', 'cbbc', 'bcbc'などの場合（〇はどの文字でもよい）。
4文字中に同じ文字が3つまたは2種類が2つずつ存在している場合には、
2文字または3文字の回文が発生してしまう。

これらの条件から各3種類の文字の出現回数に大きな差があると
回文になってしまう箇所が発生していることがわかる。

次に出現回数の差がどの程度あると、回文が発生するかを考える。
2文字の場合、'aa'を例にすると、
aの出現回数2, bの出現回数0, cの出現回数0と、最大と最小で2の差がある。
3文字の場合、'aba'を例にすると、
aの出現回数2, bの出現回数1, cの出現回数0と、こちらも最大と最小で2の差がある。

逆に、出現回数の差が全て1以内の文字列では、
'abc', 'abca', 'abcabc', 'abcabca'など、全て回文を回避することが出来る。

これらの条件から、
3種類の文字の出現回数をカウントし、
最大と最小で、出現回数の差が2以上存在している場合には回文となり得る箇所がある文字列、
最大と最小で、出現回数の差が1以下の場合には回文となりえない文字列とわかる。