新年のごあいさつ

\(2025\) 年、あけましておめでとうございます。

皆さん、おせち料理は食べましたか？おせち料理と言えば伊達巻、伊達巻と言えばパンケーキ(大嘘)、パンケーキと言えば 「パンケーキの定理」です。

パンケーキの定理

「パンケーキの定理」は有限かつ正の面積を持つ任意の \(2\) つの平面図形が与えられたとき、それらを \(1\) つの直線で同時に \(2\) 等分できることを意味する定理です(厳密には測度論を用いた定義が必要ですがここではイメージで十分です)。この定理は任意次元に拡張することができ (Stone–Tukey theorem)、\(3\) 次元バージョンは「ハムサンドイッチの定理」と呼ばれていたりします。

「パンケーキの定理」はそれぞれの平面図形が連続した領域であることを前提にした説明や証明がされることも多いですが、連続した領域でない場合にも問題無く成り立ちます。

つまり、この問題の答えは常にYesになります。

さて、あとは具体的に \(2\) 領域を同時に \(2\) 等分する直線を構成していきます(途中までパンケーキの定理の証明と並走する形になります)。

部分点解法 (\(N \le 105\)、c と s のみ)

本題に入る前に c と s のみが存在する部分点ケースを構築してみましょう。

c の領域と s の領域をともに \(2\) 等分するということは、\(2\) つを合わせた領域つまりケーキ全体も \(2\) 等分することになり、求める直線は 点 \((\frac{N}{2},\frac{N}{2})\) を必ず通ります。

よって、点 \((\frac{N}{2},\frac{N}{2})\) を通り、c の領域を \(2\) 等分する直線を \(1\) つ求めればよいことになります。

ここで、点 \((\frac{N}{2},\frac{N}{2})\) を通り、\(x\) 軸の正の向きから反時計回りに \(\theta\) \((0 \le \theta \le \pi)\) だけ回転した方向を持つ有向直線 \(l\) を考え、\(l\) の方向を向いた際に \(l\) より右側の領域を \(D\) とします。\(D\) と c の領域の共通部分の面積を \(f(\theta)\) とおき、 c の領域の面積を \(C\) とすると、\(f\) には次の性質があります。

\(f(0) + f(\pi) = C\) つまり \((f(0)-\frac{C}{2})+(f(\pi)-\frac{C}{2}) = 0\)

これは \(f(0)-\frac{C}{2}\) と \(f(\pi)-\frac{C}{2}\) の一方が \(0\) 未満のときもう一方は \(0\) より大きいことを意味します。そして、\(f(\theta)\) は自明に連続関数であるため、中間値の定理を使うことで、\(f(\theta)-\frac{C}{2} = 0\) つまり \(f(\theta) = \frac{C}{2}\) をみたす \(\theta\) が存在することがわかり、この \(\theta\) を二分探索で求められることもわかります。

\(f(\theta)\) の値を愚直に求めるのに \(O(N^2)\) の計算量を要するため、許容誤差を \(\epsilon\) として \(O(N^2 \log \frac{1}{\epsilon})\) で部分点を得ることができました。

満点解法 (\(N \le 2025\))

理論

それでは本題に取り掛かりましょう。

今度は直線が必ず通る定点が存在しませんが、先程と同様の考え方は使用することができます。

まずは c の領域を \(2\) 等分したまま直線を滑らかに回転させられることを簡単に示しましょう。このとき、回転の中心をケーキ上の点に保つことができると後で嬉しいです。

ある直線 \(l\) が c の領域を \(2\) 等分していると仮定します。ここで、\(l\) と c の領域の共通部分の「\(l\) 上の重心」を考え(共通部分を持たない場合はケーキ上の適当な点を「重心」とする)、この点を中心に \(l\) を微小角だけ反時計回りに回転させると、回転後の直線も c の領域を \(2\) 等分します ( \(l\) が c の領域の境界と正の長さを共有する場合は少し状況が複雑になりえますが、その場合も「重心」に相当する点の存在を中間値の定理で示す事ができます)。

常に「重心」はケーキ(境界を含む)に含まれるため、「ケーキ上の点を中心とした回転を繰り返すことで、c の領域を \(2\) 等分したまま直線を一方向に滑らかに回転させられる」ことが示せました。

あとは、この性質をみたす回転を有向直線の連続系列とみなし、系列内で \(x\) 軸の正の向きとなす符号付き角が \(\theta\) \((0 \le \theta \le \pi)\) である有向直線を \(l_\theta\)、\(l_\theta\) の方向を向いて \(l_\theta\) より右側の領域を\(D\)、\(D\) と s の領域の共通部分の面積を \(f(\theta)\) とおきます。

s の領域の面積を \(S\) とするとき、\(f(0)-\frac{S}{2}\) と \(f(\pi)-\frac{S}{2}\) の一方が \(0\) 未満のときもう一方は \(0\) より大きいことは部分点解法と同様に示せます。そして \(f(\theta)\) が連続であることは、回転中心の集合が有界領域(ケーキ)内に収まっていることから言えます。したがって、\(f(\theta)-\frac{S}{2} = 0\) つまり \(f(\theta) = \frac{S}{2}\) をみたす \(\theta\) が存在し、二分探索で求められます。

実装

ここまででは、解の存在証明(パンケーキの定理の部分問題の証明)を中心に説明してきましたが、実装上の課題は残っています。

まず条件をみたす有向直線の連続系列をどのように作るかです。

ここで簡単のため、直線の傾きを \(-1\) から \(1\) に制限した解法を、転置を挟んで \(2\) 回 (二分探索を行うべきは両端での \(f(\theta) - \frac{S}{2}\) の正負が異なる方のみなので、計算量としては \(1\) 回分ですが) 行うことにします。二分探索する値も偏角の代わりに傾きを採用します。

このとき、傾きが \(a\) であり、c の領域を \(2\) 等分する直線のうち、\(y\) 切片が最大であるものを採用すればよいです(イメージとしては \(y\) 軸の正の向きに直線を押し付けつつゆっくりと回転させることになり、ケーキ上の点を中心とした回転が実現できます)。

このような \(y\) 切片はさらなる二分探索で求めることができ、この時点でこの問題を許容誤差を \(\epsilon\) として \(O(N^2 \log^2 \frac{1}{\epsilon})\) で解くことができます。

しかしこれでは TLE してしまう可能性が高いです。\(-1 \le a \le 1\) であることと累積和を利用して、直線で分けられた片側の領域と c や s の領域の共通部分の面積を \(O(N)\) で求めましょう。

これは \(N\) 本の棒状領域に含まれる c や s の面積を累積和を用いてそれぞれ \(O(1)\) で求めることで実現でき、\(-1 \le a \le 1\) を考慮すると比較的少ない場合分けで実装できるため、定数倍が重くなることも防げます。

累積和の前計算の計算量は \(O(N^2)\) であるため、この問題を許容誤差を \(\epsilon\) として \(O(N^2 + N \log^2 \frac{1}{\epsilon})\) で解くことができました。これは十分高速です。

Bonus: ケーキが \(N \times M\) の長方形であり、制約が \(1 \le N \times M \le 2025105\) の場合も考えてみてください。