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 ぐらいになった。ワロタ。