CODE FESTIVAL 2015 あさぷろ Easy B - ヘイホー君と置き換え
備忘録
問題
回答
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() if N % 2 != 0: print(-1) exit() ret = 0 for a, b in zip(S[:N//2], S[N//2:]): if a != b: ret += 1 print(ret) if __name__ == '__main__': main()
考え方
まず、N
が奇数の場合には平方を作ることはできません。
そのため、N % 2 != 0
の場合には-1
とします。
次にN % 2 == 0
の場合について考えます。
平方であるためには、前半の文字列と後半の文字列が同一であることが求められます。
つまり、文字列S
の先頭からN//2
文字目までと、文字列S
の末尾からN//2
文字目までで、
異なる文字の数だけ操作によって置き換える必要があります。