ABC 054 C One-stroke Path と OI 2009 予選 D カード並べ

https://qiita.com/drken/items/e77685614f3c6bf86f44

の続き。

https://atcoder.jp/contests/abc054/tasks/abc054_c

問題概要

自己ループ、多重辺がないグラフが与えられる。頂点番号 1 から全ての頂点をたどるパスは何通りあるか?

考えた解法

dfsで全探索。通った。visitedフラグを戻したりする練習になった。

visited, g = ([], [])

def dfs(i):
    visited[i] = True
    ans = 0
    if all(visited):
        visited[i] = False
        return 1
    for j, b in enumerate(g[i]):
        if b and not visited[j]:
            ans += dfs(j)
    visited[i] = False
    return ans


def main():
    global visited, g
    n, m = [int(i) for i in input().split()]
    visited = [False for i in range(n)]
    g = [[False for i in range(n)] for j in range(n)]
    for i in range(m):
        t, f = [int(j)-1 for j in input().split()]
        g[t][f] = True
        g[f][t] = True
    print(dfs(0))


if __name__ == '__main__':
    main()

https://atcoder.jp/contests/joi2010yo/submissions/me

問題概要

カードが、N 枚あり、そのうち K 枚を横 1 列に並べ、できる数字の数を求める問題。

考えた解法

usedフラグを用いて、組み合わせを列挙する。前に、組み合わせを自分で書いた時より大幅に、コードを理解できるようになっていてびっくりした。

used = []
ans = set()
n, k = 0, 0
t = []
card = []

def rec(i):
    if i == k:
        ans.add(int(''.join(t)))
        return
    for j in range(n):
        if not used[j]:
            used[j] = True
            t.append(card[j])
            rec(i+1)
            t.pop()
            used[j] = False
    return

def main():
    global used, n, k, card
    n = int(input())
    k = int(input())
    used = [False for i in range(n)]
    card = []
    for i in range(n):
        card.append(input())
    rec(0)
    print(len(ans))

if __name__ == '__main__':
    main()

最初、再帰関数の i == k で return を書き忘れたけど、ギリ 10 秒以内(9.6s)で通ったw あとで気づいて、return入れたら 26ms ぐらいになった。ワロタ。