ABC 401-500/ABC415C - Mixture - 競技プログラミング用 知識集積所【7/20更新】

---

問題

ABC415C
C問題に不相応な難問なので注意

必要知識

B以下レベルの内容は省略

• bitDP（未作成）
  • 動的計画法
  • bit全探索（未作成）

考え方

いわゆるbitDP（未作成）。
各状態についてbit全探索（未作成）の要領で調べていく過程で動的計画法を用いる。

入力例の最初のテストケースの場合、以下のように動的計画法を進める。
（左から5列は添字に情報があり、右から2列目はsに情報があるので、右端欄だけ継承すればよい）

とりあえず、問題で与えられる情報の整理。

状態番号（十進）	状態番号（二進）	薬品3	薬品2	薬品1	安全？	可能？
0	000	x	x	x	o	o
1	001	x	x	o	o	?
2	010	x	o	x	o	?
3	011	x	o	o	x	?
4	100	o	x	x	o	?
5	101	o	x	o	o	?
6	110	o	o	x	o	?
7	111	o	o	o	o	?

左の方の5列は、普通にbit全探索（未作成）の要領で埋めたもの。
黄色い部分が、文字列sによる情報。
赤い部分は、問題に書いてないが少し考えれば明らかなこと。

次に、状態1。
まず、状態1そのものが安全であることを確認。
そして、これは薬品1のみ入れた状態なので、最後に混ぜる薬品の選択肢は薬品1の1択。
そこで、

• 状態1から薬品1を抜いた、状態0は作れるかどうか？

を見て、状態1が作れるかどうかを決定する。

状態番号（十進）	状態番号（二進）	薬品3	薬品2	薬品1	安全？	可能？
0	000	x	x	x	o	o
1	001	x	x	o	o	o
2	010	x	o	x	o	?
3	011	x	o	o	x	?
4	100	o	x	x	o	?
5	101	o	x	o	o	?
6	110	o	o	x	o	?
7	111	o	o	o	o	?

状態2も同様に、最後に入れる薬品の選択肢は薬品2の1択。

状態番号（十進）	状態番号（二進）	薬品3	薬品2	薬品1	安全？	可能？
0	000	x	x	x	o	o
1	001	x	x	o	o	o
2	010	x	o	x	o	o
3	011	x	o	o	x	?
4	100	o	x	x	o	?
5	101	o	x	o	o	?
6	110	o	o	x	o	?
7	111	o	o	o	o	?

状態3は、そもそも危険なので、作れない。

状態番号（十進）	状態番号（二進）	薬品3	薬品2	薬品1	安全？	可能？
0	000	x	x	x	o	o
1	001	x	x	o	o	o
2	010	x	o	x	o	o
3	011	x	o	o	x	x
4	100	o	x	x	o	?
5	101	o	x	o	o	?
6	110	o	o	x	o	?
7	111	o	o	o	o	?

状態4は、状態1や2と同様。

状態番号（十進）	状態番号（二進）	薬品3	薬品2	薬品1	安全？	可能？
0	000	x	x	x	o	o
1	001	x	x	o	o	o
2	010	x	o	x	o	o
3	011	x	o	o	x	x
4	100	o	x	x	o	o
5	101	o	x	o	o	?
6	110	o	o	x	o	?
7	111	o	o	o	o	?

状態5。
まず、状態5そのものが安全であることを確認。
そして、これは薬品1と薬品3を入れた状態なので、最後に混ぜる薬品の選択肢は薬品1と薬品3の2択。
そこで、

• 状態5から薬品1を抜いた、状態4は作れるかどうか？
• 状態5から薬品3を抜いた、状態1は作れるかどうか？

を見て、状態5が作れるかどうかを決定する。

状態番号（十進）	状態番号（二進）	薬品3	薬品2	薬品1	安全？	可能？
0	000	x	x	x	o	o
1	001	x	x	o	o	o
2	010	x	o	x	o	o
3	011	x	o	o	x	x
4	100	o	x	x	o	o
5	101	o	x	o	o	o
6	110	o	o	x	o	?
7	111	o	o	o	o	?

状態6は状態5と同様。

状態番号（十進）	状態番号（二進）	薬品3	薬品2	薬品1	安全？	可能？
0	000	x	x	x	o	o
1	001	x	x	o	o	o
2	010	x	o	x	o	o
3	011	x	o	o	x	x
4	100	o	x	x	o	o
5	101	o	x	o	o	o
6	110	o	o	x	o	o
7	111	o	o	o	o	?

状態7は3択になるが、やはり同様。
作る方法が少なくとも1つあれば、それは作れる。

状態番号（十進）	状態番号（二進）	薬品3	薬品2	薬品1	安全？	可能？
0	000	x	x	x	o	o
1	001	x	x	o	o	o
2	010	x	o	x	o	o
3	011	x	o	o	x	x
4	100	o	x	x	o	o
5	101	o	x	o	o	o
6	110	o	o	x	o	o
7	111	o	o	o	o	o

この手順をコードにすればいいだけ。
……ではあるが、bit全探索（未作成）のコードと動的計画法のコードが複雑に絡み合うことになるため、実際に書くのはかなり大変。
初めてのbitDP（未作成）だと、コーディングだけで1日かかるかもしれない。

これ、本当にC問題？

解答例

解答例

注意点

別解