この記事は 【AtCoder】初中級者が解くべき過去問精選 100 問を緑色コーダーが C++ で解いてみた の子記事です。お読みになる前に親記事をご確認ください。
元記事 で「圧縮」と呼んでいる処理は「連長圧縮」あるいは「Run Length 圧縮」と呼ばれる処理です。圧縮については以下の記事が参考になります。
87. JOI 2008 本選 1 – 碁石ならべ
長さ N の配列を使い、左から i 番目の要素の色を記録して、シミュレーションする場合、計算量は \Omega(N^2) = 10^{10} 程度になります。実行時間制限に違反しそうです。
\Omega(N^2) かかる理由は i が偶数かつ新しく置く碁石と右端の碁石の色が異なる場合、最悪 \Omega(N) の碁石の置き換えの処理が発生するためです。各時点の更新を O(1) でできる方法を探します。
連長圧縮 でテーブルの碁石の並びを管理すると各時点の更新を O(1) で計算できます。
連長圧縮後のデータ V を (c, l) の配列とします。ここで c は碁石の色、l は連続する c 色の碁石の個数とします。
右端の碁石の色の判定
V の最後の要素の c を確認すれば右端の碁石の色はわかります。
場合 1 i が奇数のとき
新しく置く碁石と右端の碁石の色が同じ場合は V の最後の要素 (c, l) を (c, l + 1) に変更します。
異なる場合は c を新しく置く碁石の色として V の末尾に (c, 1) を追加します。
場合 2 i が偶数のとき
新しく置く碁石と右端の碁石の色が同じ場合は V の最後の要素 (c, l) を (c, l + 1) に変更します。
異なる場合は次のように処理します。c を新しく置く碁石の色、V の最後の要素とその 1 つ手前の要素をそれぞれ (c_1, l_1), (c_2, l_2) とします。c \neq c_1, c = c_2 であるため、l_1 個の c_1 色の碁石を c = c_2 色の碁石に変更します。そのため、V の末尾の要素 (c_1, l_1) を削除し、削除後の最後の要素 (c_2, l_2) を (c_2, l_2 + l_1 + 1) に変更します。
いずれの処理も O(1) でできます。また、最後に白色の碁石を数える処理は O(N) でできるため、全体の計算量は O(N) = 10^5 程度となります。実行時間制限に違反せずに解答できます。
89. JOI 2013 本選 1 – 電飾
長さ N の配列を使って、東から i 番目の電球の明かりを管理し、機械で明かりを操作する区間を全探索する場合、操作後の最大の交互列の探索をしゃくとり法のように行ったとしても \Omega(N^3) = 10^{15} 程度かかります。実行時間制限に違反しそうです。
\{r_i\}_{i=1}^N を操作前の電飾とします。電飾を東から順に交互列 \{r_i\}_{i = i_1}^{i_2 – 1}, \{r_i\}_{i = i_2}^{i_3 – 1}, \dots, \{r_i\}_{i = i_j}^{N} に分割します。
機械を操作した後の最大の交互列の東の端は i_1, i_2, \dots, i_j のいずれかになります。もし i_{k}<i_0<i_{k + 1} となる i_0 が最大の交互列の東の端になると仮定します。もし機械の操作によって r_{i_0} を変化させたとすると \{r_i\}_{i=i_{k}}^{i_{k+1} – 1} が交互列であることから i_{k} から i_{0} – 1 までの電球もあわせて変化させると i_{0} – i_{k} だけ交互列を長くできます。また、r_{i_0} を変化させない場合も \{r_i\}_{i=i_{k}}^{i_{k+1} – 1} が交互列であることから、i_{0} – i_{k} だけ交互列を長くできます。いずれの場合も i_{0} が最大の交互列の東の端になることに矛盾します。
同様に考えると、機械を操作した後の最大の交互列の西の端は i_2 – 1, i_3 – 1, \dots, N のいずれかになります。
以上から、操作前の各交互列は、操作後の最大の交互列に含まれるか、操作後の最大の交互列と互いに素になるかのどちらかになります。
操作後の最大の交互列は連続した電球の列であるため、操作後の最大の交互列に含まれる操作前の交互列は連続でなければなりません。また、4 つ以上の交互列が含まれることはありません。4 つ以上の交互列が含まれると仮定すると、2 つ以上の連続しない交互列の電球の明かりを変更する必要があります。機械で変更できるのは連続した電球の列の明かりであることに矛盾します。3 つの交互列の場合は 2 つめの交互列の明かりを操作によって変更すれば 1 つの交互列に変更することができます。
よって、操作前の連続する 3 つの交互列の長さの和の最大値が答えになります。ただし、操作前の交互列が 1 つまたは 2 つの場合は電飾全体を交互列にできるため、答えは N になります。
操作前の交互列の列を連長圧縮の要領で長さを値とする配列として管理すると、操作前の連続する 3 つの交互列の長さの和を O(1) で計算できます。そのため、最大値は O(N) = 10^5 程度で見つけることができます。実行時間制限に違反せずに解答できます。
90. Square869120Contest #5 B – Emblem
問題文の「接してもよいが, どの円も他の円と交わるまたは含んではならない」を言い換えると、「任意の 2 つの異なる円に対し、半径の和は中心間の距離以下である」となります。
しっくりこない方は以下の記事が参考になるかもしれません。
r を最も小さい円の半径とすると、本問題は以下の数理計画問題として定式化できます。
\begin{aligned}
& \mathrm{maximize}&& r \\
& \mathrm{subject} \ \mathrm{to}&& r \leq r_i&(i = 1, 2, \dots, M + N) \\
&&& r_i > 0&(i = 1, 2, \dots, M + N) \\
&&& r_i + r_j \leq \sqrt{(x_i – x_j)^2 + (y_i – y_j)^2}&(i \neq j)
\end{aligned}
i と j について場合分けを行い、r を最大化できるよう r_i の値の範囲を絞ります。また、記述を簡単にするために d_{ij} \coloneqq \sqrt{(x_i – x_j)^2 + (y_i – y_j)^2} とおきます。
場合 1 i = 1, \dots, N のとき
r_i は入力として与えられます。
場合 2 i = N + 1, \dots, N + M かつ j = 1, \dots, N のとき
(x_i, y_i), (x_j, y_j), r_j が入力として与えられるため、r_i は以下の不等式を満たす必要があります。
r_i \leq d_{ij} – r_j
場合 3 i = N + 1, \dots, N + M かつ j = N + 1, \dots, N + M のとき
(x_i, y_i), (x_j, y_j) が入力として与えられるため、r_i と r_j は以下の不等式を満たす必要があります。
r_i + r_j \leq d_{ij}
r \leq r_i かつ r \leq r_j のもとで r の最大化を考えているため、r_i の範囲を以下に制限しても r の最大値は変わりません。
r_i \leq \frac{1}{2} d_{ij}
実際、r_i を \frac{1}{2} d_{ij} より大きくすると r \leq r_j<\frac{1}{2} d_{ij} となり、r の上からの制約が厳しくなります。
以上の場合分けから、r_i を以下を満たす範囲で考えても r の最大値は変わりません。
0<r_i \leq \min \left(
\min_{1 \leq j \leq N} d_{ij} – r_j,
\min_{N + 1 \leq j \leq N + M} \frac{1}{2} d_{ij},
\right ) \quad i = N + 1, \dots, N + M
問題文の制約から上記の集合は空集合ではありません。上記を満たす任意の r_i について、問題文の条件を満たしてエンブレムを作成できます。
r \leq r_i であるため、上記の不等式の \leq で等号が成立するときの r_i の最小値が r の最大値になります。式としては以下の通りです。
\begin{aligned}
A &= \min_{1 \leq i \leq N} r_i \\
B &= \min_{N + 1 \leq i \leq N + M, 1 \leq j \leq N} d_{ij} – r_j \\
C &= \min_{N + 1 \leq i \leq N + M, N + 1 \leq j \leq N + M, i \neq j} \frac{1}{2} d_{ij} \\
r &= \min_{1 \leq i \leq N + M} r_i = \min (A, B, C)
\end{aligned}
各 d_{ij} を計算するのに O(M^2 + N^2), 最小値の探索に O(M + N) かかるため、全体の計算量は O(M^2 + N^2) = 10^5 程度です。実行時間制限を満たして解答できます。
i = N + 1, \dots, N + M の半径を最小値に揃えても、最小値は変わりません。また、「接してもよいが, どの円も他の円と交わるまたは含んではならない」という条件を元の半径が満たしていれば、半径を最小値に揃えても条件を満たします。
そこで求める値を二分探索することを考えます。半径 r を与えたときに i = N + 1, \dots, N + M に対し r_i \coloneqq r とします。「接してもよいが, どの円も他の円と交わるまたは含んではならない」という条件を満たす判定は i = 1, \dots, N + M, j = 1, \dots, N + M に対し以下の不等式が成立するかで判定すればよいです。
r_i + r_j \leq d_{ij} \quad (i \neq j)
上記の判定は O(M^2 + N^2) でできます。不等式を精査すれば O(1) での判定もできるようになりますが、それは解答例 1 とあまり変わらないため、ここでは精査せず、愚直に判定します。
r の探索範囲は [0, \min_{1\leq i \leq N} r_i + \varepsilon)になります。r_i \leq 100 であり、解答は相対誤差または絶対誤差が 10^{-6} 以内であればよいため、\varepsilon = 10^{-6} として終了条件を区間の大きさが 10^{-6} 以下とします。探索の回数は \log_{2} 10^8 \leq 30 程度になります。
全体の計算量は 10^5 \times 10^2 = 10^7 程度になります。
91. AtCoder Beginner Contest 144 D – Water Bottle
x の大きさによって水が溢れないギリギリに水筒を傾けたときの水の形状が異なるため、場合分けします。\theta を傾ける角度とします。
場合 1 x \geq \frac{1}{2} a^2 b のとき
水の形状は下図のように台形 (正確には四角柱) になります。
水の体積 x は以下の等式を満たします。
x = \frac{1}{2} a^2 (2 b – a \tan \theta)
これを \theta について解くと以下のようになります。
\theta = \arctan \left ( \frac{2b}{a} – \frac{2x}{a^3} \right)
場合 2 x \leq \frac{1}{2} a^2 b のとき
水の形状は下図のように三角形 (正確には三角柱) になります。
水の体積 x は以下の等式を満たします。
x = \frac{a b^2}{2 \tan \theta}
これを \theta について解くと以下のようになります。
\theta = \arctan \frac{a b^2}{2 x}
c++ の場合、逆正接関数 atan があるため、その関数を用いると解答できます。
計算量は O(1) です。
逆正接関数を知らない場合は二分探索でも解けます。
水が溢れるかの判定は \theta が以下の不等式を満たすかで判定できます。
\begin{aligned}
x \geq \frac{1}{2} a^2 b \ \text{のとき} \quad
x& \leq \frac{1}{2} a^2 (2 b – a \tan \theta) \\
x \leq \frac{1}{2} a^2 b \ \text{のとき} \quad
x& \leq \frac{a b^2}{2 \tan \theta} \\
\end{aligned}
水筒を横に倒すと水は必ず溢れるため、度数法で 90 が \theta の上界です。探索範囲は [0, 90) となります。解答は絶対誤差または相対誤差が 10^{−6} 以下であればよいため、終了条件を区間の大きさが 10^{-6} 以下とします。探索の回数は \log_{2} 10^8 \leq 30 程度になります。
