ABC 250 F — One Fourth

考察

切り口の一端を固定し、もう一端を反時計回りに進めると、切り取る面積は増えていく。目標の四分の一に最も近い候補は、その目標を跨ぐ前後に絞れる。さらに、始点を進めると切片から三角形が一つ減ることに注目すれば、目標を跨ぐ境界も右へ進むだけで追える。

対角線は N(N−3)/2N(N-3)/2 本ある。各切片の面積を定数時間で求められても、全列挙には O(N2)O(N^2) 時間かかり、N≤105N\leq 10^5 では間に合わない。面積を求める方法と、調べる端点を減らす方法を順に考える。

切片と二倍面積を定める

入力の頂点を0始まりで P0,…,PN−1P_0,\ldots,P_{N-1} とし、反時計回りの順序をそのまま使う。巡回を通常の添字で扱うため、Pi+N=PiP_{i+N}=P_i として頂点列を二周分並べる。

始点を ll、終点を rr とし、頂点列 Pl,Pl+1,…,PrP_l,P_{l+1},\ldots,P_r と弦 PrPlP_rP_l で囲まれる側を切片と呼ぶ。その二倍面積を E(l,r)E(l,r)、多角形全体の二倍面積を SS とする。合法な対角線の範囲は

l+2≤r≤l+N−2l+2\leq r\leq l+N-2

である。反対側の切片は、始点を r mod Nr\bmod N にした巡回でも現れるので、0≤l<N0\leq l<N をすべて調べれば食べる側の選択も網羅できる。

走査の補助として、r=l+1r=l+1 では面積0、r=l+N−1r=l+N-1 では全体の面積、すなわち E(l,l+1)=0E(l,l+1)=0、E(l,l+N−1)=SE(l,l+N-1)=S とする。この二つは端点が隣接するため、答えの候補には含めない。

二つのベクトル u=(ux,uy)u=(u_x,u_y)、v=(vx,vy)v=(v_x,v_y) の外積を u×v=uxvy−uyvxu\times v=u_xv_y-u_yv_x と書く。頂点 Pl,Pr,Pr+1P_l,P_r,P_{r+1} の順は反時計回りなので、三角形の二倍面積は (Pr−Pl)×(Pr+1−Pl)≥0(P_r-P_l)\times(P_{r+1}-P_l)\geq 0 である。全体も P0P_0 を中心とする三角形の和から求められる。

S=∑i=1N−2(Pi−P0)×(Pi+1−P0)S=\sum_{i=1}^{N-2}(P_i-P_0)\times(P_{i+1}-P_0)

実際の全体面積は S/2S/2、切片面積は E/2E/2 だから、要求された出力値は

8∣S/24−E2∣=∣S−4E∣8\left|\frac{S/2}{4}-\frac{E}{2}\right|=|S-4E|

となる。したがって、割り算も浮動小数点も使わず、4E4E と SS を比較すればよい。

三角形一つの加減で更新する

右端を rr から r+1r+1 へ進めると、元の切片に三角形 (Pl,Pr,Pr+1)(P_l,P_r,P_{r+1}) が加わる。よって更新式は

E(l,r+1)=E(l,r)+(Pr−Pl)×(Pr+1−Pl)E(l,r+1)=E(l,r)+(P_r-P_l)\times(P_{r+1}-P_l)

である。一方、右端を固定して左端を l+1l+1 へ進めると、三角形 (Pl,Pl+1,Pr)(P_l,P_{l+1},P_r) が切片から除かれる。

E(l+1,r)=E(l,r)−(Pl+1−Pl)×(Pr−Pl)E(l+1,r)=E(l,r)-(P_{l+1}-P_l)\times(P_r-P_l)

凸多角形なので、これらの三角形は元の多角形の内側にあり、重なりやはみ出しなく加減できる。右端を進めると面積は減らず、左端を進めると増えない。

