Atcoder水色精進記録
ABC212
E - Chain Contestant
https://atcoder.jp/contests/abc215/tasks/abc215_e
アルゴリズム・データ構造
bitDP
考察
各コンテストは出場する/出場しないの2択
1<N<=1000のため全探索は2*1000のため不可
→DPを検討
保持しておかないといけない情報は？
→現在までの選び方の総和、最後に選んだコンテスト、これまで選んだコンテスト
最後に選んだコンテスト=max(10)
これまで選んだコンテスト=2**10 (10種類のコンテストについて選んだ/選んでいないの2択)
計算量
N最後に選んだコンテストこれまで選んだコンテスト
1000*10*1000=10**7
提出
感想
3次元DPとなるため実装がかなり複雑だった。
bitDPを解説なしで導出できたのは成長を感じる。