ABC 268 E — Chinese Restaurant (Three-Star Version)

考察

各人iの不満度は、正面に料理iが来る回転t_iからの円環距離であり、傾き+1と−1の二つの一次区間からなる三角波である。軸を0..2N−1へ広げれば周期境界をまたぐ区間を通常の半開区間として扱える。傾きと切片を別々の差分配列へ区間加算し、累積後の値f(x)=a_x x+b_xを計算する。各剰余xについてxとx+Nの寄与を足せば元のN回転分が得られる。

具体的には h=floor(N/2) として、[t_i,t_i+h+1) へ x−t_i、[t_i+h+1,t_i+N) へ −x+t_i+N を足す。Nが奇数なら頂上の二点は同値、偶数なら頂上は一点となり、この分け方で両方を扱える。

典型の発動条件

区間一次式のimos法

発動条件: 多数の寄与が区間ごとにax+bで表され、全整数点で総和を求めるとき。

傾きと切片の二差分配列を持ち、累積した係数へ各xを代入する。

円環区間の二倍展開

発動条件: 周期境界をまたぐpiecewise関数や区間を通常の連続区間として扱いたいとき。

index範囲を2周期へ広げ、一周期分の区間をwrapなしで加算してresidueへfoldする。

問題固有の要素

dish d の初期正面personをpos[d]とすれば、正面一致の中心回転は t_d=(d−pos[d]) mod N である。

別の問題へ持ち帰る視点: 円環配置では対象物の現在位置から目標位置へのrotation offsetを先に逆permutationで求める。

正当性

一次式 ax+bの区間加算はaとbを別々のimos配列へ加え、累積後にa_x x+b_xを評価すればよい。 長さNの半開区間 [t_i,t_i+N) は各rotation residue xについてxまたはx+Nのちょうど一方を含み、円環波形を二倍配列から復元できる。 mod Nをまたぐ三角波を通常の線形区間にでき、一人当たり定数回のrange affine addで全回転へ寄与を配れる。

実装上の注意

  • 各人の二つの半開区間へ傾きと切片を加算する。右端は含めず、t_i+Nも差分の取り消し位置として確保する。
  • 総不満度はN²規模になり得るため64bit整数を使い、差分配列は終端2Nまで確保する。

復習の核

  • 円環上の距離和は、各対象の理想offsetを中心とする三角波として全候補同時評価を考える。
  • 区間上で線形な寄与は値を直接足さず、傾き・切片を別々にrange addする。

計算量と制約

時間

O(N)、各人は定数個の一次式区間へ寄与。

空間

O(N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 3 \leq N \leq 2 \times 10^5; 0 \leq p_i \leq N-1; p_i \neq p_j if i \neq j.; All values in input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Chinese Restaurant (Three-Star Version) の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 一次元・二次元累積和と差分で区間情報を線形化する

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

      主タグ: 累積和・差分配列

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

      学習の位置

      体系上の位置: 一次元・二次元累積和と差分で区間情報を線形化する

      • prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。

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

      • オンライン更新を伴うFenwick Tree・Segment Treeの動的区間要約。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題