考察
切り口の一端を固定し、もう一端を反時計回りに進めると、切り取る面積は増えていく。目標の四分の一に最も近い候補は、その目標を跨ぐ前後に絞れる。さらに、始点を進めると切片から三角形が一つ減ることに注目すれば、目標を跨ぐ境界も右へ進むだけで追える。
対角線は 本ある。各切片の面積を定数時間で求められても、全列挙には 時間かかり、 では間に合わない。面積を求める方法と、調べる端点を減らす方法を順に考える。
切片と二倍面積を定める
入力の頂点を0始まりで とし、反時計回りの順序をそのまま使う。巡回を通常の添字で扱うため、 として頂点列を二周分並べる。
始点を 、終点を とし、頂点列 と弦 で囲まれる側を切片と呼ぶ。その二倍面積を 、多角形全体の二倍面積を とする。合法な対角線の範囲は
である。反対側の切片は、始点を にした巡回でも現れるので、 をすべて調べれば食べる側の選択も網羅できる。
走査の補助として、 では面積0、 では全体の面積、すなわち 、 とする。この二つは端点が隣接するため、答えの候補には含めない。
二つのベクトル 、 の外積を と書く。頂点 の順は反時計回りなので、三角形の二倍面積は である。全体も を中心とする三角形の和から求められる。
実際の全体面積は 、切片面積は だから、要求された出力値は
となる。したがって、割り算も浮動小数点も使わず、 と を比較すればよい。
三角形一つの加減で更新する
右端を から へ進めると、元の切片に三角形 が加わる。よって更新式は
である。一方、右端を固定して左端を へ進めると、三角形 が切片から除かれる。
凸多角形なので、これらの三角形は元の多角形の内側にあり、重なりやはみ出しなく加減できる。右端を進めると面積は減らず、左端を進めると増えない。
例えば の長方形では である。 から右端を2に進めると、外積 を加えて となり、 を満たす。次に左端を1に進めると同じ三角形の二倍面積8を引き、 に戻る。右端を3へ進めれば を加えて再び目標を超える。このとき境界は2から3へ進んでいる。
目標を跨ぐ最初の境界を引き継ぐ
各 について、 となる最初の右端を とする。補助状態の では なので、この境界は必ず存在する。固定した では面積が単調に増えるため、目標に最も近い候補は と のうち、合法な範囲にあるものだけでよい。最小の切片がすでに目標以上なら前者は空の補助状態となり、最大の合法切片でも目標未満なら後者が全体の補助状態となる。
ここで左端を進めると、同じ右端での面積は三角形の削除により減る。以前に目標未満だった右端は、次の左端でも目標未満のままである。従って、次の境界が以前の境界より左に来ることはない。右端を戻さずに追える対象は、この「初めて目標以上になる境界」である。
保持する値を現在の二倍面積 とし、次の手順で走査する。
-
全体の二倍面積 を求め、、答えを未更新とする。
-
の順に、 かつ の間、右端の更新式で三角形を加えてから を1増やす。終了時の が である。
-
が合法なら で答えを更新する。 が合法なら、最後に加わった三角形を除いた二倍面積
を使い、 でも更新する。保持中の 自体は変えない。
-
左端の更新式で三角形を引き、次の へ進む。 は引き継ぎ、戻さない。
跨ぐ直前の面積は手順3で復元するので、右端を伸ばす途中の全候補を保存する必要はない。前回の境界が次回も境界なら、伸ばす操作が0回でも同じ手順で両側を評価できる。
典型の発動条件
凸多角形の二点法
一端を固定したときに評価量が他端に対して単調なら、目標を跨ぐ前後へ候補を絞れる。さらに左端を進めても境界が後退しないことを確かめれば、始点ごとの探索を尺取り法にまとめられる。固定始点での単調性だけでは、右端を引き継げる根拠としては足りない。
外積による面積差分
端点の移動で領域から何が増減するかに注目する。差分が三角形一つなら、その二倍面積を外積で求めて定数時間で更新できる。整数座標では、比較式全体の分母を払うことで誤差なく判定できる。
問題固有の要素
反時計回りの凸多角形という条件により、連続する頂点の切片を三角形の加減で扱え、両端の移動に対する面積の変化方向が定まる。凹多角形では弦が外へ出たり外積が負になったりするため、この走査をそのまま使えない。
また、目標が全体の四分の一で、出力が差の8倍であることから、二倍面積による整数式 がそのまま出力値になる。
正当性
三角形の加減式は切片の領域の差と一致するため、保持する は常に現在の切片の二倍面積である。各三角形の外積は非負なので、固定した左端に対して は非減少となる。境界より前では が非増加、境界以降では が非減少だから、合法な右端の中での最小差は境界の直前か境界そのものにある。境界が合法範囲の外なら、残る側の端点だけを評価すればよい。
前の境界を とすると、 で次の左端にも使える右端 は、 を満たす。次の左端では範囲外となる小さな右端も候補にはならない。従って であり、前の境界から右へ伸ばせば、次の最初の境界に到達する。初回は空の状態から始め、全体の補助状態までには必ず目標以上になるので、走査は終了する。
手順3は各始点で必要な境界前後の合法候補を評価する。候補を絞る前の探索対象は各対角線の両側の切片を網羅しており、補助状態は評価から除かれる。比較値 は要求された出力に等しいため、得られる最小値が答えである。
実装上の注意
- 右端は巡回添字へ戻さず、増え続ける整数で持つ。各左端で を守れば、最後の でも で収まる。
- 評価する端点が 以上 以下かを、境界側と直前側それぞれで確認する。空の切片や全体の補助状態を答えへ混ぜない。
- 右端の更新では古い で外積を求めてから増やす。左端の更新でも古い で引く三角形を求める。直前候補用の を保持中の へ代入すると、次の左端への更新が合わなくなる。
- 座標差と積を含め、初めから符号付き64ビット整数で計算する。座標範囲の正方形の面積は 以下なので、、 で64ビットに収まる。 を非負の三角形面積の和で求めれば、途中の和もこの範囲を超えない。32ビットの積を計算した後で型を広げては遅い。
復習の核
- 右端を引き継ぐ前に、「何の境界を追うか」と「左端を消してもその境界が戻らない理由」を別々に確かめる。
- 幾何の更新では、二つの領域の差を描き、増減する三角形の頂点順から外積式を作る。
- 目標に最も近い値は、単調列が目標を跨ぐ前後を比べる。探索用に加えた空・全体の状態と、問題で選べる候補の範囲を区別する。
計算量と制約
時間
全体面積の計算と頂点列の複製に 時間かかる。左端は 回、右端は1から高々 までしか進まず、各移動と各始点の候補評価は 時間なので、全体で 時間である。
空間
二周分の頂点列に 空間を使う。面積・端点・答えの保持は 空間であり、入力の保持を含めて全体で 空間である。
制約との対応
公式制約は 、整数座標 、頂点は反時計回りの凸多角形をなす。時間制限2秒・メモリ制限1024 MiBに対し、線形時間・線形空間で処理できる。最小の でも合法な終点は各始点に一つ存在し、補助状態を除いて比較できる。凸性と頂点順は、面積更新の符号と境界の単調性の両方に使っている。
出典