ABC172 E - NEQ [解説]
いかつい見た目をしているが意外と簡単。
考えること
割とぱっと見で逃げ出したくなるような問題だが、まず $A$ を固定することを考える。そのためには $A$ の総数を考えたい。
単純な話だが、これは $1, 2, \ldots, M $ 以下の正整数から $N$ 個とるだけなので、$A$ の総数は $_MP_N$ と等しくなる。
あとは $A_i \neq B_i$ を満たすように $B$ を列挙するが、これが $Ο(N)$ でないと間に合わず、それにシンプルに列挙することもかなわない。$(M - 1)^N$ にしても全く見当違いな値になってしまう。
そこで、条件を満たす数列の個数を
$S = N$ 項であり、全ての要素が $M $ 以下で互いに相異なるような数列の集合
と定義したうえで、そのうえで包除原理を用いて求めることを考える。こうすると、
- $i$ 項以上が数列 $A$ と一致しているような数列 $B$ の総数
を $1$ 以上の全ての $i$ について求めることで、最終的に解を得られる。
$S$ は明らかにこれまた $_MP_N$ 種類の数列を含んでいる。
また、$i$ 項以上が数列 $A$ と一致しているような数列 $B$ の総数、といったが、これを求めるのは簡単で
$_NC_i \times (M-i)^{N-i}$
とするだけである。
一見、直感に反するかもしれないが、$i$ 項以上という条件が大事であり、ゆえに、必ず一致する $i$ 項を除いて、あと $N-i$ 項は重複していようがいなかろうがどうでもいいのだ。よってこの式は正当である。
なお、ちょうど $i$ 項が数列 $A$ と一致しているような数列 $B$ の総数、としてしまうのは誤りである(この場合、包除原理を使う前の条件と同じ理論で、どうしようもなくなる)。
あとは、全ての数列 $A$ について求めた $B$ の個数を掛けて、それが解である。
なお、脳が働いておらず $_nP_r$ を求めるために $_nC_r \times r!$ をしている。
ABC224 F - Problem where +s Separate Digits [解説]
ぱっと見滅茶苦茶 ad-hoc そうなのに考えれば考えるほど典型になってｳﾜｧ……ってなる
でもすき
考えること
正直サンプル $1$ を見た瞬間解法わかった人も多そうだが、自分はそれから検証の為に数分ほどは必要だった。
あと、なんならサンプル $1$ の全数式が列挙されている部分がこの問題の全てである。
以下、$|S| = N$ とする。
桁ごとに考える、という典型テクニックがある。普段は xor とかで用いるものだが、今回この全数式が列挙されている部分を執念深く睨むことで答えに近づくことが出来る。
というのも、例えばサンプル $1$ の入力のうち一番上の桁である $1$ について見ると、数式上で $1$ がある項において、$1$ が下から $1$ 桁目である場合が $4$ 回、$2$ 桁目である場合が $2$ 回、$3$ 桁目である場合が $1$ 回、$4$ 桁目である場合が $1$ 回あることがわかる。
つまり、$4$ 桁目、つまり一番上を例外として、あとは下から $i$ 桁目に出現する回数が $2^{N-i}$ 回となっている。
また、入力の $j$ 桁目になると、その数がある項において $1, 2, \ldots, j - 1$ 桁目までに出現する回数は $0$ となり、$j$ 桁目に出現する回数が $2^{j-1}$ に置き換わる。(なお、実際にはこれが $j = 1$ でも正しい)
イメージとしては、入力の一番上の桁を見ているときは、数式上でその桁が出現する項においてその項の $i$ 桁目に出現する回数が
$[1,1,2,4,8,16, \ldots]$
という感じで、入力の下の項に行くにしたがって左から順に
$[0,2,2,4,8,16, \ldots]$
$[0,0,4,4,8,16, \ldots]$
$[0,0,0,8,8,16, \ldots]$
$\vdots$
といったように変化していく。
なお、このことは、
見ている桁よりも右側にいくら + が置かれようが関係ない
ことから $2$ の階乗となること、
見ている桁が下から $i$ 番目なら、分割後のその桁がある項において下から $i$ 番目よりももっと上に来ることは無い
ことから、少しずつ $0$ が増えていくことが証明できる。厳密な証明については割愛する。
そして、これらについて、出現する桁が下から $i$ 桁目ならば $10^i$ を掛けた値をとる。つまり、
入力の $1$ 桁目 -> $[1 \times 10^N,1 \times 10^{N-1},2 \times 10^{N-2},4 \times 10^{N-3},8 \times 10^{N-4}, \ldots]$
入力の $2$ 桁目 -> $[0 \times 10^N,2 \times 10^{N-1},2 \times 10^{N-2},4 \times 10^{N-3},8 \times 10^{N-4}, \ldots]$
入力の $3$ 桁目 -> $[0 \times 10^N,0 \times 10^{N-1},4 \times 10^{N-2},4 \times 10^{N-3},8 \times 10^{N-4}, \ldots]$
入力の $4$ 桁目 -> $[0 \times 10^N,0 \times 10^{N-1},0 \times 10^{N-2},8 \times 10^{N-3},8 \times 10^{N-4}, \ldots]$
$\vdots$
各入力の桁について、係数は上の総和になるので、入力の $j$ 桁目の値と掛ける。その総和が答えになる。
ここで、各入力の桁にかかる係数を求めることになるのだが、頑張ると $Ο(N)$ で $j=1$ の場合を求めたあと、$Ο(1)$ で $j=2, 3, \ldots, N$ まで順番に求められる。
あとは、やるだけで OK。
1/28 Virtual Contest 解法一覧
https://kenkoooo.com/atcoder/#/contest/show/dfe2ad98-8e29-40b6-b570-7782091b5527
Section 1
1. ABC148 C - Snack
https://atcoder.jp/contests/abc148/tasks/abc148_c
最後のケースに $9999900000$ という巨大なケースが存在する。このケースから、$1$ から順に全ての数字を確認するのは不可能であることがわかる。
用意するお菓子の個数を $N$ とする。
$N$ 個のお菓子を $A$ 人に対して均等に配れるなら、$N$ は $A$ の倍数である。
また、$N$ 個のお菓子を $B$ 人に対して均等に配れるなら、$N$ は $B$ の倍数である。
このことから、$N$ は $A$ の倍数であり $B$ の倍数である必要がある。そのようなもののうち、最小のものを
最小公倍数
と呼んでいた記憶はないだろうか？
今回は、$A$ と $B$ の最小公倍数を求めればそれがそのまま題意を満たす。
なお、最小公倍数のことは一般に $\mathrm{LCM}$ (Least Common Multiple の略)と呼ばれる。同様に、これとセットとなる最大公倍数は $\mathrm{GCD}$ (Greatest Common Divisor) と呼ばれる。
「最小公倍数 java」などと検索すると GCD を求め、そこから LCM を求めるプログラムが見つかる。いったんそれを貼って提出すれば AC は得られる。
ただし、64 bit 整数型、Java では long を使う必要があるので注意。
以下に、その仕組みを説明する。
最小公倍数の求め方
$A$ と $B$ の $\mathrm{LCM}$ を $\mathrm{lcm}(A, B)$ と表記する。同様に、$A$ と $B$ の $\mathrm{GCD}$ を $\mathrm{gcd}(A, B)$ と表記する。
このとき、$\mathrm{lcm}(A, B) = A \times B \div \mathrm{gcd}(A, B)$ が成り立つ。
この証明には素因数分解などを用いたものがあるが、割愛する。
最大公約数の求め方
手計算だと
- ユークリッドの互除法
- $A$ と $B$ の約数をそれぞれ全部書き出す
といった方法がある。どちらもプログラム上で実現はするのだが、
- ユークリッドの互除法は、$Ο(\log(\mathrm{min}(A, B)))$
- 約数の全列挙は $Ο(\sqrt{A+B})$
という計算量の違いがある。
前者はたとえ $A, B \leq 10^{18}$ だろうが非常に高速 ($60$ 回程度の計算で終了する)なのに対して、後者は $A, B \leq 10^{18}$ だと $10^9$ ステップを超える計算が必要であり、低速である。
なお競プロでは、基本的にユークリッドの互除法をどこかに保存して持っておけばよく、空で書ける必要はない。
2. ABC124 B - Great Ocean View
https://atcoder.jp/contests/abc124/tasks/abc124_b
各 $i$ について題意を満たすか調べるのに、$H_1, H_2, \ldots, H_{i - 1}$ を調べなくてはならない。
しかし、$N \leq 20$ なので、合計で最大でも $200$ 回程度の計算しか必要ないため、一つ一つシンプルに調べればよい。
問題文に示された条件は、言い換えれば「自分より先頭側の要素に、自分より真に大きい値がない」ことであり、これは単純な < 演算子を用いて判定できる。
なお、直感に反するかもしれないが、オーダー表記の計算量は $Ο(N^2)$ である。よって、これが $N \leq 2 \times 10^5$ などの場合はこの解法だと TLE すると言える。
Bonus
$N \leq 2 \times 10^5$ でも解く方法が存在する。考えてみると考察力向上の一助となるはずだ。
3. M-Solutions プロコンオープン 2020 B - Magic 2
https://atcoder.jp/contests/m-solutions2020/tasks/m_solutions2020_b
まず、赤のカードに対して操作するべきではない。なぜなら、緑のカードに要求される数字が大きくなってしまうからだ。
そして、$A<B$ である場合はいつまでたっても魔術が成功しない。よって、まずは $A<B$ となるまで緑のカードに対して操作をすればよい。
$A<B$ を満たしたあとは、青のカードに対して操作をする。この間 $A<B$ である状態は必ず保たれるので、青のカードに対して限界まで操作をして $B<C$ になれば Yes と出力すればよい。
このように、一見操作順序などにいくつもの可能性がありそうな場合に、最も良い方法を $1$ 通り見つけてそれを行うことを貪欲法と呼ぶ。
Section 2
4. ABC064 C - Colorful Leaderboard
https://atcoder.jp/contests/abc064/tasks/abc064_c
危険なコーナーケースがサンプル上に存在しないので注意されたい。全員がレーティング $3200$ 以上の場合は適当に実装すると $0$ を出力するようなプログラムを作りかねない。
それにさえ気が付けば、後は区間数 $10 = σ$ として $Ο(σN)$ 程度でユーザを振り分けて map などで処理できる。
Bonus
わずかな改善だが $Ο(N \log σ)$ でも解ける。
5. ABC180 D - Takahashi Unevolved
https://atcoder.jp/contests/abc180/tasks/abc180_d
愚直にシミュレーションを行うことが出来ない。条件をうまく切り分けていくこととなる。
もちろん、$\times A$ と $+B$ ではいずれ後者の方が必ず変動量が小さくなるタイミングが来る。逆に、それまでは必ず前者の方が変動量は小さい。
ところでそのタイミングだが、そもそも $X=1$ の場合でも $\times A$ する回数は $\log_A{Y}$ 程度となるため、非常にその回数は少ない($60$ 程度)。
よって、$\times A$ する部分だけは愚直にシミュレートできる。
ただし、条件式は丁寧に構築すること。
6. ABC178D - Redistribution
https://atcoder.jp/contests/abc178/tasks/abc178_d
非常に難しいが、このような個数が多すぎる数え上げはまず $\mathrm{DP}$ で解けないかと考えてよい。
$\mathrm{DP}[x]$ は $S = x$ の時の解である、とすると
$A[0] = 1$ という初期条件と
$A[n] = Σ_{k=0}^{n-3} A[k]$ という漸化式を得られて、これは $Ο(N^2)$ で処理できて、解くことが出来る。
Bonus 1
$Ο(N)$ で解けるように漸化式を変形できる。これは difficulty $1000$ 程度なので挑戦する価値はあり。
Bonus 2
$Ο(\log N)$ でも解ける。difficulty $1600$ を超えるような難易度ではあるが。
2021年総括&2022年目標
白羽です。
2021 年が終わったので、2022 年になりました。
去年したこと
- AtCoder を始めた (2月 / ABC191)
- AtCoder をした
- AtCoder のレートが茶色になった (3月 / ABC196)
- AtCoder をした
- AtCoder のレートが緑色になった (5月 / ABC201)
- AtCoder をした
- AtCoder のレートが水色になった (10月 / ABC223)
- AtCoder をした
戦績
- Highest レーティング : $0$→$1381$ (Δ +$1381$)
- 現在値 : 1381
- Highest パフォーマンス : 0→$1889$ (Δ +$1889$)
- Rated 参加回数 : $0$→$37$ (Δ +$37$)
- Unique AC 数 : 0→$1140$ (Δ +$1140$)
- Rated Point Sum : 0→$268400$ (Δ +$268400$)
- Top-player Equivalent Effort : 0→$92177$ (Δ +$92177$)
- 約 $25$ 時間 $36$ 分
- コンテスト中に AC した問題の最高 Difficulty : 0→$1740$ (Δ +$1740$)
- AC した問題の最高 Difficulty : 0→$2514$ (Δ +$2514$)
- Highest レーティング : 0→$1481$ (Δ + $1481$)
- 現在値 : $1481$
- Rated 参加回数 : 0→$5$ (Δ +$5$)
振り返り
私はかつて「プログラマーとして世界クラスを目指す」という実現するための手段も検討のつかないようなざっくりした目標を抱えていました。
あの頃は間違いなく、プログラミングが好きだというだけで止まってしまいかねない危険な時期だったと思います。
そんな中、色々な経緯があって(直接的には Paiza から)競プロを始めました。正直、色の感覚も全然わからない状態からのスタートで、最初は C++ の環境を組まずコードテストでプログラムを書いていました。ABC198D を通した時の感動は未だに忘れられません。……E の方が簡単だったとか言わない。
正直、これほど自分にとって必要なものが揃っている世界があるとは思っていませんでした。
勉強すれば、それが結果になる。失敗とは勉強不足そのもの。ステップを踏んで学習すれば、かつてコンテスト本番に解けなかった問題も簡単に解けるようになる。コンテストは、余計な評価が加わらない実力勝負。それが自分にとってはとても快適な世界でした。
そして幸いにも、音ゲーという接点からフォロワーに競プロユーザーが数人いたり、競プロを始めてからも多くの強い方々と Twitter や Discord などで話す機会がありました。
身に余る難易度の問題で実装を詰まらせたときに助けを頂けたこともあります。
そういった方々の助けもあって、途中 $1$ カ月の休止(免許合宿)がありながら $1$ 年で(上方向の)色変を $3$ 回達成できました。
未だに「そういった方々」の誰にも勝てそうにないですが……。
今年の目標
- 4月、入社までにレーティング $1600$、またはそれを超える
- 2022年が終わるまでにレーティング $2000$、またはそれを超える
- 可能ならば、レーティング $2000$、またはそれを超えた状態で2022年を終える
- Div.3 を主としたバーチャルコンテストを積極的に行い、問題傾向に慣れる
- 速やかにレーティング $1600$ を超える
- 2022年が終わるまでにレーティング $2100$ を超える
コメント
精進量について一切書いていないのはわざとです。
目標のレーティングに対して、どのくらい問題を解けばいいのかが想像もつかないことが一因です。すなわち、最善を尽くすということです。
あと、これは精神的な問題ですが、ここで適当に次の色に上がるための精進量を見積もってしまうと、それが心理的な一種の「ゴール」になってしまい、それを達成した時に万が一次の色に上がっていない場合に、それが「負」になってしまう、という可能性を感じて……また、実際に他の競プロユーザーの動向から実感しています。
問題を解けば、Unique AC Count は増えます。でも、どこに「色が上がる程の実力を得た」と言えるボーダーラインが待っているかは自分にすら解ったものではない、と考えています。いや、少なくとも今の私にとってはそういうものです。
もしかしたら $1$ 年で $2$ 色上に上がる、というのも実は過酷な目標かもしれませんが、目測がつかないなりの結論なので、やべぇこと言ってんなとか思ってください。
ただし CodeForces に関しては問題傾向に慣れるためにも Div.3 を主としたバチャをそれなりの頻度でやっていく予定ではあります。
最後に
競プロは、いいぞ。
ちょっとした追記
物理好きさんという競技プログラマーがいます。AtCoder 2600 や TopCoder, CodeForces で赤に到達している凄い人です。
先ほど述べた通り音ゲー繋がりで知った方ですが、私はこの方を競プロにおいてかねてから目標としています。
まだまだ遠い目標です。しかも当たり前ながら現役なので、今この瞬間も私の目標は私から遠ざかっていっています。ですが、少なくともこの方が目標であるということが、今の私を AtCoder で黄やそれ以上を目指す理由のひとつです。
貴方のおかげで今年 $1$ 年競プロを続けられました。ありがとうございます。
いつか必ず追い付きます。
ARC107 D - Number of Multisets
この解法、結構時間かかるので流石に本番では選べないか……？
$N \leq 3000$ なので $Ο(N^2 log N)$ は通しにくい($Ο(N^3)$ でも枝刈すると通るらしいけど……)。
なるべく情報 $2$ 個で通らないだろうか？
考えたこと
- $\frac{1}{2^i}$ を選ぶ部分和 DP はキリがない
- 部分和といっても総和 $K$ にしか興味がないのでどうにかそれ以外の情報は捨てられないだろうか？→そもそも総和 $K$ の状態で集合の中身を弄る感じにしたい
- $1$ を分解して $\frac{1}{2} \times 2$ にすると長さが $1$ 増加してしまう。→長さ $1, 2, \ldots, N$ のそれぞれを考える DP に出来るか？
- $3$. における漸化式を考えると、$\frac{1}{2^i}$ を $\frac{1}{2^{i+1}}$ に分解するには $\frac{1}{2^i}$ がいくつあるかを知りたい。→求め方は $2$ 通り。
- $\frac{1}{2^{i-1}}$ を分解した結果生じた $\frac{1}{2^{i}}$ の個数を保持する
- $\frac{1}{2^{i-1}}$ をいくつ分解したかを保持する
- $4$-$1$. を吟味→$\frac{1}{2^i}$ を $\frac{1}{2^{i+1}}$ に分解すると $\frac{1}{2^{i+1}}$ の個数は $2$ の倍数になって飛び飛びになる。恐らくダメそう
- $4$-$2$. を吟味→計算量度外視なら出来そう。恐らく $Ο(N^3)$ になる。$Ο(N^2)$ にならないだろうか？→ $4$-$1$. ではダメだが、$4$-$2$. では累積和が出来るかも。ここで $4$-$2$. の採用が確定する。
- 情報を整理する。
- $dp[i][j] =$ 要素数 $i$ 個の状態から遷移して、 $j$ 個で総和 $K$ が達成できる多重集合の種類数
7 ~ 8 が大分ぶっ飛んでいるのでより詳細に説明する。
だいたいの方針としては「ある数字 $f$ を $\frac{f}{2}$ に分解する」ことを DP 上で漸化式として表現しようとしている。
そのため、初期状態は $dp[0][K] = 1$ となる。
そのうえで、複数個の分解を行うことを累積和でどうにかして高速に処理しようとした。つまり、ある状態から分解して得られる状態を一括で遷移するようにするのだ。
しかし、分解できる数は $1$ 種類のみであり、そうなるように処理しなければ論理が破綻する。そのため「今の状態で分解が有効な数がいくつあるか？」を保持しなくてはならなくなる。
例えば、${1, 1, 1}$ を分解して ${1, 1, \frac{1}{2}, \frac{1}{2}}$ を得たとする。次に分解が有効なのは $\frac{1}{2}$ のみであり、$1$ を分解することは出来ないようにしたい。なぜなら、そのような分解は ${1, 1, 1}$ から ${1, \frac{1}{2}, \frac{1}{2}, \frac{1}{2}, \frac{1}{2}}$ に分解することと同値なためである。
ここで、分解が有効な数が具体的に何なのかまでは保持しなくてよいことに注目されたい。それが幾つであろうと $\frac{1}{2}$ をかけた数 $2$ 個に分解されるのみである。
よって状態は要素数が以前いくつだったか、そして分解によっていくつになったかだけに圧縮できてしまうのではないかと考える。
次に、累積和について考える。
要素数が $i$ である状態から $dp[i][i+1, i+2, \ldots, i+x]$ に遷移するようにすると、気持ちとしては前の次元のほうが固定されるので考えやすい。
これで $dp[i]$ から $dp[?]$ に遷移する前に累積和すれば正当な値になる。
最後に漸化式と初期状態を考える。
初期状態は先ほども述べたように $dp[0][K] = 1$ となるが、追加があるので後述する。
かつて要素数 $i$ だった状態から、なんらかの数を分解して要素数 $j$ になったとする。この状態で分解が有効な要素はいくつあるだろうか？
例：
${1, 1, 1}$ を分解して ${1, 1, \frac{1}{2}, \frac{1}{2}}$ を得たとする。次に分解が有効なのは $\frac{1}{2}$ のみである。この場合は、分解が有効な要素は $2$ 個ある。
ここで逆に、分解が無効な要素はいくつあるかを考える。
$i$ 個から $j$ 個に遷移したということは差分が $j-i$ 個であるので、$j-2(j-i)$ を解けば解が得られる。解は $2i-j$ となる。
ここから分解が有効な要素数を求められる。$j-(2i-j) = 2j-2i$ 個となる。
ここで、$x$ 個の分解が無効な数と $y$ 個の分解が有効な数について、全ての分解個数を試すと分解結果の個数は区間 $[x+y+1, x+2 \times y]$ になる。
このことから、分解個数の最大値は $2i-j+2(2j-2i)$ となり、整理すると $3j-2i$ となる。
ちなみに $x+y$ とは $j$ のことなので、累積和を考慮した漸化式は以下の通り。
$$dp[j][j+1] += dp[i][j]$$
$$dp[j][a] -= dp[i][j] (a=3j-2i+1, 0 \leq a \leq N)$$
しかし、唯一この漸化式が狂う場合が存在する。$i=0$ の場合である。
この場合に対処するために、$i=K$ の場合を最初に埋め込んでおく。
初期条件(追加分を含む、累積和を考慮)：
$$dp[0][K]=1$$
$$dp[K][K+1]=1$$
$$dp[K][2K+1]=-1(2K+1 \leq N)$$
以上、これを求めた結果の
$$Σ_{i=0}^{N} dp[i][N]$$
が解となる。
ABC057D - Maximum Average Sets
自分と同じ解法で通してる解説がなくて「？」になったのでやり方を書き残します。
とりあえず「組み合わせにおける個数」「組み合わせに含まれる品物の数」がわかればいいです。なので部分和 dp に個数の軸を加えて
$dp[i][j][k]$ = $i - 1$ 番目までの要素で $j$ 個選び、なおかつ $k=1$ ならば $i$ 番目の要素を選ぶ時の総和の最大
として $dp[n][i][j] (a \leq i \leq b, j \in \{0, 1\})$ を拾っていきます。
ここで、最大値と一緒にその個数も計算することが可能です。
$cnt[i][j][k]$ = $dp[i][j][k]$ に対応する選び方の総数
こちらの更新がちょっとめんどくさいのでこの解法を捨てた方もいるかもしれません。やり方としては ABC211D と同じ発想で「$dp[i][j][k]$ は今の値より小さい値に更新されることは無い」ことを利用します。すなわち
- $dp$ を更新しようとするときに値がより大きい値に更新されるなら、$cnt$ は更新元の値と同じ値になる
- そうでなく、$dp$ の値が完全に等しいならば、$cnt$ は更新元の値との和になる
漸化式でいえば
$cnt[i + 1][j + 1][1] = cnt[i][j][k] (dp[i + 1][j + 1][1] < dp[i][j][k] + v[i])$
$cnt[i + 1][j + 1][1] += cnt[i][j][k] (dp[i + 1][j + 1][1] = dp[i][j][k] + v[i])$
$cnt[i + 1][j][0] = cnt[i][j][k] (dp[i + 1][j][0] < dp[i][j][k])$
$cnt[i + 1][j][0] += cnt[i][j][k] (dp[i + 1][j[0] = dp[i][j][k])$
このように最後まで $dp$ を回すことで、各選ぶ個数について最大ではない組み合わせを全部排除できます。
あとは [(総和 $÷$ 選ぶ個数), (選び方の通り数)] となる map を作って答えます。
コード (解説中の $dp$ が $mx$ で $cnt$ が $dp$ になってます、すみません)
ABC142E - Get Everything
https://atcoder.jp/contests/abc142/tasks/abc142_e
最近、水色問題を頑張っています。
面白い問題があったので貼り付けますが、割と典型な気がするので特に需要は無いです。
問題概要
鍵がたくさんあり、それぞれに値段と開けられる宝箱が決まっているので、全ての宝箱を開けられる鍵の組み合わせの内で値段総和の最小を答える問題です。
考え方
宝箱の個数が $\leq 12$ なので、宝箱の集合はbitで表現できます。
ただ、選ぶのは鍵なので宝箱を全探索は出来ません。
ここでbit全探索という選択は無くなりますが、bitを使う前提で他の手段を考えるとbit DPが思い当たります。
鍵を選ぶか選ばないかは何とかするとして、開けられる宝箱の一覧を添字で管理できるのではないかと考えられます。
そして、これは選ぶか選ばないかのDPでよくありますが、$i$ 番目までの要素に対する何らかの計算結果が $j$ = $v$ で表せる時、配列を $dp[i][j] = v$ となるように作ることで
$dp[i + 1][j] += dp[i][j]$
$dp[i + 1][j$ に何かの計算を行う $] += dp[i][j]$
または、これらに準ずる漸化式
で $Ο(n \max{j})$ ($n$ は全ての要素数) 程度の計算量で解ける場合が非常に多いです。
今回はbitで宝箱の集合を管理するので、$i$ が鍵で $j$ が宝箱の集合とすると
$dp[i+1][j] = \min(dp[i+1][j], dp[i][j])$
$dp[i+1][j \lor $ 鍵 $i$ が開けられる宝箱の集合 $] = \min($ 左辺 $, dp[i][j] + $ 鍵 $i$ の価格 $)$ (ここで、$\lor$ はbitwise or)
という漸化式を立ててループを回すことでこの問題を解けます。
ここで初期条件は $dp[0][0] = 0$ でそれ以外は $10^9$ とかにしておけばよいです。価格の総和はどう頑張っても $M \cdot \max{a}$ (厳密にはもっと少ない)となります。
また、dp配列の大きさは $(m + 1, $ 1<<n $)$ であり、ループ終了後答えがあるのは $dp[m][$ (1<<n)-1 $]$ (0-indexed)です。
計算量は特に工夫しなくても余裕ですが、先にそれぞれの鍵について開けられる宝箱の集合をbit値にしてしまえばbitwise orを掛けるだけになって高速になります。
そのような処理をすれば $Ο(2^NM)$
そうでなくとも $Ο(2^NNM)$ を達成します。
