AGC028 A - Two Abbreviations

備忘録

問題

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

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)

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


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

    N, M = il()
    S = iss()
    T = iss()
    G = math.gcd(N, M)

    for g in range(G):
        if S[g * N // G] != T[g * M // G]:
            print(-1)
            exit()
    else:
        print(lcm(N, M))


if __name__ == '__main__':
    main()

考え方

よい文字列を作るために、文字列Sと文字列Tで一致する箇所が発生する。
そのため、一致しているが文字列Sと文字列Tで同じ文字か否かを判定する。
下記の解説が非常に丁寧でわかりやすかった。

AtCoder AGC028 A - Two Abbreviations (300点) - Hewlaの競プロ記

まずよい文字列Xの長さLについて考える。
最も小さい倍数で一致していない場合には、倍数を何倍しても一致することはないため、
長さLはNとMの最小公倍数(lcm)となる。

次によい文字列Xの中で、
文字列Sと文字列Tの文字が出現する箇所について考える。

文字列Sの文字がよい文字列Xの中で出現する箇所は0-indexで考えると、
0, L//N, 2 * L//N, 3 * L//N, ...。つまり、L//Nの倍数で出現する。
また、文字列Tの場合には0, L//M, 2 * L//M, 3 * L//M, ...となり、L//Mの倍数で出現する。
このL//Nの倍数とL//Mの倍数については最大公約数(gcd)で求めることが出来る。
下記解説参考に実装した。

AtCoder AGC 028 A - Two Abbreviations (300 点) - けんちょんの競プロ精進記録

数学系の問題はほかの方の解説を読んでも理解が覚束ない。。。