この記事は 【AtCoder】初中級者が解くべき過去問精選 100 問を緑色コーダーが C++ で解いてみた の子記事です。お読みになる前に親記事をご確認ください。
8. Square869120Contest #6 B – AtCoder Markets
10^9 個のマスに入口と出口を置いて移動とき間の合計を探索するのは実行時間制限に違反する可能性があります。マスの個数に比べて買い物客の人数 N は N \leq 30 と少ないです。買い物客の情報 (A_i, B_i) だけで探索できないか考えます。
入口のマスを X, 出口のマスを Y とおきます。
X \leq Y としてよいです。もし X > Y で最小値をとる場合、入口と出口を取り替えて、買い物客に逆順に巡ってもらえばよいためです。
このとき A_i \leq B_i より、買い物客は入口 → A_i → B_i → 出口の順で回るのが最短になります。
A_i, B_i, X, Y の値の大小で場合分けして確認します。
場合 1 A_i \leq B_i \leq X \leq Y のとき
A_i から回っても B_i から回っても同じ移動時間です。
場合 2 A_i \leq X \leq B_i \leq Y のとき
A_i から回った方が 2 (B_i – X) 秒短くなります。
場合 3 A_i \leq X \leq Y \leq B_i のとき
A_i から回った方が 2 (Y – X) 秒短くなります。
場合 4 X \leq A_i \leq B_i \leq Y のとき
A_i から回った方が 2 (B_i – A_i) 秒短くなります。
場合 5 X \leq A_i \leq Y \leq B_i のとき
A_i から回った方が 2 (Y – A_i) 秒短くなります。
場合 6 X \leq Y \leq A_i \leq B_i のとき
A_i から回っても B_i から回っても同じ移動時間です。
i 人目の買い物客の移動時間は下記の式で表現できます。
| A_i – X | + | B_i – A_i | + | Y – B_i |
買い物客の移動の速さは 1 マス / 秒であるため、移動時間 = 移動距離 \div \ 1 = 移動距離です。第 1 項が入口 X からマス A_i までの移動距離、第 2 項がマス A_i からマス B_i への移動距離、第 3 項がマス B_i から出口 Y への移動時間です。
i 人目の移動時間の式から「すべての買い物客の移動時間の合計」は下記になります。
\begin{aligned}
&\sum_{i=1}^N \lparen | A_i – X | + | B_i – A_i | + | Y – B_i | \rparen \\
= &\sum_{i=1}^N | A_i – X | + \sum_{i=1}^N | B_i – A_i | + \sum_{i=1}^N | Y – B_i |
\end{aligned}
右辺の第 1 項は X にのみに依存し、第 2 項は X, Y に依存せず、第 3 項は Y にのみ依存しています。このことから「すべての買い物客の移動時間の合計」を最小化したい場合は X, Y の組み合わせを考える必要がなく、第 1 項を X について最小化、第 3 項を Y について最小化すれば良いことがわかります。また、第 1 項と第 3 項は式の形としては同じであるため、第 1 項の最小化と第 3 項の最小化は同じ問題であることがわかります。
整理すると、i 番目の買い物客が入口 X からマス A_i に移動するとき、すべての買い物客の移動時間の合計の最小値を求めなさい、という問題に帰着できます。
式の形から A_i \leq A_{i+1} としても一般性は失われません。また、N \leq 30 のため、ソート (O(N \log N)) しても計算時間に余裕はあります。以降 A_i \leq A_{i+1} とします。
これから 2 つの考え方で移動時間の合計が最小になるときの X を求めます。どちらの考え方でも結論は同じため、わかりやすい方で理解いただければと思います。
考え方 1
I_S を集合 S の指示関数とします。言い換えると I_S を x\in S なら I_S(x) = 1, x \notin S なら I_S(x) = 0 となる関数とします。また、形式的に A_0 = -\infty, A_{N+1} = \infty とします。これらを使って \sum_{i=1}^N | A_i – X | が区間 (A_i, A_{i+1}] でどのような関数なのかわかるように変形します。
\begin{aligned}
&\sum_{i=1}^N | A_i – X | \\
= &\sum_{i=1}^N \lparen – (X – A_i) I_{(- \infty, A_i]}(X) + (X – A_i) I_{(A_i, \infty)}(X) \rparen \\
= &\sum_{i=1}^N -X I_{(- \infty, A_i]}(X) + \sum_{i=1}^N A_i I_{(- \infty, A_i]}(X) + \sum_{i=1}^N X I_{(A_i, \infty)}(X) – \sum_{i=1}^N A_i I_{(A_i, \infty)}(X) \\
\end{aligned}
\begin{aligned}
\text{第 1 項}
&= \sum_{i=1}^N -X I_{(-\infty, A_i]}(X) = \sum_{i=1}^N \sum_{j=1}^i -X I_{(A_{j-1}, A_j]}(X) \\
&= \sum_{j=1}^N \sum_{i=j}^N -X I_{(A_{j-1}, A_j]}(X)
= \sum_{j=1}^N – (N + 1 – j) X I_{(A_{j-1}, A_j]}(X) \\
\text{第 2 項}
&= \sum_{i=1}^N A_i I_{(- \infty, A_i]}(X)
= \sum_{i=1}^N \sum_{j=1}^i A_i I_{(A_{j-1}, A_j]}(X)
= \sum_{j=1}^N \sum_{i = j}^N A_i I_{(A_{j-1}, A_j]}(X) \\
\text{第 3 項}
&= \sum_{i=1}^N X I_{(A_i, \infty)}(X)
= \sum_{i=1}^N \sum_{j=i}^N X I_{(A_j, A_{j+1}]}(X) \\
&= \sum_{j=1}^N \sum_{i=1}^j X I_{(A_j, A_{j+1}]}(X)
= \sum_{j=1}^N j X I_{(A_j, A_{j + 1}]}(X) \\
\text{第 4 項}
&= -\sum_{i=1}^N A_i I_{(A_i, \infty)}(X)
= \sum_{i=1}^N \sum_{j=i}^N -A_i I_{(A_j, A_{j+1}]}(X)
= \sum_{j=1}^N \sum_{i=1}^j -A_i I_{(A_j, A_{j+1}]}(X)
\end{aligned}
\begin{aligned}
\text{第 1 項} + \text{第 3 項}
&= \sum_{j=1}^N – (N + 1 – j) X I_{(A_{j-1}, A_j]}(X) + \sum_{j=1}^N j X I_{(A_j, A_{j + 1}]}(X) \\
&= \sum_{j=0}^{N} – (N – j) X I_{(A_{j}, A_{j+1}]}(X) + \sum_{j=0}^N j X I_{(A_j, A_{j + 1}]}(X) \\
&= \sum_{j=0}^{N} (2 j – N) X I_{(A_{j}, A_{j+1}]}(X) \\
\text{第 2 項} + \text{第 4 項}
&= \sum_{j=1}^N \sum_{i = j}^N A_i I_{(A_{j-1}, A_j]}(X) + \sum_{j=1}^N \sum_{i=1}^j -A_i I_{(A_j, A_{j+1}]}(X) \\
&= \sum_{j=0}^{N} \sum_{i = j + 1}^{N} A_i I_{(A_{j}, A_{j+1}]}(X) + \sum_{j=0}^N \sum_{i=1}^j -A_i I_{(A_j, A_{j+1}]}(X) \\
&= \sum_{j=0}^{N} \left ( \sum_{i = j + 1}^{N} A_i – \sum_{i=1}^j A_i \right ) I_{(A_{j}, A_{j+1}]}(X)
\end{aligned}
\begin{aligned}
\sum_{i=1}^N | A_i – X | = \sum_{j=0}^N \left ( (2 j – N) X + \sum_{i = j + 1}^{N} A_i – \sum_{i=1}^j A_i \right ) I_{(A_{j}, A_{j+1}]}(X)
\end{aligned}
以上の変形から \sum_{i=1}^N | A_i – X | は半開区間 (A_j, A_{j+1}] では、傾き 2 j – N, 切片 \sum_{i = j + 1}^{N} A_i – \sum_{i=1}^j A_i の一次関数になることがわかります。
| X | -\infty | \cdots | A_1 | \cdots | A_{\frac{N – 1}{2}} | \cdots | A_{\frac{N + 1}{2}} | \cdots | A_{\frac{N + 3}{2}} | \cdots | A_N | \cdots | \infty |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| f^{\prime} | – | – | – | + | + | + | |||||||
| f | \infty | \searrow | \searrow | \searrow | \nearrow | \nearrow | \nearrow | \infty |
N が偶数のときは以下のようになります。
| X | -\infty | \cdots | A_1 | \cdots | A_{\frac{N}{2}} | \cdots | A_{\frac{N+2}{2}} | \cdots | A_N | \cdots | \infty |
|---|---|---|---|---|---|---|---|---|---|---|---|
| f^{\prime} | – | – | 0 | + | + | ||||||
| f | \infty | \searrow | \searrow | \rightarrow | \nearrow | \nearrow | \infty |
以上から、\sum_{i=1}^N | A_i – X | は X = A_{\frac{N+1}{2}} (N が奇数のとき), A_{\frac{N}{2}} \leq X \leq A_{\frac{N+2}{2}} (N が偶数のとき) のとき、つまり X が A_1, A_2 \dots A_N の中央値のとき、最小値をとることがわかります。
考え方 2
A_{i}<X<A_{i+1} に入口を置いてみます。このときの移動時間の合計は下記の式になります。
\sum_{j=1}^{i} (X – A_j) + \sum_{j=i+1}^N (A_j – X)
もし、入口を X + 1 に移動した場合、移動時間の合計の差は
\begin{aligned}
&\sum_{j=1}^{i} (X + 1 – A_j) + \sum_{j=i+1}^N (A_j – (X + 1)) – \sum_{j=1}^{i} (X – A_j) – \sum_{j=i+1}^N (A_j – X) \\
= &\sum_{j=1}^{i} 1 – \sum_{j=i+1}^N 1 = i – (N – i) = 2 i – N
\end{aligned}
となります。i<N/2 つまり、入口より左側に半数未満のお店しかない場合は、右側に入口を動かした方が移動時間の合計を小さくできることがわかります。同様に、入口より右側に半数未満のお店しかない場合は、左側に入口を移動した方が移動時間の合計を小さくできます。
結局、移動時間の合計が最小になり得るのは、X の左右にあるお店の数が等しいときのみです。N が奇数のときは X = A_{\frac{N+1}{2}} です。N が偶数の時は A_{\frac{N}{2}} \leq X \leq A_{\frac{N+2}{2}} が候補ですが、先の式から入口を X から X + 1 に移動させても、差は 2 \times (N / 2) – N = 0 となり、値が変わらないこと、つまり、どこでも最小値になることがわかります。
以上から、X が A_1, A_2 \dots A_N の中央値の時、最小値をとることがわかります。
A_1, A_2 \dots A_N の中央値はソート後に、添字 \frac{N+1}{2} の値(N が奇数のとき)、添字 \frac{N}{2} の値と添字 \frac{N+2}{2} の値の平均 (N が偶数のとき) を取れば O(N \log N) = 10^3 程度で求まります。中央値を線形時間で求めるアルゴリズムもありますが、プログラミング言語のライブラリにあるソート関数を使った方が手軽だと思います。
また、偶数の場合、2 つの値の平均を中央値としますが、この問題の場合は 2 つの値の間ならどこでも良いです。そのため、偶数のときはX = A_{\frac{N + 2}{2}} とすると C++ では奇数・偶数の場合分けが不要になります。
9. JOI 2008 予選 4 – 星座探し
探したい星座を並行移動させて星座の星のうち 1 つを写真の星の 1 つに重ねると、以下のいずれかの場合になります。
場合 1 星座のすべての星が写真の星に重なるとき
星座の星と写真の星の対応が合っている場合です。
場合 2 写真の星に重ならない星座の星が存在するとき
星座の星と写真の星の対応が間違っている場合です。
問題文には下記の記述があります。
写真には必ず，探したい星座と同じ形・向き・大きさの図形がちょうど一つ含まれている．
そのため、星座の星のうちの 1 つを平行移動し、写真の各星に合わせて 1 か 2 かを確認していくと、ちょうど 1 回だけ 1 の場合になります。1 の場合になった際に平行移動の量を出力すれば解答となります。
指定の座標に星があるかの判定ですが、set などで写真の星の座標を保持しておくことで判定できます。
x, y の範囲が 0 \leq x, y \leq 10^6 であり、(x, y) の組み合わせは 10^{12} を超えるため、バケットは使えません。char 型を使っても 1 TB を超えるメモリを確保しなければならず、メモリ制限に違反します。
計算量を確認します。
写真内の 1 つの座標の星の有無の判定に O(\log n) かかるため、平行移動後に 1 か 2 かを判定するのに星座の星の数 m に比例して O(m\log n) かかります。写真内の n 個の星すべてを試すため、計算量は O(mn \log n) = 10^7 程度です。
