【AtCoder】PythonでABC324を解く

はじめに

abc324のA,B,C,D問題をPython3で解きます。

A問題: Same

atcoder.jp

問題の概要

与えられる整数が全て等しいか答えよ。

問題の考察

集合のサイズが1かを調べます。

コード

def main():
    N = int(input())
    A = list(map(int, input().split()))
    ans = "Yes" if len(set(A)) == 1 else "No"
    print(ans)


if __name__ == "__main__":
    main()

B問題: 3-smooth Numbers

atcoder.jp

問題の概要

正の整数について、を満たす整数が存在するか答えよ。

問題の考察

をで割れるだけ割ったときにとなれば、そのようなが存在しています。

コード

def solve(N):
    n = N
    while n % 2 == 0:
        n //= 2
    while n % 3 == 0:
        n //= 3

    return n == 1


def main():
    N = int(input())
    ans = "Yes" if solve(N) else "No"
    print(ans)


if __name__ == "__main__":
    main()

C問題: Error Correction

atcoder.jp

問題の概要

個の文字列が文字列とほぼ等しいかを判定せよ(ほぼ等しいの意味は問題文を参照)。

問題の考察

文字列と文字列の長さが等しい場合、1つ差のある場合、それ以外の3つに場合分けて考えます。長さが等しい場合、先頭から順に見て違う文字同士の数が1以下ならほぼ等しいと分かります。1つ差の場合、先頭から順に見て違う文字があったらそれ以降が全て同じ文字ならばほぼ等しいと分かります。それ以外の場合、明らかにほぼ等しくなることはないです。個の文字列の入力と先頭から1文字ずつ見ていく処理があるため、計算量はで解けました。

コード

def solve(N, TT, Ss):
    def is_valid(S1, S2):
        if len(S1) > len(S2):
            S1, S2 = S2, S1

        if len(S1) == len(S2):
            return sum([s != tt for s, tt in zip(S1, S2)]) <= 1
        elif len(S1) + 1 == len(S2):
            for i, (s1, s2) in enumerate(zip(S1, S2)):
                if s1 != s2:
                    return S1[i:] == S2[i + 1 :]
            return True

        return False

    ans = []
    for i, S in enumerate(Ss, 1):
        if is_valid(S, TT):
            ans.append(i)

    return ans


def main():
    N, TT = input().split()
    N = int(N)
    Ss = [input() for _ in range(N)]
    ans = solve(N, TT, Ss)
    print(len(ans))
    print(*ans)


if __name__ == "__main__":
    main()

D問題: Square Permutation

atcoder.jp

問題の概要

長さの文字列を並び替えた結果を10進数の整数として解釈したもののうち、平方数となるようなものはいくつあるか答えよ。

問題の考察

と小さくはあるものの、並び替えた整数を全て作るのにの計算量だけ掛かるため、この方針だと解けないと分かります。

Wikipediaの平方数のページにあった平方数の数列を見ると、平方数の数は明らかに少ないと分かるため、先に平方数を列挙し、その後に文字列で各平方数を作れるかを判定するのがよさそうです。平方数を列挙するには、からまでの整数を二乗すれば得られます。各平方数を作れるかは、各平方数をゼロパディングした桁の10進数と見たときに各桁に現れる整数の頻度が、文字列と同じか調べれば判定できます。平方数を列挙するのに、各平方数を作れるかの判定にだけ掛かるため、全体での計算量で解けました。

コード

from collections import Counter
from itertools import count, takewhile


def solve(N, target_digits):
    target_hist = Counter(target_digits)

    MAX = pow(10, N)
    squares = [i * i for i in takewhile(lambda x: x * x < MAX, count())]

    ans = 0
    for s in squares:
        digits = list(f"{s:0{N}}")
        hist = Counter(digits)
        ans += int(hist == target_hist)

    return ans


def main():
    N = int(input())
    S = input()
    ans = solve(N, list(S))
    print(ans)


if __name__ == "__main__":
    main()