先週の土曜日に実施された AtCoder Beginner Contest 415 に参加しました。結果は A・Bの2完。
うーん……前回に引き続き、2週連続で2完という悔しい結果となってしまいました。
C問題について
C問題は、コンテスト終了35分前にサンプルが通り、「これはいける！」と思って提出したのですが……TLE（時間切れ）。
その後、処理時間の改善を試みたものの、どうしてもTLEが取れず、最終的にACには至りませんでした。
問題の概要（私の理解）
複数の薬品があり、それらを1つずつ混ぜていき、すべての薬品が混ざった状態を作ることが目標の問題です。
ただし、薬品同士には安全な組み合わせと危険な組み合わせがあり、その情報が 2進数で与えられます。
例えば、3種類の薬品に対して 0010010 のような2進数が与えられた場合、
3番目と6番目にビットが立っていることから、それぞれの内容は以下の通り：
-
3番目 →
011（= 薬品1と2の組み合わせが危険） -
6番目 →
110（= 薬品2と3の組み合わせが危険）
この場合、薬品1 → 3 → 2の順で混ぜれば、すべての薬品を安全に混ぜることが可能です。
私のアプローチ：順列全探索 → TLE地獄
「これは順列全探索でいけるのでは？」と思い、C++の next_permutation を使ってすべての並びを試す作戦に出ました。
しかし……
実装の壁：18の階乗（18!）問題
薬品の種類は最大18種類。
順列の総数は 18! ≒ 6 × 10¹⁵ 通りになります。
冷静に考えれば、これは到底2秒以内に終わる計算量ではないですね。
重複する順列をスキップするよう工夫はしましたが、焼け石に水。
結局、計算量の見積もりを誤ったことが敗因でした。
解説で得た学び：実はBFSで高速に解ける到達問題だった！
公式解説動画（YouTube） を確認してみたところ、
この問題は実は、**「グラフの到達問題」**として考えることで、**BFS（幅優先探索）**で効率よく解ける構造になっていました。
グラフ構造のイメージ
初期状態（すべて未混合）を 000、最終状態（すべて混合）を 111 とし、
1つずつビットを立てていくことで状態を遷移させるという考え方です。
これはちょうど、立方体の1点から対角点まで進むようなグラフの探索問題として捉えることができ、
順列全探索よりもはるかに高速に処理できます。
方法①：BFS（幅優先探索）
解説では、BFSを使って状態の遷移を1ステップずつ進めていく手法が紹介されていました。
到達した状態からのみ探索を続けることで、無駄な探索を減らす点がポイントです。
また、以下のような実装も参考になりました。
rep(i, n){
int nt = t | 1 << i; // i番目の薬品を混ぜてみる（ビットを立てる） if(t == nt) continue; // 状態に変化がなければスキップ } このように、**「今の状態に1つ薬品を追加する」**という遷移をグラフの辺として扱うことで、
順列全探索とは比べものにならない効率で解けるようになります。
方法②：ビットDP
もう一つの解法は、ビットDPによる実装でした。
こちらも考え方自体はシンプルでしたが、コンテスト中に思いつくのは難しかったかもしれません。
今回の反省と感想
-
順列全探索が通らない計算量であることを、もっと早く見抜くべきでした。
-
本質はグラフの最短経路問題であり、BFSによる高速化が解決のカギでした。
-
状態遷移をビット演算で表現するテクニックは、今後の実装にも活かせそうです。
最後に
今回のパフォーマンスは 429、レートは 544（-13）。
少し下がってしまいましたが、悔しさを学びに変えて、次回もめげずに頑張ります！