無向グラフの探索。再帰よりもキューのほうが好き。深さ優先と幅優先の切り替えが楽だから。
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))
簡単な因数分解。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あたりを覚えたらかなり行数が減った気がする。