7K12 blog

猫でも分かるアルゴリズム解説

AOJ ALDS1_5_A Exhaustive Search

f:id:tkr987:20200625221320p:plain

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4610462

  • bit全探索した 2^n通りの答えをメモ化

f:id:tkr987:20200625221617p:plain

制約を見ると20しかないのでbit全探索できそうと予想する。全ての組み合わせを調べても最大 2^{20}通りしかないので、全探索しても処理できる。ただし、各質問毎に毎回全探索するのは無駄なので、質問に答える前に 2^n通りの答えをメモ化しておこう。