例えば P0=(0,0),P1=(4,0),P2=(4,2),P3=(0,2)P_0=(0,0),P_1=(4,0),P_2=(4,2),P_3=(0,2) の長方形では S=16S=16 である。l=0,r=1,E=0l=0,r=1,E=0 から右端を2に進めると、外積 (4,0)×(4,2)=8(4,0)\times(4,2)=8 を加えて E=8E=8 となり、4E≥S4E\geq S を満たす。次に左端を1に進めると同じ三角形の二倍面積8を引き、E(1,2)=0E(1,2)=0 に戻る。右端を3へ進めれば (0,2)×(−4,2)=8(0,2)\times(-4,2)=8 を加えて再び目標を超える。このとき境界は2から3へ進んでいる。

目標を跨ぐ最初の境界を引き継ぐ

各 ll について、4E(l,r)≥S4E(l,r)\geq S となる最初の右端を qlq_l とする。補助状態の r=l+N−1r=l+N-1 では E=SE=S なので、この境界は必ず存在する。固定した ll では面積が単調に増えるため、目標に最も近い候補は ql−1q_l-1 と qlq_l のうち、合法な範囲にあるものだけでよい。最小の切片がすでに目標以上なら前者は空の補助状態となり、最大の合法切片でも目標未満なら後者が全体の補助状態となる。

ここで左端を進めると、同じ右端での面積は三角形の削除により減る。以前に目標未満だった右端は、次の左端でも目標未満のままである。従って、次の境界が以前の境界より左に来ることはない。右端を戻さずに追える対象は、この「初めて目標以上になる境界」である。

保持する値を現在の二倍面積 E=E(l,r)E=E(l,r) とし、次の手順で走査する。

  1. 全体の二倍面積 SS を求め、r=1,E=0r=1,E=0、答えを未更新とする。

  2. l=0,1,…,N−1l=0,1,\ldots,N-1 の順に、4E<S4E<S かつ r<l+N−1r<l+N-1 の間、右端の更新式で三角形を加えてから rr を1増やす。終了時の rr が qlq_l である。

  3. rr が合法なら ∣S−4E∣|S-4E| で答えを更新する。r−1r-1 が合法なら、最後に加わった三角形を除いた二倍面積

    E−=E−(Pr−1−Pl)×(Pr−Pl)E_-=E-(P_{r-1}-P_l)\times(P_r-P_l)

    を使い、∣S−4E−∣|S-4E_-| でも更新する。保持中の EE 自体は変えない。

  4. 左端の更新式で三角形を引き、次の ll へ進む。rr は引き継ぎ、戻さない。

跨ぐ直前の面積は手順3で復元するので、右端を伸ばす途中の全候補を保存する必要はない。前回の境界が次回も境界なら、伸ばす操作が0回でも同じ手順で両側を評価できる。

典型の発動条件

凸多角形の二点法

一端を固定したときに評価量が他端に対して単調なら、目標を跨ぐ前後へ候補を絞れる。さらに左端を進めても境界が後退しないことを確かめれば、始点ごとの探索を尺取り法にまとめられる。固定始点での単調性だけでは、右端を引き継げる根拠としては足りない。

外積による面積差分

端点の移動で領域から何が増減するかに注目する。差分が三角形一つなら、その二倍面積を外積で求めて定数時間で更新できる。整数座標では、比較式全体の分母を払うことで誤差なく判定できる。

問題固有の要素

反時計回りの凸多角形という条件により、連続する頂点の切片を三角形の加減で扱え、両端の移動に対する面積の変化方向が定まる。凹多角形では弦が外へ出たり外積が負になったりするため、この走査をそのまま使えない。

また、目標が全体の四分の一で、出力が差の8倍であることから、二倍面積による整数式 ∣S−4E∣|S-4E| がそのまま出力値になる。

正当性

三角形の加減式は切片の領域の差と一致するため、保持する EE は常に現在の切片の二倍面積である。各三角形の外積は非負なので、固定した左端に対して E(l,r)E(l,r) は非減少となる。境界より前では S−4ES-4E が非増加、境界以降では 4E−S4E-S が非減少だから、合法な右端の中での最小差は境界の直前か境界そのものにある。境界が合法範囲の外なら、残る側の端点だけを評価すればよい。

