【AtCoder参加記録】AtCoder Beginner Contest 233【AB2完】
C問題
https://atcoder.jp/contests/abc233/tasks/abc233_c
とD問題
https://atcoder.jp/contests/abc233/tasks/abc233_d
に挑戦しましたがどちらも解けずAB2完という結果でした。
C問題は実装方法がわからず、D問題は累積和の未実装しその後の高速化の方法がわかりませんでした。
以下はC問題の解説
https://atcoder.jp/contests/abc233/editorial/3162
のコードを参考にしたものです。
DFSについてはアルゴリズム実技検定公式テキストで知ってはいました。 実際に使えるようになるまで習熟度を上げていきたいです。
N, X = map(int, input().split()) L = [] AL = [] for i in range(N): l = list(map(int, input().split())) L.append(l[0]) AL.append(l[1:]) ans = 0 def dfs(pos, seki): global ans if pos == N: if seki == X: ans += 1 return for i in AL[pos]: if seki * i > X: continue dfs(pos+1, seki*i) dfs(0, 1) print(ans)
D問題については後日記事にしたいと思います。