AtCoder Beginner Contest 054 - C / 057 - C

beta.atcoder.jp

無向グラフの探索。再帰よりもキューのほうが好き。深さ優先と幅優先の切り替えが楽だから。

def solve(N, M, Es):
    al = {}
    for e in Es:
        al.setdefault(e[0], []).append(e[1])
        al.setdefault(e[1], []).append(e[0])

    ans = 0
    q = [(1, [1])]
    while len(q) > 0:
        current, history = q.pop()
        nexts = al[current] if current in al else []
        if len(history) == N:
            ans += 1
        for n in nexts:
            if n not in history:
                nhist = history[:]
                nhist.append(n)
                q.append((n, nhist))
    return ans


if __name__ == "__main__":
    N, M = map(int, input().split(" "))
    Es = []
    for _ in range(M):
        Es.append(tuple(map(int, input().split(" "))))
    print(solve(N, M, Es))

beta.atcoder.jp

簡単な因数分解。300点でも波があるな。

因数を探すとき、上限が√Nであるのはよいのだけれど、下を少し気にしなくてはいけない。 素因数分解だとrangeの最初は2。Nを割りながら探すために1にすると無限ループになってしまう。 逆に単なる因数はNが素数の時を考慮しなくてはならないので、1になる。

def solve(N):
    ret = []
    for i in range(1, int(N ** 0.5) + 1):
        if N % i == 0:
            ret.append(max(len(str(i)),
                           len(str(N // i))))
    return min(ret)


if __name__ == "__main__":
    N = int(input())
    print(solve(N))

pythonはmin / max / all / anyあたりを覚えたらかなり行数が減った気がする。