前の境界を qlq_l とすると、t<qlt<q_l で次の左端にも使える右端 tt は、E(l+1,t)≤E(l,t)<S/4E(l+1,t)\leq E(l,t)<S/4 を満たす。次の左端では範囲外となる小さな右端も候補にはならない。従って ql+1≥qlq_{l+1}\geq q_l であり、前の境界から右へ伸ばせば、次の最初の境界に到達する。初回は空の状態から始め、全体の補助状態までには必ず目標以上になるので、走査は終了する。

手順3は各始点で必要な境界前後の合法候補を評価する。候補を絞る前の探索対象は各対角線の両側の切片を網羅しており、補助状態は評価から除かれる。比較値 ∣S−4E∣|S-4E| は要求された出力に等しいため、得られる最小値が答えである。

実装上の注意

  • 右端は巡回添字へ戻さず、増え続ける整数で持つ。各左端で r≤l+N−1r\leq l+N-1 を守れば、最後の l=N−1l=N-1 でも r≤2N−2r\leq 2N-2 で収まる。
  • 評価する端点が l+2l+2 以上 l+N−2l+N-2 以下かを、境界側と直前側それぞれで確認する。空の切片や全体の補助状態を答えへ混ぜない。
  • 右端の更新では古い rr で外積を求めてから増やす。左端の更新でも古い ll で引く三角形を求める。直前候補用の E−E_- を保持中の EE へ代入すると、次の左端への更新が合わなくなる。
  • 座標差と積を含め、初めから符号付き64ビット整数で計算する。座標範囲の正方形の面積は 6.4×10176.4\times 10^{17} 以下なので、S≤1.28×1018S\leq 1.28\times 10^{18}、4E≤5.12×10184E\leq 5.12\times 10^{18} で64ビットに収まる。SS を非負の三角形面積の和で求めれば、途中の和もこの範囲を超えない。32ビットの積を計算した後で型を広げては遅い。

復習の核

  • 右端を引き継ぐ前に、「何の境界を追うか」と「左端を消してもその境界が戻らない理由」を別々に確かめる。
  • 幾何の更新では、二つの領域の差を描き、増減する三角形の頂点順から外積式を作る。
  • 目標に最も近い値は、単調列が目標を跨ぐ前後を比べる。探索用に加えた空・全体の状態と、問題で選べる候補の範囲を区別する。

計算量と制約

時間

全体面積の計算と頂点列の複製に O(N)O(N) 時間かかる。左端は NN 回、右端は1から高々 2N−22N-2 までしか進まず、各移動と各始点の候補評価は O(1)O(1) 時間なので、全体で O(N)O(N) 時間である。

空間

二周分の頂点列に O(N)O(N) 空間を使う。面積・端点・答えの保持は O(1)O(1) 空間であり、入力の保持を含めて全体で O(N)O(N) 空間である。

制約との対応

公式制約は 4≤N≤1054\leq N\leq 10^5、整数座標 ∣Xi∣,∣Yi∣≤4×108|X_i|,|Y_i|\leq 4\times 10^8、頂点は反時計回りの凸多角形をなす。時間制限2秒・メモリ制限1024 MiBに対し、線形時間・線形空間で処理できる。最小の N=4N=4 でも合法な終点は各始点に一つ存在し、補助状態を除いて比較できる。凸性と頂点順は、面積更新の符号と境界の単調性の両方に使っている。

出典

分類・前提・執筆情報

掲載状態: 収録済み

One Fourth の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 尺取り法・sliding windowで連続区間を走査する

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: 尺取り法・sliding window

    補助タグ: 幾何の基本判定・配置・座標変換

    執筆: abc-explanation-author1.1.1 / revision 2

    学習の位置

    体系上の位置: 尺取り法・sliding windowで連続区間を走査する

    • 一列の窓または二列の現在blockに関する不変条件を保ち、各pointerを単調に進められる。

    先に読む単元:

    この解説で扱わないこと:

    • 値域上の真偽境界を探す二分探索・パラメトリックサーチ。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題