AtCoder Beginner Contest 073
AtCoder Beginner Contest 073 - AtCoder Beginner Contest 073 | AtCoder:
http://abc073.contest.atcoder.jp
- masashinakata
- 1724
- 0
- 0
- 0
すとまと
@stmtk_g
@chokudai このD問題のDFSという関数の実行時間がだいたいO(n!)だと思うのですが、これの実行時間を減らす方法ってないですか? atcoder.jp/img/abc073/edi…
2017-09-15 15:59:12
chokudai(高橋 直大)@AtCoder社長
@chokudai
@stmtk_g あります!「今まで訪れた場所」「最後に訪れた場所」をメモする動的計画法を考えてあげると、状態数が2^n * nに対し、遷移がn通りなので、n=16くらいまでは間に合いますよー!
2017-09-15 16:00:19