atcoder.jp 解法 それぞれの鍵を買うか否かの選択をM回することになるので、愚直に全探索しようとするとO(2M)になるが、制約的に時間が足りない。 そこでDPができないかを考えてみる。 愚直解がO(2n)になってしまう時、DPを使うと無駄な計算を省いて高速化で…

atcoder.jp 解法 問題を簡単に言い換えると、同じ種類のコンテストには連続でしか出場できないという条件を満たす、コンテストへの出場の仕方は何通りですか？ といった感じになる。 DPで解くことを考えてみる。 どの種類のコンテストへの出場経験があるか、…

atcoder.jp bitDPについて初めて学んだのでメモしておく。 bitDPとは？ 下の記事たちがわかりやすい。 algo-logic.info qiita.com 解法 巡回セールスマン問題であることが制約や問題名から読み取れる。 この問題の説明は下の記事でもされているので省く。 al…