この記事は 【AtCoder】初中級者が解くべき過去問精選 100 問を緑色コーダーが C++ で解いてみた の子記事です。お読みになる前に親記事をご確認ください。
15. AtCoder Beginner Contest 145 C – Average Length
N \leq 8 より next_permutation で順列を全部列挙しても、列挙のみの計算量は O(N!) = 8! = 40320 程度です。
各順列ごとの経路の計算は O(N) かかります。全体の計算量は O(N N!) = 10^6 程度で実行時間制限を違反せずに求解できます。
距離の計算には hypot, 出力の際の桁数の調整には setprecision が利用できます。
AtCoder の解説 にあるように町から町への移動の出現回数を予め求めておく方法もあります。
町を訪れる N! の経路のうち、町 i から町 j へ移動する経路は (N – 1)! 通りです。考え方としては、一度、町 i, j を同じ町だとみなして、N – 1 個の町を並べ替えた後、再び i, j に分けると考えます。これは i, j によらずに決まるため、先ほどの順列全探索の際にすべての町から町への移動は (N – 1)! 回発生したことになります。
町 i と町 j の距離を d_{ij} とおくと N! 通りの経路の長さの総和は下記の式で表せます。
\sum_{i = 1}^{N} \sum_{j \neq i} (N – 1)! \, d_{ij}
d_{ij} = d_{ji} であることを用いて N! 通りの平均は次の式で求められます。
\frac{2}{N} \sum_{i = 1}^{N} \sum_{j = i + 1}^{N} d_{ij}
上記の式にしたがって計算する場合、計算量は O(N^2) で済みます。
16. AtCoder Beginner Contest 150 C – Count Order
N \leq 8 より next_permutation で順列を全部列挙しても 列挙のみの計算量は O(N!) = 8! = 40320 程度です。
next_permutation は辞書順に列挙するため、列挙のたびに順位を数えておき、
- 順列 P と列挙した順列が一致した時 a に順位を代入
- 順列 Q と列挙した順列が一致した時 b に順位を代入
として、a, b を計算した後に |a – b| を計算すれば答えとなります。順列と P, Q の比較が O(N) の計算量のため、全体の計算量は O(N N!) = 10^6 程度です。
17. ALDS_13_A – 8 クイーン問題
クイーンの配置を長さ 8 の順列で表現することを考えます。具体的には順列 P と (0, P_0), (1, P_1), \dots , (7, P_7) にクイーンを配置することを対応させます。第一成分が行で第二成分が列です。クイーンの配置の候補の数、すなわち順列の個数は 8! = 40320 しかないため、順列全探索で解くことを考えます。
順列で表現するメリットは縦に複数のクイーン、横に複数のクイーンが並ぶことがないため、要求されている配置か否かの判定が下記 2 つの確認で十分になる点です。
- クイーンが k 個の指定の位置に配置されているか。
- 斜めに複数のクイーンが並んでいないか。
1 については、k 個の座標 (r, c) が与えられているため、1 つづつ確認します。
2 については、任意の i, j に対し、(i, P_i) と (j, P_j) が斜めに並んでいないか確認します。斜めに配置される場合 (i, P_i) と (j, P_j) の上下の差 j – i と左右の差 P_j – P_i は等しい (左下右上の並び) か、-1 倍 (左上右下の並び) になるため、それを確認します。
1 つの順列に対し、1 の確認は k \leq 8 回、2 の確認は 8 \times 7 \div 2 = 28 回、計算を繰り返します。全体の計算量はおよそ (8 + 28) \times 8! = 10^6 程度で実行時間制限に違反しません。
この問題は深さ優先探索でも解けます。行の番号を深さとして、1 行目から 8 行目まで順にクイーンの配置を決めていきます。単純に列挙しても 8^8 = 16777216 なのでおそらくギリギリ間に合うと思いますが、下記の枝刈りができます。
- クイーンを置いた列を覚えておき、縦にクイーンが並ぶことを避ける。
- 順列全探索では自然と回避できたケースです。
- クイーンを置くたびに斜めに複数のクイーンが並んでいないか確認する。
- 配置が決まっている行については、指定の列にしかクイーンを置かない。
2 は探索の深さを進めるたびに (深さ – \ 1) 回の計算が必要です。私の粗い計算量見積能力では並べ終わった後に斜めの確認するより計算量は増えてしまいますが、探索が浅いうちに枝を刈ることができるため、有効だろうと考えています。
