この記事は 【AtCoder】初中級者が解くべき過去問精選 100 問を緑色コーダーが C++ で解いてみた の子記事です。お読みになる前に親記事をご確認ください。
49. DPL_2_A – 巡回セールスマン問題
順列全探索で解こうとすると \Omega((|V| + 1)!) = 10^{13} 程度の計算量となり、間に合わなそうです。
ビット演算 (bit 演算) の使い方を総特集！ 〜 マスクビットから bit DP まで 〜 の「巡回セールスマン問題」に類題とその解説が記載されています。基本的には、この解説を参考にすれば求解できます。ただし、類題と異なり閉路の最短経路を求めるため、初期値と最短経路の距離の表現は変更します。
類題の解説と同様に \mathrm{dp}[S][v] を全体集合 V の部分集合 S について最後が v であるという制約の下で順序を最適化したときの S の中での最短経路の距離とします。
閉路を求めるため、始点はどこでも良いのですが、後述の最短経路の距離の表現のために一点を始点と決めます。ここでは番号 0 の点を始点とします。\mathrm{dp}[\{0\}][0] を 0 で初期化します。その他の \mathrm{dp}[S][v] については実現不可能な場合を表す -1 で初期化します。
\mathrm{dp}[V][v] は以下を満たす経路の距離の最小値になります。
- すべての点を一度通る。
- 始点 0, 終点 v.
v から 0 への辺が存在するとき、辺の距離を d_{v0} とおきます。\mathrm{dp}[V][v] + d_{v0} はすべての点を一度通る閉路の距離です。このような閉路のうち最短の閉路の距離が答えとなるため、答えは \min_{v} (\mathrm{dp}[V][v] + d_{v0}) です。
計算量は \mathrm{dp}[S][v] の更新に O(|V|) かかるため、全体では O(2^{|V|} |V|^2) = 10^7 程度で時間制限を満たします。
別の考え方として、ある点を始点と終点の 2 点に分ける考え方もあります。
番号 |V| の点を用意します。番号 0 の点を 2 点に分けることを考えます。終点が 0 である辺の終点を番号 |V| の点に変更します。このとき、0 から |V| への経路は元のグラフの閉路に対応します。あとは解答例 1 と同様に \mathrm{dp}[\{0\}][0] を 0 で初期化したあと bit DP を行います。\mathrm{dp}[V \cup \{|V|\}][|V|] が答えとなります。
計算量はグラフに 1 点増えただけであるため、変わらず O(2^{|V|} |V|^2) です。
50. Square869120Contest #1 G – Revenge of Traveling Salesman Problem
順列全探索だと \Omega((N + 1)!) の計算量となり、N \leq 16 であるため、実行時間制限に違反しそうです。
bit DP で解くことを考えます。最短経路の距離については問題 49 の巡回セールスマン問題を bit DP で解く方法に time_i 以内に道路を渡り切れるかの判定を追加すれば求められます。
場合の数については距離とは別の動的計画法の表を用意します。
\mathrm{cnt}[S][v] を建物の集合 \{1, \dots, N\} の部分集合 S について S 内の各建物を一度訪問し、最後に v を訪問する経路のうち、最短時間の経路の本数とします。
距離 \mathrm{dp}[S][s_i] + d_i と \mathrm{dp}[S\cup\{t_i\}][t_i] を比較する際に以下の更新を行います。
\mathrm{dp}[S][s_i] + d_i = \mathrm{dp}[S\cup\{t_i\}] のとき、これまでの最短経路の候補と同じ距離の経路が \mathrm{cnt}[S][s_i] だけ増えるため、新しく増えた経路の数を足し合わせます。
\mathrm{cnt}[S\cup\{t_i\}][t_i] = \mathrm{cnt}[S\cup\{t_i\}][t_i] + \mathrm{cnt}[S][s_i]
\mathrm{dp}[S][s_i] + d_i<\mathrm{dp}[S\cup\{t_i\}] のとき、これまでの最短経路の候補は最短経路ではないことがわかるため、新しい最短経路の候補の数を記録します。
\mathrm{cnt}[S\cup\{t_i\}][t_i] = \mathrm{cnt}[S][s_i]
\mathrm{cnt}[S][v] は \mathrm{cnt}[\{1\}][1] のみ 1 で初期化し、残りは 0 で初期化します。
建物 1 を始点と終点の 2 点に分ける場合は \mathrm{dp}[\{1, \dots, N + 1\}][N + 1] と \mathrm{cnt}[\{1, \dots, N + 1\}][N + 1] が答えになります。
計算量は O(2^N N^2) = 10^8 程度です。実行時間制限に間に合います。
51. JOI 2014 予選 4 – 部活のスケジュール表
一人の部員の N 日間の出欠の場合の数は 2^N です。3 人の場合は 2^{3N} です。各場合を列挙して実行可能な予定であるかを確認する手法は \Omega(2^{3N} N) の計算量です。実行時間制限に違反しそうです。
前日の部活の予定 (参加者一覧) が分かれば、当日の予定の候補の成立可否が判定できます。そのことをふまえて動的計画法で解くことを検討します。
i を日数、S を部員の集合として \mathrm{dp}[i][S] を i 日目までの予定のうち、以下を満たす予定の場合の数とします。
- 各活動日に少なくとも一人の前日の参加者が参加します。(鍵の管理)
- 各活動日に当日の責任者が参加します。
- 第 i 日の活動日の参加者の集合は S です。
a_i を i 日目の活動日の責任者として以下の更新式を立式できます。
\mathrm{dp}[i + 1][S] = \begin{cases}
\sum_{V \cap S \neq \empty} \mathrm{dp}[i][V]&(a_i \in S) \\
0&(a_i \notin S)
\end{cases}
最初は J 君が部室の鍵を持っているため、\mathrm{dp}[0][{\text{‘J’}}] を 1 で初期化して、その他の \mathrm{dp}[0][S] を 0 で初期化します。i \geq 1 となる \mathrm{dp}[i][S] については更新を for 文を使って行うのであれば 0 で初期化するのが無難です。
\sum_{S} \mathrm{dp}[N][S] を 10007 で割った余りが答えになります。オーバーフローを防ぐため、\mathrm{dp}[i][S] の更新の際に右辺を 10007 で割った余りで更新します。
部員は 3 人しかいないため、計算量は O(N) = 10^3 程度です。定数倍を考慮しても 10^5 程度です。実行時間制限を満たして求解できます。
52. JOI 2017 予選 4 – ぬいぐるみの整理
順序全探索を行う場合、計算量が \Omega(M! N) = 10^{24} 程度になるため、実行時間制限に違反しそうです。
O(2^M) = 10^6 程度なので、ビット演算による部分集合の計算はできそうです。ぬいぐるみを並べる順序に依存しない性質を探します。
\mathrm{cnt1}[j][i] を左から i 番目までの区画に置いてある種類 j のぬいぐるみの個数とします。ぬいぐるみの種類の集合を V, その部分集合を S とおきます。\mathrm{cnt2}[S] を S に属する種類のぬいぐるみの個数とします。p_i \in V として、左から種類 p_1,p_2, \dots , p_i の順にぬいぐるみを並べるとき、C_{p_1 \dots p_i} を \mathrm{cnt1}[\{p_1,p_2, \dots , p_i\}] 番目までの区画から取り出すぬいぐるみの個数の最小値とします。便宜上 S_{i} \coloneqq \{p_1,p_2, \dots , p_i\}, S_{i+1} \coloneqq \{p_1, \dots , p_i, p_{i+1}\} とおきます。C_{p_1 \dots p_i p_{i + 1}} は以下の 1, 2 の和になります。
- 第 \mathrm{cnt2}[S_i] 番目までの区画 (区間 1 とします) に p_1, p_2, \dots, p_i を並べるために区間 1 から取り出すぬいぐるみの個数
- 第 \mathrm{cnt2}[S_i] + 1 番目から第 \mathrm{cnt2}[S_{i+1}] 番目までの区画 (区間 2 とします) に種類 p_{i+1} のぬいぐるみを並べるために区間 2 から取り出すぬいぐるみの個数
1 は定義から C_{p_1 \dots p_i} です。2 は区間 2 にある種類 p_{i+1} 以外のぬいぐるみの個数です。C_{p_1 \dots p_i p_{i + 1}} は以下の式のように書けます。
\begin{aligned}
c[p_{i+1}][S_i] &\coloneqq (\mathrm{cnt2}[S_{i+1}] – \mathrm{cnt2}[S_i]) – (\mathrm{cnt1}[p_{i+1}][\mathrm{cnt2}[S_{i+1}]] – \mathrm{cnt1}[p_{i+1}][\mathrm{cnt2}[S_i]]) \\
&= \mathrm{cnt1}[p_{i+1}][N] – (\mathrm{cnt1}[p_{i+1}][\mathrm{cnt2}[S_{i}] + \mathrm{cnt1}[p_{i+1}][N]] – \mathrm{cnt1}[p_{i+1}][\mathrm{cnt2}[S_i]]) \\
\end{aligned}
C_{p_1 \dots p_i p_{i + 1}} = C_{p_1 \dots p_i} + c[p_{i+1}][S_i]
c[p_{i+1}][S] は S 内の種類の並べる順番によらずに決まります。そこで bit DP で解くことを検討します。
\mathrm{dp}[S] を S に属する種類のぬいぐるみを左から並べるとき、\mathrm{cnt2}[S] 番目までの区画から取り出すぬいぐるみの個数の最小値とします。C_{p_1 \dots p_i} についての考察から以下の更新式を立式できます。
\mathrm{dp}[S] = \min_{j \in S} (\mathrm{dp}[S \setminus \{j\}] + c[j][S \setminus \{j\}])
初期化は \mathrm{dp}[\empty] は 0 で初期化し、それ以外の \mathrm{dp}[S] は取り出すことのできるぬいぐるみの個数の最大値より大きい値で初期化します。例えば N + 1 で初期化します。
\mathrm{dp}[V] が答えになります。
\mathrm{cnt1}[j][i] の前処理に O(MN), \mathrm{cnt2}[S] の前処理に O(2^M), bit DP に O(2^M M) かかるため、計算量は O(MN + 2^M M) = 10^8 程度です。実行時間制限に違反せず、求解できます。
\mathrm{cnt2}[S] は \mathrm{cnt1}[j][N] から O(M) で計算できるため、\mathrm{dp}[S] を更新する際に都度算出してもよいです。その場合の計算量も O(MN + 2^M M) になります。
